[Powered by Google Translate] [Paso a paso - conxunto de problemas 6] [Zamyla Chan - Harvard University] [Esta é CS50. - CS50.TV] 

Ola, todos, e ben benvida ao Paso a paso 6: Puff Huff'n. En Puff Huff'n o que estamos facendo vai estar lidando con un arquivo comprimido Huffman e despois golpe-lo de volta para descompactá-lo, para que poidamos traducir do 0s e 1s que o usuario envía-nos e convertela-lo de volta para o texto orixinal. Pset 6 vai ser moi legal porque está indo a ver algunhas das ferramentas que usou na pset 4 e 5 e pset tipo de combina-los nun concepto moi ordenado cando chegou a pensar sobre iso. 

Ademais, sen dúbida, pset 4 e 5 foron os máis reto serie de exercicios que tiñamos para ofrecer. Entón, a partir de agora, temos esa pset un máis en C, e despois diso que estamos diante de programación web. Entón felicitar-vos para estar máis a máis difícil corcova na CS50. 

Pasando para Puff Huff'n, a nosa caixa de ferramentas a este pset van ser árbores Huffman, para a comprensión non só como traballo árbores binarias, pero tamén árbores especialmente Huffman, como son construídos. E entón nós imos ter un monte de código distribución neste pset, e nós imos chegar a ver que, en realidade, parte do código Podemos non ser capaces de comprender plenamente aínda, e así eses serán os ficheiros. C, pero despois os seus acompañantes. arquivos h nos dará o suficiente comprensión de que necesitamos para que poidamos saber como esas funcións funcionan ou polo menos o que se quere facer - as súas entradas e saídas - mesmo se non sabemos o que está a suceder na caixa negra ou non entenden o que está a suceder na caixa negra dentro. E entón, finalmente, como de costume, estamos a tratar con estruturas de datos novos, tipos específicos de nós que ligan con certas cousas, e por iso aquí ter unha pluma e un papel non só para o proceso de deseño e cando está tentando descubrir como o seu pset debe funcionar pero tamén durante a depuración. Pode ter GDB á beira da súa pluma e papel, mentres toma para abaixo o que os valores son, onde as súas frechas están apuntando, e cousas así. 

En primeiro lugar, imos ollar para as árbores Huffman. Árbores Huffman son árbores binarias, o que significa que cada nodo só ten 2 fillos. En árbores Huffman característica é a de que os valores máis frecuentes son representados por menor número de bits. Nós vimos nos exemplos de conferencias do Código Morse, que tipo de consolidada algunhas letras. Se está tentando traducir un A ou E, por exemplo, está traducindo que, moitas veces, entón en vez de ter que usar todo o conxunto de bits alocados para ese tipo de datos de costume, comprimi-lo para abaixo, a menos, e despois as cartas que son representados con menos frecuencia son representados con anacos máis longos porque pode pagar que cando pesar as frecuencias que estas letras aparecen. Temos a mesma idea aquí en árbores Huffman onde estamos facendo unha corrente, unha especie de camiño para chegar aos personaxes certas. E entón os personaxes que teñen máis frecuencia vai ser representado con menor número de bits. 

O xeito que construír unha árbore de Huffman é a colocación de todos os personaxes que aparecen no texto e calcular a súa frecuencia, cantas veces aparecen. Isto podería ser unha conta de cantas veces as letras aparecen ou quizais unha porcentaxe de fóra de todos os personaxes cantos cada un aparece. E entón o que fai é cando ten todo isto para fóra mapeado, entón mira para as dúas frecuencias máis baixas e despois Xunta-los como irmáns onde, entón, o nodo pai ten unha frecuencia que é a suma dos seus dous fillos. E entón por convención dicir que o nodo esquerdo, vostede segue que, seguindo a rama 0, e despois o nó máis á dereita é a rama 1. Como vimos en código Morse, o único pegadinha é que, se tivese só un bip e bip era ambigua. Podería ser unha letra ou pode ser unha secuencia de dúas letras. E entón o que Huffman árbores fai é porque, por natureza dos personaxes ou finais nosos personaxes reais, sendo os nos últimos no sector - nos referimos aos que como as follas - en virtude de que non pode haber ningún ambigüidade en termos de que a letra que está intentando codificar coa serie de bits porque en ningún lugar ao longo dos bits que representan unha carta vai atopar outra carta enteira, e non haberá ningunha confusión alí. Pero imos entrar en exemplos que vostedes poden realmente ver que en vez de simplemente dicindo que iso é verdade. 

Vexamos un exemplo simple de unha árbore de Huffman. Eu teño unha secuencia aquí que é de 12 carácteres. Eu teño 4 Como, 6 BS, Cs e 2. O meu primeiro paso sería contar. Cantas veces é que unha opinión? Aparece catro veces na secuencia. B aparece 6 veces, e C é exhibida dúas veces. Por suposto, eu vou dicir que estou usando B na maioría das veces, así que quero representar B con menor número de bits, o menor número de 0s e 1s. E entón eu tamén vou esperar C para esixir a maior cantidade de 0s e 1s tamén. Primeiro o que eu fixen aquí é que eu colocaba en orde crecente en termos de frecuencia. Vemos que o C e A, esas son as nosas dúas frecuencias máis baixas. Creamos un nó pai, e que o nodo pai non ten unha carta a ela asociados, pero ten unha frecuencia, que é a suma. A suma torna-se 2 + 4, o cal é 6. Entón, seguimos a rama esquerda. Se estivésemos naquel no 6, entón poderiamos seguir 0 para chegar a C e, a continuación, 1 para a A. Polo tanto, agora temos dous nós. Temos o valor 6 e despois tamén temos outro no co valor 6. E así os dous non son só o menor 2, pero tamén a só 2 que sobraron, para que unirse aos que por outro pai, coa suma sendo 12. Polo tanto, temos aquí a nosa árbore de Huffman onde para chegar a B, que sería só o bit 1 e, a continuación, para chegar a un teriamos 01 e, a continuación, C con 00. Entón aquí vemos que, basicamente, estamos representando estes chars con 1 ou 2 bits en que a B, como previsto, ten polo menos. E entón esperabamos C para ter máis, pero xa que é tal unha árbore de Huffman pequeno, entón o A é tamén representada por 2 bits en lugar de algures no medio. 

Só para pasar por riba de outro exemplo simple da árbore de Huffman, dicir que ten a cadea "Ola". O que é primeiro diría cantas veces H aparecer nesta? H aparece unha vez e logo e aparece unha vez e entón temos l aparecendo dúas veces é a aparición vez. E entón esperamos que carta a ser representado polo menor número de bits? [Alumno] l. L. >> Si l é correcto. Esperamos l ser representado por polo menos o número de bits porque eu se usa máis na cadea "Ola". O que eu vou facer agora é aproveitar eses nós. I ter 1, que é H, e, a continuación, outro 1, que é a e, a continuación, un 1, que é o - agora eu estou poñendo-os en orde - e, a continuación, 2, que é l. Entón eu digo o xeito que eu construír unha árbore de Huffman é atopar os dous nós coas menores frecuencias e sexa los irmáns creando un nodo pai. Aquí temos tres nós coa menor frecuencia. Son todos un. Entón aquí nós escoller cal imos chamar primeiro. Imos dicir que eu escoller o H e e. A suma de 1 + 1 e 2, pero este nó non ten unha carta a ela asociados. El só ten o valor. Agora imos ollar para os próximos 2 frecuencias máis baixas. Isto é 2 e 1. Isto podería ser un deses dous, pero eu vou escoller un regalo. A suma é 3. E entón, finalmente, eu só teño 2 esquerda, de modo que se fai entón 5. Entón, aquí, como esperaba, se eu encher a codificación para que, 1s son sempre o brazo dereito e 0s son a esquerda. Entón temos l representadas por só un pouco e despois o por 2 e, a continuación, o correo por 2 e, a continuación, o H cae 3 bits. Entón pode transmitir esta mensaxe "Ola" en vez de realmente usando os personaxes por só 0s e 1s. Con todo, lembre que en varios casos que lazos coa nosa frecuencia. Poderiamos ter ou xuntou o H e O primeiro quizais. Ou, máis tarde, cando tivemos a l representada por 2 así como a que se xuntou un representado por 2, pódese ter ligado un ou outro. 

E así, cando envía os 0s e 1s, que en realidade non garante que o destinatario pode enteiramente ler a súa mensaxe pronto de cara porque poden non saber que a decisión que fixo. Entón, cando estamos lidando con compresión Huffman, de algunha maneira, debemos dicir o destinatario da nosa mensaxe como decidimos - Eles precisan saber algún tipo de información adicional ademais da mensaxe comprimida. Eles necesitan entender o que a árbore realmente parece, como realmente fixo estas decisións. 

Aquí foron só facendo exemplos baseados na conta real, pero ás veces pode ter tamén unha árbore de Huffman con base na frecuencia en que as letras aparecen, e é exactamente o mesmo proceso. Aquí estou expresando a en termos de porcentaxes ou fracción, e por iso aquí exactamente a mesma cousa. Creo menor 2, suma-los, o 2 menor seguinte suma-los, ata eu ter unha árbore chea. Aínda que puidésemos facelo de calquera xeito, cando estamos lidando con porcentaxes, iso significa que estamos dividindo as cousas e xestionar decimais ou mellor, flutúa se estamos a pensar en estruturas de datos dunha cabeza. O que sabemos sobre coches alegóricos? ¿Que é un problema común cando estamos lidando con coches alegóricos? [Alumno] aritmética imprecisa. Si >>. Imprecisión. Por mor da imprecisión de punto flotante, a este pset para que comprobe se que non perdemos ningún valor, entón estamos realmente vai ser xestione o contador. Entón, se pensar en un nó Huffman, se ollar cara atrás, a estrutura aquí, Se ollar para os verdes que ten unha frecuencia asociada a el así como el apunta a un nodo polo seu lado esquerdo, así como un nó á dereita. E, a continuación, as pinturas teñen tamén un carácter que lles están asociados. Non imos facer os separados para os pais e, a continuación, os nodos finais, a que nos referimos como as follas, senón aqueles que só teñen valores nulos. Para cada nodo teremos un personaxe, o símbolo que representa ese nodo, a continuación, a frecuencia, así como un indicador para o seu fillo esquerdo, así como a súa neno dereita. As follas, que son ben no fondo, tamén tería punteiros nodo á súa esquerda e á súa dereita, pero sempre que estes valores non están apuntando para nós reais, o que sería o seu valor ser? >> [Alumno] NULL. NULL. >> Exactamente. Aquí está un exemplo de como pode representar a miúdo en coches alegóricos, pero imos estar lidando con iso con números enteiros, entón todo o que eu fixen é cambiar o tipo de datos alí. 

Imos a un pouco máis de un exemplo complexo. Pero agora que temos feito as máis simples, é só o mesmo proceso. Vostede está as dúas frecuencias máis baixas, sumar as frecuencias e esa é a nova frecuencia do seu nodo pai que, entón, apunta a súa esquerda co ramo do dereito 0 e co sector 1. Se temos a cadea "Este é CS50," entón nós contar cantas veces é mencionado T, h mencionado, i, s, c, 5, 0. Entón o que eu fixen aquí é os nós vermellos eu só plantas, Eu dixen que eu vou ter eses personaxes, eventualmente, na parte inferior da miña árbore. Aqueles van ser todas as follas. Entón o que eu fixen é que eu clasificados los pola frecuencia en orde crecente, e esta é realmente a forma que o código fai pset é el clasifica-lo por frecuencia e, a continuación, en orde alfabética. Por iso, ten os números primeiro e logo en orde alfabética polo miúdo. Entón o que me gustaría facer é que eu ía atopar a menor 2. Isto é 0 e 5. Quere suma-los, e iso é 2. Entón quere continuar, o seguinte 2 menor. Estes son os 1s dous, e, a continuación, os dous se fan tamén. Agora sei que o meu seguinte paso será engadir o menor número, Que é o T, 1, e en seguida, selecciona un dos nós que ten 2 como a miúdo. Polo tanto, temos aquí tres opcións. O que eu vou facer a foto é só visualmente reorganiza-los para ti de xeito que se pode ver como eu estou construíndo-o. O que o código eo código de distribución vai facer sería xuntar a unha T co nodo 0 e 5. Entón que resume a 3, e entón continuar o proceso. O 2 a 2 e agora son os máis baixos, de xeito entón aqueles suma a 4. Todos seguindo ata agora? Okay. A continuación, despois de que temos a 3 e 3 que necesitan ser engadidos, así outra vez eu estou só liga-lo de modo que pode ver visualmente, de forma que non quede moi confuso. Entón temos un 6, e entón o noso paso final é agora cando temos só 2 nós sumamos os para facer a base da nosa árbore, que é 10. E o número 10 ten sentido, porque cada nodo representado, o seu valor, o seu número de frecuencia, era cantas veces eles apareceron na secuencia, e entón temos 5 personaxes na nosa cadea, de xeito que ten sentido. Se ollar para coma nós, en realidade, codifica-lo, como esperaba, o I eo s, que aparecen con máis frecuencia son representados polo número mínimo de bits. 

Teña coidado aquí. En árbores Huffman caso realmente importa. Un S maiúsculo é distinto de un s minúsculo. Se tivésemos "Este é CS50" con letras maiúsculas, o s minúsculo só aparecen dúas veces, Sería un nó con 2 como o seu valor e, a continuación, S maiúsculo sería só unha vez. Entón a súa árbore cambiaría as estruturas, porque realmente ten unha folla extra aquí. Pero a suma aínda sería 10. Isto é o que estamos realmente vai ser chamar o checksum, a adición de todas as contas. 

Agora que nós Cubrimos árbores Huffman, podemos mergullar en Huff'n Puff, o pset. Nós imos comezar con unha sección de preguntas, e iso vai leva-lo acostumado con árbores binarias e como operar en torno a que: Nós deseño, creando a súa propia estrutura typedef a un nodo, e ver como pode inserir nunha árbore binaria, un que está clasificado, atravesando, e cousas así. Este coñecemento é sempre vai axudar cando mergulla na porción Puff Huff'n do pset. Na edición estándar do pset, a súa tarefa é aplicar Puff, e na versión pirata súa tarefa é aplicar Huff. O Huff fai é que leva o texto e entón o traduce para os 0s e 1s, así o proceso que fixemos anteriormente, onde contamos as frecuencias e en seguida, fixo a árbore e, a continuación, dixo: "Como podo obter T?" T é representado por 100, cousas así, Huff e despois levaría o texto e, a continuación, saída que binario. Pero tamén porque sabemos que queremos facer que o noso destinatario da mensaxe para recrear a mesma árbore que, tamén inclúe información sobre as contas de frecuencia. Entón, con Puff nos é dado un arquivo binario de 0s e 1s e atendendo tamén á información sobre as frecuencias. Traducimos todo 0s e 1s de volta para a mensaxe orixinal que foi, por iso estamos descompactando iso. Se está facendo a edición estándar, non aplicar Huff, , Entón podes simplemente usar a aplicación equipo de Huff. Hai instrucións na especificación de como facelo. Pode realizar a implementación equipo de Huff enriba dun arquivo de texto certa e despois usar esta saída como a súa entrada para Puff. 

Cómo mencionen antes, temos unha morea de código de distribución a este. Vou comezar a pasar por iso. Vou pasar a maior parte do tempo no. Arquivos h porque nos arquivos. c, porque temos o h. e que nos ofrece os prototipos de funcións, non é totalmente precisa entender exactamente - Se non entende o que está a suceder nos arquivos. C, entón non se preocupe moito, pero sempre tentar dar un ollo porque pode dar algúns consellos e é útil para acostumar lectura de código de outras persoas. 

Mirando huffile.h, nos comentarios que declara unha capa de abstracción para Huffman codificados arquivos. Se descermos, vemos que hai un máximo de 256 símbolos que podemos ter códigos para. Isto inclúe todas as letras do alfabeto - maiúsculas e minúsculas - e, a continuación, os símbolos e números, etc Entón aquí temos un número máxico identificar un ficheiro Huffman-codificado. Dentro dun código de Huffman eles van ter un número de certa maxia asociados a cabeceira. Isto pode parecer só un número máxico ao chou, pero se realmente traducir-lo en ASCII, entón realmente explicita Huff. Aquí temos unha estrutura para un ficheiro Huffman-codificado. Hai todas estas características asociadas cun ficheiro de Huff. Entón aquí temos a cabeceira dun arquivo de Huff, por iso nós dicimos que Huffeader en vez de engadir o h extra porque parece o mesmo de calquera maneira. Bonito. Temos un número máxico asociado a el. Se é un ficheiro de Huff real, que vai ser o número anterior, esta maxia. E entón el vai ter unha matriz. Así, para cada símbolo, dos cales existen 256, vai incluír o que a frecuencia destes símbolos están dentro do ficheiro de Huff. E entón, finalmente, temos unha suma de verificación para as frecuencias, cal debe ser a suma destas frecuencias. Entón é iso que un Huffeader é. Entón, temos algunhas funcións que retornan ao seguinte bit no arquivo Huff así como escribe algo para o ficheiro de Huff, e entón esta función aquí, hfclose, que realmente pecha o ficheiro Huff. Antes, estabamos lidando con recta só fclose, pero cando ten un arquivo de Huff, en vez de fclosing o que en realidade está indo facer é hfclose e hfopen-lo. Esas son funcións específicas para os ficheiros de Huff que imos tratar. Entón aquí nós lemos na cabeceira e logo escribir a cabeceira. 

Só lendo o. Arquivo h podemos tipo de obter unha noción do que un arquivo pode ser Huff, cales as características que ten, sen realmente ir ao huffile.c, que, se mergullar, vai ser un pouco máis complexa. El ten todo o arquivo I / O lidando aquí con punteiros. Aquí vemos que cando chamamos hfread, por exemplo, que aínda está lidando con fread. Non vai se librar destas funcións totalmente, pero estamos enviando as medidas a tomar conta de dentro do arquivo Huff en vez de facer todo nós mesmos. Pode sentirse libre para facer a pescudas a través deste se está curioso e ir descascada a capa de volta un pouco. 

O seguinte ficheiro que imos ollar é tree.h. Antes do paso a paso desliza dixemos que esperar un nodo Huffman e fixemos un nó typedef struct. Esperamos que ten un símbolo, unha frecuencia, e despois dúas estrelas no. Neste caso, o que estamos facendo é que este é esencialmente o mesmo excepto en vez de nodo imos chamalos de árbores. Temos unha función que cando chamar facer árbore que retorna un punteiro de árbore. Volver Speller, cando estaba facendo un novo nodo vostede dixo no palabra * novo = malloc (sizeof) e cousas así. Basicamente, mktree vai ser tratar con isto para ti. Do mesmo xeito, cando quere eliminar unha árbore, de xeito que é esencialmente liberar a árbore cando rematar con el, en vez de chamar explicitamente libre en que, en realidade está indo só para usar a función rmtree onde pasar o punteiro para a árbore e, a continuación, tree.c vai coidar diso para ti. 

Miramos para tree.c. Agardamos que as mesmas funcións, excepto para ver a execución tamén. Como esperabamos, cando chamalo mktree mallocs do tamaño dunha árbore nun punteiro, arrincar todos os valores para o valor NULL, así 0s ou nulos, e retorna o punteiro para a árbore que acaba de malloc'd para ti. Aquí cando chamar eliminar árbore primeiro asegura que non está liberando dobre. El asegura que realmente ten unha árbore que quere eliminar. Aquí porque unha árbore tamén inclúe os seus fillos, O que isto significa é que chama recursivamente eliminar árbore no nodo esquerdo da árbore así como o nó dereito. Antes que libera o pai, precisa liberar os fillos tamén. Pai tamén é intercambiable con raíz. O primeiro pai nunca, así como o gran-gran-gran-gran-avó ou árbore avoa, primeiro temos que liberarse os primeiros niveis. Entón, atravesar para o fondo, sen aqueles, e en seguida, volver-se, libre daqueles, etc Entón, iso é árbore. 

Agora imos ollar para bosque. Bosque é onde se pon todas as súas árbores de Huffman. Está dicindo que nós imos ter unha cousa chamada trama que contén un enlace a unha árbore, así como un indicador para unha trama chamada seguinte. Que estrutura fai este tipo de ollar como? É o tipo de di por aí. Ben aquí. Unha lista ligada. Vemos que, cando temos unha trama que é como unha lista ligada de parcelas. O bosque é definida como unha lista ligada de parcelas, e así a estrutura do bosque é que estamos indo só para ter un punteiro para o noso primeiro lote e que a trama ten unha árbore dentro del, ou mellor apunta a unha árbore e, a continuación, apunta para o lote seguinte, así por diante e así por diante. Para facer un bosque que chamamos mkforest. Entón, temos algunhas funcións moi útiles aquí. Temos escoller onde pasa nun bosque e, a continuación, o valor de retorno é un * Árbore, un punteiro para unha árbore. O que vai facer é escoller vai para o bosque que está a apuntar cara a continuación, eliminar unha árbore coa menor frecuencia que o bosque e despois darlle o punteiro para esa árbore. Unha vez que chama a elixir, a árbore non vai existir no bosque máis, pero o valor de retorno é o punteiro para a árbore. Entón tes planta. Dende que pasar un punteiro para unha árbore que ten unha frecuencia non-0, que planta vai facer é que vai levar o bosque, tomar a árbore, e planta que árbore dentro do bosque. Aquí temos rmforest. Similar para eliminar árbore, que, basicamente, liberou todos os nosos árbores para nós, eliminar bosque vai todo libre contida no bosque. 

Se olharmos para forest.c, imos esperar a ver polo menos un comando rmtree alí, porque a memoria libre no bosque unha bosque ten árbores que, despois, eventualmente, vai ter que eliminar as árbores tamén. Se olharmos para forest.c, temos a nosa mkforest, que é como esperamos. Nós malloc cousas. Nós arrincar a primeira parcela no bosque coma NULL porque está baleiro, para comezar, entón vemos cabeza, que retorna a árbore co menor peso, menor frecuencia, e entón se librar dese nó especial que apunta a que a árbore eo próximo, por iso é preciso que fóra da lista ligada do bosque. E entón aquí temos planta, que introduce unha árbore á lista ligada. O que mata non é así mantén clasificados para nós. E, a continuación, finalmente, temos rmforest e, como esperaba, temos chamado rmtree alí. 

Mirando cara o código de distribución, ata agora, huffile.c foi probablemente, de lonxe, o máis difícil de entender, mentres que os outros arquivos en si eran ben sinxelo de seguir. Co noso coñecemento de punteiros e listas ligadas e tal, fomos capaces de seguir moi ben. Pero todo o que necesitamos para realmente estar seguro de que entendemos plenamente. Son os arquivos h porque ten que estar chamando estas funcións, xestionar eses valores de retorno, para asegurarse que entendeu o que a acción vai ser realizada sempre que chamar a unha desas funcións. Pero, en realidade, a comprensión dentro do que non é absolutamente necesario, porque temos os. Arquivos h. Temos dous arquivos deixados no noso código de distribución. 

Imos ollar para despejo. Despejo polo seu comentario aquí leva un ficheiro Huffman-comprimido e, a continuación, traduce e depósitos de todo o seu contido para fóra. Aquí vemos que está chamando hfopen. Esta é unha especie de espelhamento para o ficheiro de entrada * = fopen, e entón pasa a información. É case idéntico, excepto en vez de un * ficheiro que está pasando nun Huffile; en vez de fopen está pasando en hfopen. Aquí lemos na cabeceira da primeira, que é unha especie de similar a como se le na cabeceira para un ficheiro bitmap. O que estamos facendo aquí é comprobar a ver se a información de cabeceira contén o número máxico dereito que indica que é un ficheiro de Huff real, a continuación, todas estas comprobacións para asegurarse de que o arquivo que está aberto un arquivo real xingou ou non. O que isto significa que xera as frecuencias de todos os símbolos que podemos ver dentro dun terminal para unha táboa gráfica. Esta parte vai ser útil. El ten un pouco e le pouco a pouco a pouco variable e imprime o. Entón, se eu fose chamar despejo en hth.bin, que é o resultado dun ficheiro huffing utilizando a solución persoal, quere obter isto. É a saída de todos eses personaxes e despois poñer a miúdo en que aparecen. Se miramos, a maioría deles son 0s excepto para iso: H, que aparece dúas veces, T e, a continuación, unha vez que aparece. E aquí temos a verdadeira mensaxe 0s e 1s. Se olharmos para hth.txt, que é probablemente a mensaxe orixinal que foi bufou, Esperamos ver algúns hs e Ts alí. Especificamente, esperamos ver só 1 T e 2 hs. Aquí estamos hth.txt. De feito, ten HTH. Incluído, aínda que non poidamos velo, é un carácter de nova liña. O hth.bin arquivo Huff tamén é a codificación de caracteres de nova liña tamén. Aquí porque sabemos que a orde é HTH e despois de nova liña, podemos ver que, probablemente, o H é representado por só un único 1 e, a continuación, o T é probablemente 01 e, a continuación, o seguinte é un H, así e entón temos unha nova liña indicada por dous 0s. Cool. 

E entón, finalmente, arquivos, porque estamos lidando con múltiples. C e. H, nós imos ter un argumento moi complexo para o compilador, e aquí temos un Makefile que fai despejo para ti. Pero, en realidade, ten que ir sobre como facer o seu propio arquivo puff.c. O Makefile en realidade, non se trata de facer puff.c para ti. Estamos deixando isto para vostede editar o Makefile. Cando escribe unha orde como facer todo, por exemplo, que vai facer todos eles para ti. Sinto-se libre para ollar os exemplos de Makefile das pset pasado así como saír dun agasallo para ver como pode ser capaz de facer o seu arquivo Puff editando este Makefile. É sobre iso para o noso código de distribución. 

Unha vez que temos obtido a través diso, entón aquí é só un recordatorio de como imos estar lidando cos nós Huffman. Non imos estar chamando-os de nós máis, nós imos estar chamando-os de árbores onde imos estar representando o seu símbolo cun char, a súa frecuencia, o número de ocorrencias, con un número enteiro. Estamos a usar iso porque é máis preciso que un coche alegórico. E entón temos outro punteiro para o fillo esquerdo, así como o dereito do neno. Un bosque, como vimos, é só unha lista encadeada de árbores. Por fin, cando estamos construíndo o noso arquivo Huff, queremos que a nosa bosque para conter unha árbore 1 - Unha árbore, unha raíz con varios fillos. A principios de cando estabamos facendo as nosas árbores de Huffman, comezamos por poñer todos os nós na nosa pantalla e dicindo que nós imos ter eses nós, finalmente, eles van ser as follas, e este é o seu símbolo, esta é a súa frecuencia. Na nosa bosque só temos 3 letras, que é un bosque de tres árbores. E entón, como imos, cando engadimos o primeiro pai, fixemos un bosque de dúas árbores. Nós eliminamos 2 dos nenos da nosa bosque e, a continuación, substitúe-lo con un nó pai que eses dous nós como fillos. E entón, finalmente, o noso último paso con facer o noso exemplo, o As, Bs e Cs sería facer o proxenitor final, e así, entón, que ía traer a nosa conta total de árbores no bosque para 1. Será que todo o mundo ver como comeza con varias árbores na súa bosque e acabar con un? Okay. Cool. 

O que necesitamos facer para Puff? O que necesitamos facer é garantir que, como sempre, eles nos dan o dereito tipo de entrada para que poidamos realmente executar o programa. Neste caso, eles van estar dando-nos logo do seu argumento de liña de comandos primeiro 2 máis: o ficheiro que queremos descomprimir e saída do ficheiro descomprimido. Pero unha vez que temos a certeza de que eles pasan connosco a cantidade correcta de valores, queremos garantir que a entrada é un ficheiro Huff ou non. E entón, xa que asegura que é un arquivo de Huff, entón nós queremos construír a nosa árbore, construír a árbore de tal forma que corresponda a árbore que a persoa que enviou a mensaxe construída. A continuación, despois de construír a árbore, entón podemos manexar o, 0s e 1s que pasaron en seguir os ao longo da nosa árbore porque é idéntico, e logo escribir esta mensaxe, interpretar os bits de volta para chars. E entón, ao final, porque estamos lidando con punteiros aquí, queremos estar seguro de que non temos ningunha derrames de memoria e que todo libre. 

Garantir o uso axeitado é vello sombreiro para nós agora. Nós levamos unha entrada, que vai ser o nome do ficheiro a golpe, e, entón, indicar unha saída, de xeito que o nome do ficheiro de saída para o tufado, que será o ficheiro de texto. Isto é uso. E agora queremos garantir que a entrada é xingou ou non. Pensando ben, estaba alí nada no código de distribución que nos pode axudar a coa comprensión un ficheiro xingou ou non? Houbo información sobre o huffile.c Huffeader. Sabemos que cada ficheiro ten un Huff Huffeader asociada cun número máxico , Así como unha matriz de as frecuencias para cada símbolo , Así como unha suma de verificación. Nós sabemos diso, pero nós tamén levou un ollo a dump.c, no que se le nun arquivo Huff. E así, para facelo, tiña que comprobar que realmente foi xingou ou non. Entón, talvez puidésemos utilizar dump.c como unha estrutura para o noso puff.c. Volver pset 4, cando tivemos a copy.c arquivo que copiou no triplica RGB e Interpreta que para Whodunit e redimensionar, Do mesmo xeito, o que podería facer é executar o comando como cp dump.c puff.c e utilizar parte do código alí. Con todo, non vai ser tan sinxelo dun proceso para traducir o seu dump.c en puff.c, pero polo menos el dálle un lugar para comezar sobre a forma de garantir que a entrada é efectivamente ou non bufou así como algunhas outras cousas. Temos asegurado o uso adecuado e asegurou que a entrada é bufou. Cada vez que fixemos o que fixemos nosa comprobación de erros adecuada, para volver e pechar a función algunha falla ocorre, se hai un problema. 

Agora, o que queremos facer é construír a árbore real. Se miramos en Bosque, hai dúas principais funcións que imos querer facer-se moi familiarizado. Hai a planta función booleana que planta unha árbore de frecuencia non-0 dentro da nosa bosque. E así, alí pasar un punteiro para un bosque e un punteiro para unha árbore. Pregunta rápida: Cantos bosques que ten cando está construíndo unha árbore de Huffman? A nosa bosque é como a nosa pantalla, non? Entón, nós estamos indo só para ter un bosque, pero imos ter varias árbores. Entón, antes de chamar planta, está probablemente vai querer facer a súa bosque. Hai un comando para que, se ollar para forest.h de como pode facer un bosque. Pode plantar unha árbore. Nós sabemos como facelo. E entón tamén pode escoller unha árbore do bosque, eliminación dunha árbore co menor peso e dándolle o punteiro para iso. Pensando cando estabamos facendo os exemplos de nós mesmos, cando estabamos deseñando-o para fora, nós simplemente acaba de engadir as ligazóns. Pero aquí, no canto de só engadir as ligazóns, pensar máis como está eliminando dous deses nós e, a continuación, substituílo por outro. Para expresar iso en termos de colleita e cultivo, está escollendo dúas árbores e plantas outra árbore que esas dúas árbores que escolleu como nenos. Para construír árbore de Huffman, podes ler os símbolos e frecuencias en orde porque o que Huffeader dá para ti, dálle un conxunto de frecuencias. Entón pode ir adiante e simplemente ignorar calquera cousa con a 0 nel porque non queremos 256 follas ao final do mesmo. Nós só queremos o número de follas que son personaxes que son realmente utilizados no ficheiro. Podes ler neses símbolos, e cada un deses símbolos que frecuencias non-0, aqueles van ser árbores. O que podes facer é cada vez que ler un símbolo de frecuencias non-0, pode plantar a árbore no bosque. Despois de plantar as árbores no bosque, pode xuntarse esas árbores como irmáns, Entón, volvendo ao cultivo e escoller onde escolle 2 e despois planta 1, onde que unha planta que é o pai dos dous nenos que escolleu. Entón o resultado final vai ser unha única árbore no bosque. É como construír a súa árbore. 

Hai moitas cousas que poden dar mal aquí porque estamos lidando con facer novas árbores e xestionar punteiros e cousas así. Antes, cando estabamos lidando con punteiros, sempre que malloc'd nós queriamos estar seguro de que non nos devolver un valor de punteiro NULL. Entón, en varios pasos dentro deste proceso non van ser varios casos onde o programa podería fallar. O que quere facer é que quere estar seguro de que trata sobre estes erros, e na especificación di para seguro-los graciosamente, así como imprimir unha mensaxe para o usuario dicíndolles por iso que o programa ten para saír e entón rapidamente saír dela. Para iso o tratamento de erros, lembre que quere comprobar se cada vez que pode haber unha falla. Cada vez que está facendo un novo punteiro quere estar seguro de que iso é éxito. Antes de que estamos afeitos a facer é facer un novo punteiro e malloc-lo, e entón nós comprobar que ese punteiro é NULL. Polo tanto, non van ser algúns casos en que só se pode facer iso, pero ás veces realmente está chamando dunha función e dentro desta función, que é a única que está facendo a mallocing. Nese caso, se miramos para algunhas das funcións dentro do código, algúns deles son funcións booleanas. No caso abstracto, se temos unha función booleana chamada foo, Basicamente, podemos supoñer que, ademais de facer o que fai foo, xa que é unha función booleana, el retorna verdadeiro ou falso - certo caso de éxito, falso se non. Entón, queremos asegurarse de que o valor de retorno de foo é verdadeira ou falsa. Se é falso, o que significa que nós imos querer imprimir algún tipo de mensaxe e pecha o programa. O que queremos facer é comprobar o valor de retorno de foo. Se foo retorna falso, entón sabemos que atopamos algún tipo de erro e necesitamos deixar de noso programa. Unha forma de facelo é ter unha condición onde a función en si é a súa condición. Diga foo leva en x. Podemos ter como condición if (foo (x)). Basicamente, isto significa que a finais de execución de foo el retorna true, entón podemos facelo porque a función ten que avaliar foo , A fin de avaliar a condición xeral. Entón é así que pode facer algo, a función volverá certo e é ben sucedido. Pero cando se está a comprobación de erros, só quere saír a súa función devolve falso. O que podería facer é só engadir un == false ou só engadir un estrondo na fronte del e entón tes if (! foo). Dentro dese corpo que condición tería todo o tratamento de erros, así como, "Non se puido crear esta árbore" e, a continuación, voltar 1 ou algo así. O que fai, porén, é que aínda que foo retornou falso - Diga foo retorna true. Entón non tes que chamar foo novo. Isto é un equívoco común. Porque estaba na súa condición, el xa está valorado, Entón xa tes o resultado, se está a usar facer árbore ou algo así ou planta ou cabeza ou algo así. Ela xa ten ese valor. El xa está executado. Por iso, é útil usar funcións booleanas como condición porque se está ou non realmente facer o corpo do loop, el executa a función de calquera maneira. 

O noso segundo a última etapa é escribir a mensaxe ao ficheiro. Unha vez que imos construír a árbore de Huffman, a continuación, escriba a mensaxe para o arquivo é moi sinxelo. É moi sinxelo agora só seguir os 0s e 1s. E así por convención, sabemos que nunha árbore Huffman os 0s indican que deixaron e os 1s indican correcto. Entón, se ler aos poucos, cada vez que recibir un 0 vai seguir o sector da esquerda, e despois cada vez que ler un 1 vai seguir a rama dereita. E entón vai continuar ata que bata unha folla porque as follas van ser a finais dos ramos. Como podemos dicir se se loita dunha folla ou non? Nós dixemos que antes. [Alumno] Se os punteiros son NULL. Si >>. Podemos dicir se se loita dunha folla os punteiros para árbores, tanto a esquerda e dereita son NULL. Perfecto. Sabemos que queremos ler aos poucos no noso arquivo Huff. Como vimos antes, en dump.c, o que eles fixeron é que len aos poucos para o arquivo Huff e só impresos que eses fragmentos eran. Non imos estar facendo iso. Estamos indo facer algo que é un pouco máis complexa. Pero o que podemos facer é que podemos tomar aquel anaco de código que le a bit. Aquí temos o bit enteiro que representa o bit actual que estamos no. Este coida de iteração todos os bits no ficheiro ata chegar ao final do arquivo. Con base niso, entón vai querer ter algún tipo de iterador para atravesar a súa árbore. E, a continuación, con base en que o bit é 0 ou 1, vai querer quere mover este iterador á esquerda ou movelo a dereita todo o camiño ata que bata unha folla, así todo o camiño ata ese nó que está en non ligan con nós nada máis. Por que podemos facelo cun ficheiro Huffman pero non o código Morse? Porque no código Morse hai un pouco de ambigüidade. Nós poderiamos ser como, oh wait, se loita unha carta ao longo do camiño, quizais por iso esta é a nosa carta, mentres que, se seguimos un pouco máis, entón tería atinxido outra carta. Pero iso non vai ocorrer en codificación de Huffman, para que poidamos estar seguro de que a única forma que nós imos bater un personaxe é se os nenos esquerdo e dereito que son NULL. 

Finalmente, queremos liberar toda a nosa memoria. Queremos ambos preto o arquivo Huff que estamos lidando con así como eliminar todas as árbores na nosa selva. Con base na súa implementación, probablemente vai querer chamar eliminar bosque en vez de realmente pasar por todas as árbores de si mesmo. Pero se fixo todas as árbores temporais, vai querer liberar isto. Vostede sabe o seu código de mellor, para que vostede sabe onde está alocando memoria. E por iso, se vostede poñerse, comezar por ata controlar f'ing para malloc, vendo sempre que malloc e asegurarse de que liberar de todo isto pero entón só pasando polo seu código, entender onde pode ter asignado memoria. Normalmente pode só dicir: "A finais de un arquivo que eu estou indo só para eliminar bosque na miña selva", Entón, basicamente claro que a memoria libre, que, "E entón eu tamén estou indo para pechar o ficheiro e entón o meu programa vai saír." Pero é que a única vez que o programa é pechado? Non, porque, ás veces, pode haber un erro que pasou. Quizais a xente non pode abrir un arquivo ou non poderíamos facer outra árbore ou algún tipo de erro ocorreu no proceso de asignación de memoria e por iso volveu NULL. Un erro ocorreu e, despois, devolto e saia. Entón quere estar seguro de que en calquera momento pode que o seu programa pode saír, quere liberar toda a súa memoria alí. Non só vai ser ao final da función principal que saia do seu código. Quere mirar para atrás cada instancia que o seu código potencialmente pode devolver prematuramente e memoria calquera libre ten sentido. Digamos que chamara facer bosque e que retornou falso. Entón probablemente non vai ter eliminar o bosque porque non ten un bosque aínda. Pero en todos os puntos do código onde podes voltar prematuramente quere ter seguro de que liberar calquera memoria posible. 

Entón, cando estamos lidando con liberar memoria e ter vazamentos potenciais, queremos non só usar o noso xuízo eo noso lóxica pero tamén usar Valgrind para determinar se nós liberou toda a nosa memoria correctamente ou non. Pode realizar Valgrind en Puff e entón tamén ten que pasalo o número correcto de liña de comandos argumentos para Valgrind. Pode realizar tanto, pero a saída é un pouco enigmática. Temos tido un pouco acostumado con Speller, pero aínda necesitamos de axuda un pouco máis, así entón executa-lo con algunhas bandeiras, como o baleirado de máis-check = full, que probablemente vai dar algunha saída máis útil en Valgrind. 

A continuación, outra información útil cando está depurar é o comando diff. Pode acceder a implementación do persoal de Huff, que executar un arquivo de texto, e despois a saída a un ficheiro binario, un arquivo binario Huff, para ser específico. Entón, se executar o seu propio vento en que o ficheiro binario, a continuación, idealmente, o seu arquivo de texto outputted será idéntico ao orixinal que pasou dentro Aquí estou usando hth.txt como exemplo, e iso é o que falou na súa especificación. Iso é literalmente só HTH e entón unha nova liña. Pero, en definitiva, sentirse libre e está sempre animou a utilizar exemplos máis para o seu arquivo de texto. 

Podes incluso levar un tiro na cadra comprimir e despois descomprimir algúns dos arquivos que usou na Speller como Guerra e Paz ou Jane Austen, ou algo así - o que sería ben legal - ou Austin Powers, tipo de manexar arquivos maiores porque non teriamos chegado ata el se usan a ferramenta seguinte aquí, ls-l. Estamos acostumados a ls, que lista todos basicamente o contido no noso directorio actual. Pasando o sinalizador-l realmente mostra o tamaño dos arquivos. Se pasar por a especificación pset, realmente percorre a creación do ficheiro binario, de huffing-lo, e ve que a arquivos moi pequenos o custo do espazo de comprimi-lo e traducir toda esa información de todas as frecuencias e cousas así supera o beneficio real de comprimir o ficheiro primeiro. Pero se executa-lo en algúns arquivos de texto máis longos, entón podes ver que comeza a ter algún beneficio en comprimir os arquivos. 

E entón, finalmente, temos o noso GDB vello amigo, que, certamente, vai vir a cadra tamén. 

Non temos ningunha dúbida en árbores Huff ou o proceso pode facer as árbores ou calquera outras preguntas sobre Puff Huff'n? Okay. Eu vou ir en torno a un bit. 

Grazas a todos. Este foi Walkthrough 6. , E boa sorte. 

[CS50.TV]