[Powered by Google Translate] [Tutorial - Boletín de problemas 6] [Zamyla Chan - Harvard University] [Esta es CS50. - CS50.TV] 

Hola a todos y bienvenidos a Tutorial 6: Puff Huff'n. En Puff Huff'n lo que estamos haciendo va a estar tratando con un archivo comprimido Huffman y luego soplar una copia de seguridad, por lo que la descompresión, por lo que podemos traducir de el 0 y 1 que el usuario nos envía y convertir de nuevo en el texto original. Pset 6 va a ser muy bueno porque vas a ver algunas de las herramientas que utilizó en el conjunto de procesadores 4 y 5 y el conjunto de procesadores tipo de combinación en un concepto bastante limpio cuando se llega a pensar en ello. 

También, sin duda, pset 4 y 5 fueron los conjuntos de procesadores más difíciles que hemos tenido que ofrecer. Así que a partir de ahora, tenemos este conjunto de procesadores 1 más en C, y después de eso estamos en la programación web. Así que os felicito por conseguir sobre la chepa más dura en CS50. 

Pasando por Puff Huff'n, nuestra caja de herramientas para este conjunto de procesadores van a ser árboles de Huffman, por lo que entender no sólo cómo funcionan los árboles binarios, sino también específicamente árboles Huffman, cómo están construidos. Y entonces vamos a tener una gran cantidad de código distribución en este conjunto de procesadores, y vamos a llegar a ver que en realidad parte del código no podría ser capaz de entender completamente todavía, por lo que esos serán los archivos. C, pero entonces sus archivos adjuntos. h nos dará suficiente entendimiento que necesitamos para que podamos saber cómo esas funciones se o por lo menos lo que tienen que hacer - las entradas y salidas - incluso si no sabemos lo que está pasando en el cuadro negro o no entiende lo que está pasando en el cuadro negro en su interior. Y, por último, como siempre, se trata de nuevas estructuras de datos, determinados tipos de nodos que apuntan a ciertas cosas, y aquí tiene una pluma y un papel, no sólo para el proceso de diseño y cuando usted está tratando de averiguar cómo el conjunto de procesadores deben trabajar pero también durante la depuración. Usted puede tener GDB junto a su lápiz y papel mientras se toma por lo que los valores son, donde las flechas están apuntando, y cosas por el estilo. 

Primero echemos un vistazo a los árboles de Huffman. Árboles Huffman son árboles binarios, lo que significa que cada nodo sólo tiene 2 hijos. En árboles Huffman la característica es que los valores más frecuentes están representados por los menos bits. Hemos visto en los ejemplos de conferencias de código Morse, que tipo de consolidado algunas letras. Si usted está tratando de traducir una A o una E, por ejemplo, estás traduciendo a menudo, así que en lugar de tener que utilizar todo el conjunto de bits previstas para este tipo de datos es habitual, se comprime a menos, y luego esas cartas que están representados con menos frecuencia se representan con más bits de ya que puede darse el lujo de que cuando usted pesa las frecuencias que esas cartas aparecen. Tenemos la misma idea aquí en los árboles de Huffman donde estamos haciendo una cadena, una especie de camino para llegar a los determinados caracteres. Y luego los personajes que tienen más frecuencia van a ser representados con el menor número de bits. 

La forma en que se construye un árbol de Huffman es mediante la colocación de todos los caracteres que aparecen en el texto y el cálculo de su frecuencia, la frecuencia con la que aparecen. Esto podría ser un recuento de las veces que las letras aparecen o tal vez un porcentaje de entre todos los personajes de la cantidad de cada uno de ellos aparece. Y así, lo que haces es una vez que tienes todo eso fuera asignada, entonces busque las 2 frecuencias más bajas y luego unirlos como hermanos donde entonces el nodo padre tiene una frecuencia que es la suma de sus 2 niños. Y entonces, por convención, decir que el nodo izquierdo, usted sigue que, siguiendo la ramificación 0, y luego el nodo más a la derecha es la rama 1. Como vimos en el código Morse, el gotcha una era que si tenías un bip bip y el era ambigua. Es bien podría ser 1 carta o podría ser una secuencia de letras 2. ¿Y qué árboles Huffman hace es porque por la naturaleza de los personajes o la final los personajes reales que son los nodos anteriores en el ramo - nos referimos a aquellas como hojas - en virtud de que no puede haber ninguna ambigüedad en términos de la carta que usted está tratando de codificar con la serie de bits porque en ninguna parte a lo largo de los bits que representan una carta se encuentra otra carta entera, y no habrá ninguna confusión allí. Pero vamos a entrar en ejemplos que ustedes pueden ver realmente que en lugar de nosotros simplemente le dice que eso es cierto. 

Veamos un ejemplo simple de un árbol de Huffman. Tengo una cadena que aquí es de 12 caracteres. Tengo 4 As, 6 B, y C 2. Mi primer paso sería contar. ¿Cuántas veces Una aparecer? Parece 4 veces en la cadena. B aparece 6 veces, y C aparece 2 veces. Naturalmente, yo voy a decir que estoy usando B con mayor frecuencia, así que quiero representar B con el menor número de bits, el menor número de 0s y 1s. Y entonces yo también voy a esperar C y requieren mayor cantidad de 0s y 1s también. En primer lugar lo que hice aquí se los puse en orden ascendente en términos de frecuencia. Vemos que la C y la A, esas son nuestras dos frecuencias más bajas. Creamos un nodo padre, y que el nodo padre no tiene una carta asociada a él, pero tiene una frecuencia, que es la suma. La suma se convierte en 2 + 4, que es 6. Luego seguimos la rama izquierda. Si estuviéramos en ese nodo 6, entonces seguiríamos 0 a llegar a C y luego 1 para llegar a A. Así que ahora tenemos dos nodos. Tenemos el valor 6 y luego también tenemos otro nodo con el valor 6. Y así, los dos no son sólo el más bajo 2, pero también sólo el 2 que quedan, Por eso con los de otros padres, con la suma es 12. Así que aquí tenemos nuestro árbol de Huffman donde para llegar a B, que no sería más que el bit 1 y luego de llegar a un tendríamos 01 y luego C, con 00. Así que aquí vemos que básicamente estamos representando estos caracteres con 1 ó 2 bits donde el B, como se predijo, tiene la menor. Y entonces lo que esperábamos C a los que más tienen, pero ya que es un pequeño árbol de Huffman, A continuación, el también está representado por 2 bits en lugar de en algún lugar en el medio. 

Sólo para repasar otro ejemplo simple del árbol de Huffman, dice que tiene la cadena "Hola". Lo que hace es primero que diría cuántas veces H aparezcan en el presente? H aparece una vez y luego e aparece una vez y luego tenemos l aparece dos veces y o una vez que aparece. Y entonces esperamos que la carta de ser representado por el menor número de bits? [Estudiante] l. >> L. Si. l es correcto. Esperamos l a estar representado por el menor número de bits porque l se utiliza más en la cadena "Hola". ¿Qué voy a hacer ahora es sacar estos nodos. Tengo 1, que es H, y luego otro 1, que es e, y luego un 1, que es O - ahora mismo me estoy poniendo en orden - y luego 2, que es l. Entonces me dicen que el camino que voy a construir un árbol de Huffman es encontrar los 2 nodos que tienen menos frecuencias y hacerlos hermanos mediante la creación de un nodo padre. Aquí tenemos 3 nodos con la frecuencia más baja. Son todos 1. Así que aquí tenemos que elegir uno que vamos a vincular primero. Digamos que elegir el H y el correo. La suma de 1 + 1 es 2, pero este nodo no tiene una letra asociada con ella. Sólo tiene el valor. Ahora nos centraremos en los próximos 2 frecuencias más bajas. Eso es 2 y 1. Eso podría ser cualquiera de los 2, pero yo voy a elegir este. La suma es 3. Y, finalmente, sólo tengo 2 a la izquierda, por lo que se convierte luego 5. Entonces aquí, como era de esperar, si cumplimento la codificación para que, 1s siempre la rama derecha y 0s son el de la izquierda. Entonces tenemos l representada por sólo 1 bit y luego o el 2 por y entonces el correo por 2 y luego el H cae a 3 bits. Así que usted puede transmitir este mensaje "Hola" en lugar de utilizar realmente los personajes con sólo 0s y 1s. Sin embargo, recuerde que en varios casos hemos tenido lazos con nuestra frecuencia. Podríamos haber ni se unió a la H y O tal vez el primero. O entonces más adelante, cuando tuvimos la l representado por 2 así como el unido uno representado por 2, podríamos haber vinculado cualquiera de ellos. 

Y así, cuando se envía el 0 y 1, que en realidad no garantiza que el destinatario puede leer completamente el mensaje de buenas a primeras porque no se puede saber qué decisión que ha realizado. Así que cuando nos enfrentamos con la compresión Huffman, de alguna manera tenemos que decirle al receptor de nuestro mensaje como decidimos - Necesita saber algún tipo de información adicional Además del mensaje comprimido. Ellos necesitan entender lo que el árbol se ve realmente como, la forma en que realmente hizo esas decisiones. 

Aquí estábamos haciendo ejemplos basados ​​en el recuento real, pero a veces también puede tener un árbol de Huffman basado en la frecuencia con la que aparecen las letras, y es exactamente el mismo proceso. Aquí me estoy expresando en términos de porcentajes o fracción, y aquí exactamente lo mismo. Me parece el más bajo 2, los suma, la más baja 2 siguiente, sumarlos, hasta que tenga un árbol completo. A pesar de que podría hacerlo de cualquier manera, cuando estamos tratando con porcentajes, eso significa que estamos dividiendo las cosas y tratar con decimales o más bien flota si estamos pensando en estructuras de datos de una cabeza. ¿Qué sabemos acerca de los flotadores? ¿Qué es un problema común cuando nos enfrentamos con flotadores? [Estudiante] aritmética imprecisa. Sí >>. La imprecisión. Debido a la imprecisión de coma flotante, para este conjunto de procesadores por lo que nos aseguramos de que no se pierde ningún valor, entonces estamos realmente va a estar tratando con el conde. Así que si usted fuera a pensar en un nodo Huffman, si miramos hacia atrás a la estructura de aquí, si nos fijamos en los verdes tiene una frecuencia asociada a ella así como que apunta a un nodo a su izquierda, así como un nodo a su derecha. Y a continuación, los rojos no tienen también un carácter asociado con ellos. No vamos a hacer otras distintas para los padres y luego los nodos finales, la cual nos referimos como hojas, sino más bien los que acaban tendrán valores NULL. Por cada nodo que vamos a tener un carácter, el símbolo que representa a ese nodo, a continuación, una frecuencia, así como un puntero a su hijo izquierdo, así como su hijo derecho. Las hojas, que se encuentran en la parte inferior, también tendría punteros a nodos a su izquierda ya su derecha, pero ya que esos valores no están apuntando a los nodos reales, lo que su valor sea? >> [Estudiante] NULL. >> NULL. Exactamente. He aquí un ejemplo de cómo se puede representar la frecuencia en carrozas, pero vamos a tratar con él con números enteros, así que todo lo que he hecho es cambiar el tipo de datos allí. 

Vamos a ir a un poco más de un ejemplo complejo. Pero ahora que hemos hecho los más simples, es solo el mismo proceso. Usted encontrará las 2 frecuencias más bajas, sume las frecuencias y esa es la nueva frecuencia de su nodo padre, que a su vez apunta a su izquierda con la ramificación 0 y el derecho a la sucursal 1. Si tenemos la cadena "This is CS50", entonces cuente las veces que se menciona T, h mencionado, i, s, c, 5, 0. Entonces lo que hice aquí es con los nodos rojos Acabo de plantados, He dicho que voy a tener estos personajes finalmente en el fondo de mi árbol. Los que van a ser todas las hojas. Entonces lo que hice es que ellos ordenados por frecuencia en orden ascendente, y esto es en realidad la forma en que el código de conjunto de procesadores que hace ¿Vale la clase de frecuencia y luego por orden alfabético. Por lo tanto, tiene los números primero y luego alfabéticamente por la frecuencia. Entonces lo que yo haría es que iba a encontrar la más baja 2. Eso es 0 y 5. Yo les suma, y ​​eso es 2. A continuación, me gustaría seguir, encontrar el próximo 2 bajo. Esos son los dos 1s, y luego convertirse en los 2 también. Ahora sé que mi próximo paso va a unirse a la cifra más baja, que es la T, el 1, y después elegir uno de los nodos que tiene 2 como la frecuencia. Así que aquí tenemos 3 opciones. Lo que voy a hacer por el tobogán es sólo visualmente reordenarlos para usted para que pueda ver cómo lo estoy construyendo. Lo que el código y el código de distribución se va a hacer sería unirse a la T un con el nodo 0 y 5. Así que las sumas a 3, y luego continuamos el proceso. El 2 y el 2 ahora son los más bajos, para que luego los suma a 4. Todo el mundo siguiendo hasta ahora? Bien. Luego, después de que tenemos el 3 y el 3 que deben ser sumados, así que de nuevo sólo lo estoy cambiando de modo que usted puede ver visualmente para que no sea demasiado complicado. Entonces tenemos un 6, y luego nuestro paso final es ahora que sólo tenemos dos nodos sumamos aquellos a los que la raíz de nuestro árbol, que es 10. Y el número 10 tiene sentido porque cada nodo representado, su valor, su número de frecuencia, era cuántas veces apareció en la cadena, y luego tenemos 5 caracteres en nuestra cadena, por lo que tiene sentido. Si miramos a la forma en que realmente lo codificar, como se esperaba, la i y la s, que aparecen con más frecuencia están representados por el menor número de bits. 

Tenga cuidado aquí. En el caso de árboles Huffman realmente importa. Una S mayúscula es diferente a una s minúscula. Si tuviéramos "Este es CS50" con letras mayúsculas, la s minúscula sólo aparecen dos veces, Sería un nodo con dos como su valor, y luego S mayúscula sólo sería una vez. Así que el árbol podría cambiar las estructuras, ya que en realidad tienen una hoja adicional aquí. Pero la suma todavía sería 10. Eso es lo que realmente va a estar llamando a la suma de comprobación, la adición de todos los recuentos. 

Ahora que hemos cubierto los árboles Huffman, podemos sumergirnos en Huff'n Puff, el conjunto de procesadores. Vamos a empezar con una sección de preguntas, y esto se va a poner usted acostumbrado con los árboles binarios y la forma de operar en torno a lo siguiente: nodos de dibujo, la creación de su propia estructura typedef para un nodo, y ver cómo se puede insertar en un árbol binario, que está clasificado, atravesando, y cosas por el estilo. Ese conocimiento es, sin duda va a ayudar cuando te sumerjas en la parte Puff Huff'n del conjunto de procesadores. En la edición estándar del conjunto de procesadores, su tarea es implementar Puff, y en la versión pirata de su tarea es implementar Huff. ¿Qué Huff hace es que toma el texto y luego se traduce en el 0 y 1, por lo que el proceso que hemos hecho anteriormente, donde contamos con las frecuencias y luego hizo el árbol y luego dijo: "¿Cómo puedo obtener T?" T está representado por 100, cosas así, Huff y luego tomaría el texto y luego la salida que binaria. Pero también porque sabemos que queremos permitir que nuestro destinatario del mensaje para volver a crear el mismo árbol exacta, sino que también incluye información sobre las cuentas de la frecuencia. Luego, con Puff se nos da un archivo binario de 0 y 1 y dada también la información sobre las frecuencias. Traducimos todos los de vuelta 0s y 1s en el mensaje original que fue, por lo que estamos descomprimiendo eso. Si usted está haciendo la edición estándar, no es necesario implementar Huff, así entonces usted puede utilizar la aplicación personal de Huff. Hay instrucciones en la especificación de cómo hacer eso. Puede ejecutar la aplicación personal de Huff en un archivo de texto determinado y luego usar esa salida como la entrada a Puff. 

Como ya he dicho antes, tenemos una gran cantidad de código de distribución de ésta. Voy a empezar a ir a través de él. Voy a pasar la mayor parte del tiempo en el. Archivos h porque en el expediente. c, porque tenemos la h. y que nos proporciona los prototipos de las funciones, no acabamos de entender exactamente que - Si usted no entiende lo que está pasando en el expediente. C, entonces no te preocupes demasiado, pero sin duda prueba a echar un vistazo, ya que podría dar algunas pistas y es útil para acostumbrarse a la lectura de código de otras personas. 

En cuanto a huffile.h, en los comentarios se declara una capa de abstracción para con código de Huffman archivos. Si vamos hacia abajo, vemos que hay un máximo de 256 símbolos que puede ser que necesite para códigos. Esto incluye todas las letras del alfabeto en mayúsculas y minúsculas - - y luego los símbolos y números, etc Entonces aquí tenemos un número mágico que identifica un archivo con codificación Huffman. Dentro de un código Huffman que van a tener un número de cierta magia asociado con la cabecera. Esto podría parecer sólo un número mágico al azar, pero si en realidad se traducen en ASCII, entonces lo que realmente explica Huff. Aquí tenemos una estructura de un archivo con codificación Huffman. No todas estas características asociadas con un archivo de Huff. Entonces aquí tenemos el encabezado de un archivo de Huff, por eso lo llamamos Huffeader en lugar de agregar la h extra porque suena igual de todos modos. Cute. Tenemos un número mágico asociado con él. Si se trata de un verdadero archivo de Huff, que va a ser el número de arriba, este mágico. Y entonces tendrá una matriz. Así, para cada símbolo, de los cuales hay 256, que va a enumerar lo que la frecuencia de dichos símbolos se encuentran en el archivo de Huff. Y, finalmente, tenemos una suma de comprobación de las frecuencias, que debe ser la suma de esas frecuencias. Así que eso es lo que un Huffeader es. Entonces tenemos algunas funciones que devuelven el siguiente bit en el archivo de Huff así como escribe un bit en el fichero de Huff, y entonces esta función aquí, hfclose, que en realidad cierra el archivo Huff. Antes, se trataba de recta justo fclose, pero cuando se tiene un archivo de Huff, en lugar de lo fclosing lo que realmente va a hacer es hfclose y hfopen ella. Son funciones específicas a los archivos Huff que vamos a estar tratando. Entonces aquí se lee en el encabezado y luego escribir el encabezado. 

Con sólo leer el archivo. H podamos tipo de tener una idea de qué es un archivo Huff podría ser, ¿qué características tiene, sin tener que ir a la huffile.c, que, si nos sumergimos en, va a ser un poco más complejo. Tiene todo el archivo I / O aquí tratando con punteros. Aquí vemos que cuando llamamos hfread, por ejemplo, todavía se trata de fread. No vamos a deshacernos de esas funciones por completo, pero estamos enviando a los que se ocuparon de dentro del archivo de Huff en lugar de hacer todo nosotros mismos. Usted puede sentirse libre para explorar a través de esto si usted es curioso e ir a pelar la capa de nuevo un poco. 

El siguiente archivo que vamos a mirar es tree.h. Antes del Tutorial desliza dijimos que esperar un nodo Huffman e hicimos un nodo typedef struct. Esperamos que tenga un símbolo, una frecuencia, y luego 2 estrellas nodo. En este caso lo que estamos haciendo es que este es esencialmente el mismo pero en lugar de nodo vamos a llamarlos árboles. Tenemos una función que cuando se llama a hacer árbol que le devuelve un puntero árbol. Regreso a Speller, cuando estaban haciendo un nuevo nodo usted ha dicho nodo palabra * nuevo = malloc (sizeof) y cosas por el estilo. Básicamente, mktree se va a tratar con eso por ti. Del mismo modo, cuando se desea quitar un árbol, por lo que es esencialmente liberando al árbol cuando haya terminado con él, en vez de llamar explícitamente libre en que, en realidad estás sólo va a utilizar la función de rmtree donde se pasa el puntero a ese árbol y luego tree.c se hará cargo de eso por ti. 

Analizamos tree.c. Esperamos que las mismas funciones, excepto para ver la implementación. Como era de esperar, cuando se llama mktree lo mallocs el tamaño de un árbol en un puntero, inicializa todos los valores para el valor NULL, por lo que 0 º o nulos, y devuelve el puntero a ese árbol que acaba de malloc'd a usted. Aquí cuando se llama a eliminar árbol por primera vez se asegura de que usted no está liberando doble. Se asegura de que usted realmente tiene un árbol que desea eliminar. He aquí porque un árbol también incluye a sus hijos, lo que esto hace es que llama de forma recursiva eliminar árbol en el nodo izquierdo del árbol así como el nodo derecho. Antes de que se libera a los padres, tiene que liberar a los niños también. Padres también es intercambiable con la raíz. El padre por primera vez, así que como el tatara-tatara-tatara-tatara-abuelo o árbol abuela, primero tenemos que liberar por los primeros niveles. Así que recorrer hasta el fondo, sin ellos, y luego volver a subir, sin ellos, etc Así que eso es árbol. 

Ahora nos centraremos en los bosques. Bosque es donde se colocan todos los árboles de Huffman. Es como decir que vamos a tener algo que se llama una parcela que contiene un puntero a un árbol, así como un puntero a una trama llamada siguiente. ¿Qué estructura tiene este tipo de parece? En cierto modo se dice por ahí. Justo por aquí. Una lista enlazada. Vemos que cuando tenemos un argumento que es como una lista enlazada de parcelas. Un bosque se define como una lista enlazada de parcelas, por lo que la estructura del bosque es sólo vamos a tener un puntero a nuestra primera parcela y que la parcela tiene un árbol dentro de ella o, más bien apunta a un árbol y luego apunta a la trama siguiente, así sucesivamente y así sucesivamente. Para que un bosque que llamamos mkforest. A continuación tenemos algunas funciones muy útiles aquí. Tenemos que elegir donde se pasa en un bosque y luego el valor de retorno es un * Árbol, un puntero a un árbol. ¿Qué selección va a hacer es que voy a entrar en el bosque que está apuntando a luego retire un árbol con la frecuencia más baja de ese bosque y luego darle el puntero a ese árbol. Una vez que usted llame a recoger, el árbol no existirá nunca más en el bosque, pero el valor de retorno es el puntero a ese árbol. Entonces usted tiene la planta. Siempre y cuando se pasa un puntero a un árbol que tiene una frecuencia de no-0, qué planta va a hacer es que tomará el bosque, tome el árbol, y que dentro de la planta del árbol de la selva. Aquí tenemos rmforest. Similar a eliminar árbol, que básicamente liberó a todos nuestros árboles para nosotros, quitar bosque que para toda realidad libre contenido en ese bosque. 

Si nos fijamos en forest.c, vamos a esperar a ver por lo menos un comando rmtree allí, porque para liberar memoria en el bosque si un bosque tiene árboles en ella, luego, eventualmente vas a tener que quitar esos árboles también. Si nos fijamos en forest.c, tenemos nuestra mkforest, que es lo que esperamos. Tenemos cosas malloc. Nos inicializar la primera parcela en el bosque como NULL porque está vacío, para empezar, entonces vemos selección, que devuelve el árbol con el peso más bajo, la frecuencia más baja, y luego se deshace de ese nodo particular que apunta a ese árbol y el que viene, por lo que toma que de la lista enlazada de la selva. Y entonces aquí tenemos planta, que inserta un árbol en la lista enlazada. Lo que hace es que los bosques bien mantiene ordenados para nosotros. Y, finalmente, tenemos rmforest y, como era de esperar, tenemos rmtree llamado allí. 

En cuanto a la distribución de código hasta ahora, huffile.c fue probablemente con mucho más difícil de entender, mientras que los otros archivos en sí eran bastante fáciles de seguir. Con nuestro conocimiento de los punteros y listas enlazadas y tal, hemos sido capaces de seguir bastante bien. Pero todo lo que necesitamos hacer realmente seguro de que estamos totalmente de entender son los archivos. H porque hay que estar llamando a esas funciones, que trata de los valores de retorno, así que asegúrese de que comprende perfectamente la acción que se va a realizar cada vez que se llame a una de esas funciones. Pero en realidad la comprensión dentro de la misma no es muy necesario porque tenemos esos. Archivos h. Tenemos 2 más archivos que quedan en nuestro código de distribución. 

Echemos un vistazo a vertedero. Volcado por su comentario aquí toma un archivo comprimido Huffman- y luego traduce y vertederos de todo su contenido fuera. Aquí vemos que se está llamando hfopen. Esta es una especie de espejo para presentar de entrada * = fopen, y luego se le pasa la información. Es casi idéntico excepto que en lugar de un archivo * que estés pasando un Huffile; en lugar de fopen que está pasando en hfopen. Aquí leemos en la primera cabecera, que es una especie de forma similar a como se lee en el encabezado para un archivo de mapa de bits. Lo que estamos haciendo aquí es la comprobación para ver si la información del encabezado contiene el número mágico correcto que indica que es un archivo real Huff, entonces todas estas comprobaciones para asegurarse de que el archivo abierto que es un archivo real huffed o no. Lo que esto hace es que emite las frecuencias de todos los símbolos que podemos ver dentro de un terminal en una tabla gráfica. Esta parte va a ser útil. Tiene un poco y lee poco a poco en la variable de bits y luego imprime. Así que si yo fuera a llamar volcado en hth.bin, que es el resultado de inhalar un archivo utilizando la solución personal, me gustaría tener esto. Es la salida de todos estos personajes y luego poner la frecuencia con la que aparecen. Si nos fijamos, la mayoría de ellos son 0s excepto por esto: H, que aparece dos veces, y entonces T, que aparece una vez. Y aquí tenemos el mensaje real en 0s y 1s. Si nos fijamos en hth.txt, que presumiblemente es el mensaje original que se bufó, esperamos ver algunos Hs y Ts en ese país. En concreto, se espera ver a sólo 1 T y HS 2. Aquí estamos en hth.txt. En efecto, tiene HTH. Incluido en allí, aunque no lo podemos ver, es un carácter de nueva línea. El hth.bin archivo Huff también se codifica el carácter de nueva línea también. He aquí porque sabemos que el orden es HTH y luego salto de línea, podemos ver que probablemente el H está representada por sólo un único 1 y luego la T es probablemente 01 y luego el siguiente es H 1, así y entonces tenemos una nueva línea indicada por dos 0s. Cool. 

Y finalmente, porque estamos tratando múltiple. Cy. Archivos h, vamos a tener un argumento bastante complejo para el compilador, y aquí tenemos un Makefile que hace volcado para usted. Pero en realidad, hay que ir sobre la fabricación de su propio archivo puff.c. El Makefile en realidad no trata de hacer puff.c para usted. Estamos dejando que depende de usted para editar el Makefile. Cuando se introduce un comando como hacen todos, por ejemplo, hará todo por usted. Siéntase libre de mirar los ejemplos de Makefile del conjunto de procesadores pasado así como salirse de éste para ver cómo podría ser capaz de hacer que el archivo Puff mediante la edición de este Makefile. Eso es todo por nuestro código de distribución. 

Una vez que haya pasado por eso, entonces aquí es sólo otro recordatorio de la forma en que vamos a tener trato con los nodos de Huffman. No vamos a estar llamando a los nodos más, nosotros vamos a estar llamando árboles donde vamos a representar a su símbolo con un char, su frecuencia, el número de ocurrencias, con un número entero. Estamos usando esto porque es más preciso que un flotador. Y luego tenemos otro puntero al hijo izquierdo y el hijo derecho. Un bosque, como hemos visto, es sólo una lista enlazada de árboles. En última instancia, cuando estamos construyendo nuestro archivo Huff, queremos que nuestro bosque para contener sólo 1 árbol - Un árbol, una raíz con varios niños. Anteriormente cuando estábamos haciendo nuestros árboles Huffman, empezamos poniendo todos los nodos en nuestra pantalla y decir que vamos a tener estos nodos, eventualmente van a ser las hojas, y esta es su símbolo, se trata de su frecuencia. En nuestro bosque si solo tenemos tres cartas, que es un bosque de 3 árboles. Y luego, a medida que avanzamos, cuando se agregó el primer padre, hicimos un bosque de 2 árboles. Hemos eliminado dos de los hijos de nuestro bosque y luego lo reemplazó con un nodo padre que tenía esos dos nodos como los niños. Y, por último, nuestro último paso con la fabricación de nuestro ejemplo con el As, Bs y Cs sería hacer la matriz final, y es así, que traería a nuestra cuenta total de los árboles en el bosque a 1. ¿Todo el mundo ve cómo se inicia con varios árboles en el bosque y terminar con 1? Bien. Cool. 

¿Qué es lo que tenemos que hacer para Puff? Lo que tenemos que hacer es asegurarse de que, como siempre, nos dan el tipo de entrada para que pueda ejecutar el programa. En este caso, vamos a estar dándonos después de su primer argumento de la línea de comandos 2 más: el archivo que desea descomprimir y la salida del archivo descomprimido. Pero una vez que nos aseguramos de que nos pase en la cantidad correcta de los valores, queremos asegurar que la entrada es un archivo Huff o no. Y una vez te garantizamos que es un archivo de Huff, entonces queremos construir nuestro árbol, construir el árbol de manera que coincida con el árbol que la persona que envió el mensaje construido. A continuación, después de construir el árbol, entonces podemos tratar con el, 0s y 1s que pasaron en siguen a los largo de nuestro árbol porque es idéntico, y luego escribir ese mensaje, interpretar los bits de nuevo en chars. Y luego, al final, ya que estamos tratando con punteros aquí, queremos asegurarnos de que no tenemos pérdidas de memoria y que todo sea gratis. 

Velar por el uso adecuado es algo viejo para nosotros por ahora. Tomamos en una entrada, que va a ser el nombre del archivo que se hinchan, y entonces especificar una salida, por lo que el nombre del archivo para la salida de inflado, que será el archivo de texto. Esa es su uso. Y ahora queremos asegurarnos de que la entrada está resopló como si no. Pensándolo bien, ¿había algo en el código de distribución que nos pueden ayudar a con la comprensión de si un archivo está resopló o no? No había información en huffile.c sobre la Huffeader. Sabemos que todos los archivos Huff tiene un Huffeader asociado con un número mágico así como una matriz de las frecuencias para cada símbolo así como una suma de comprobación. Lo sabemos, pero que también nos llevó un vistazo a dump.c, en el que se lee en un archivo de Huff. Y para hacer eso, tenía que comprobar si realmente se sopló como si no. Así que tal vez podríamos usar dump.c como una estructura para nuestro puff.c. Volver al conjunto de procesadores 4 cuando tuvimos la copy.c archivo que copió en triples RGB y se interpretó que para Whodunit y cambio de tamaño, del mismo modo, lo que se puede hacer es ejecutar el comando como cp dump.c puff.c y el uso de una parte del código allí. Sin embargo, no va a ser tan sencillo de un proceso para la traducción de su dump.c en puff.c, pero al menos le da un lugar para empezar en la forma de garantizar que la entrada está realmente o no resopló así como algunas otras cosas. Nos hemos asegurado el uso adecuado y asegurarse de que la entrada está resopló. Cada vez que hemos hecho lo que hemos hecho nuestro chequeo de errores adecuado, lo que volver y dejar la función si se produce algún fallo, si hay un problema. 

Ahora lo que quiero hacer es construir el árbol real. Si nos fijamos en el bosque, hay 2 funciones principales que vamos a querer conocer muy bien. Ahí está la planta función booleana que planta un árbol frecuencia no-0 en el interior de nuestro bosque. Y así se pasa un puntero a un bosque y un puntero a un árbol. Una pregunta rápida: ¿Cómo muchos bosques se tiene cuando usted está construyendo un árbol de Huffman? Nuestro bosque es como nuestro lienzo, ¿no? Así que sólo vamos a tener un bosque, pero vamos a tener varios árboles. Así que antes de llamar a la planta, que está probablemente va a querer hacer su bosque. Hay un comando para que si nos fijamos en forest.h sobre cómo usted puede hacer un bosque. Usted puede plantar un árbol. Sabemos cómo hacerlo. Y entonces usted puede también elegir un árbol del bosque, la eliminación de un árbol con el peso más bajo y que le da el puntero a eso. Pensando de nuevo a cuando estábamos haciendo los ejemplos de nosotros mismos, cuando la estábamos sacando, simplemente acaba de añadir los enlaces. Pero aquí, en lugar de limitarse a añadir los enlaces, Creo que es más como estás quitando 2 de los nodos y luego reemplazarlo por otro. Para expresar que en términos de cosecha y siembra, usted está recogiendo dos árboles y luego plantar otro árbol que tiene esos dos árboles que usted escogió como niños. Para construir árbol de Huffman, se puede leer en los símbolos y las frecuencias con el fin de porque el Huffeader da a ti, te ofrece una amplia gama de las frecuencias. Así que usted puede seguir adelante y simplemente hacer caso omiso de cualquier cosa con el 0 en el mismo porque no queremos 256 hojas al final de la misma. Sólo queremos que el número de hojas que son personajes que se utiliza realmente en el archivo. Usted puede leer en esos símbolos, y cada uno de esos símbolos que tienen frecuencias no-0, los que van a ser árboles. Lo que puede hacer es que cada vez que se lee en un símbolo de frecuencia no-0, usted puede plantar ese árbol en el bosque. Una vez que plantar los árboles en el bosque, usted puede unirse a los árboles como hermanos, así que ir de nuevo a la siembra y la cosecha en el que recoger 2 y luego la planta 1, donde esa planta 1 que usted es el padre de los dos niños que usted escogió. Así que el resultado final va a ser un solo árbol en el bosque. Esa es la forma de construir su árbol. 

Hay varias cosas que podrían salir mal aquí porque estamos tratando con la fabricación de nuevos árboles y hacer frente a los punteros y cosas por el estilo. Antes, cuando estábamos tratando con punteros, siempre que malloc'd queríamos asegurarnos de que no nos devuelven un valor de puntero NULL. Así que en varios pasos dentro de este proceso no van a ser varios casos donde el programa podría fallar. Lo que quiero hacer es que usted quiere asegurarse de que usted maneja esos errores, y en la especificación que dice manejarlos con gracia, así como imprimir un mensaje al usuario diciéndole por qué el programa tiene que dejar de fumar y luego rápidamente salir de ella. Para ello, el control de errores, recuerde que usted desee comprobar cada vez que hay podría ser un fracaso. Cada vez que usted está haciendo un nuevo puntero usted quiere asegurarse de que eso es un éxito. Antes de lo que solemos hacer es hacer un nuevo puntero y malloc ella, y entonces podríamos comprobar si ese puntero es NULL. Así que ahí va a haber algunos casos donde sólo se puede hacer eso, pero a veces en realidad está llamando a una función y dentro de esa función, que es la que está haciendo el mallocing. En ese caso, si echamos la vista atrás a algunas de las funciones dentro del código, algunos de ellos son funciones booleanas. En el caso abstracto si tenemos una función booleana llamada foo, Básicamente, podemos suponer que, además de hacer lo que hace foo, ya que es una función booleana, devuelve verdadero o falso - true si es correcto, false en caso contrario. Así que queremos comprobar si el valor de retorno de foo es verdadero o falso. Si es falso, eso significa que vamos a querer imprimir algún tipo de mensaje y salga del programa. Lo que queremos hacer es comprobar el valor devuelto de foo. Si foo devuelve false, entonces sabemos que nos encontramos con algún tipo de error y tenemos que salir de nuestro programa. Una manera de hacer esto es tener una condición donde la función en sí es su condición. Diga foo toma en x. Podemos tener como condición if (foo (x)). Básicamente, esto significa que si al final de la ejecución de foo devuelve verdadero, entonces no podemos hacer esto porque la función tiene que evaluar foo con el fin de evaluar la condición general. Así que así es como se puede hacer algo si la función devuelve cierto y es un éxito. Pero cuando uno es la comprobación de errores, sólo quieren dejar de fumar si su función devuelve false. Lo que podría hacer es añadir un == false o simplemente añadir una explosión en frente de ella y luego tienes if (! foo). Dentro de ese conjunto de condiciones que usted tendría todo el control de errores, así como, "No se pudo crear este árbol" y luego devolver 1 o algo por el estilo. Lo que hace, sin embargo, es que a pesar de foo devuelto false - Diga foo devuelve true. Entonces usted no tiene que llamar a foo nuevo. Eso es un error común. Debido a que fue en su condición, ya está evaluado, por lo que ya tienen el resultado si usted está usando make árbol o algo por el estilo o de la planta o de la selección o algo así. Ya tiene ese valor. Ya está ejecutado. Así que es útil el uso de funciones booleanas como la condición porque si en realidad se ejecuta el cuerpo del bucle, ejecuta la función de todos modos. 

Nuestro segundo a último paso es escribir el mensaje en el archivo. Una vez que construir el árbol de Huffman, a continuación, escribir el mensaje en el archivo es bastante sencillo. Es bastante sencillo ahora a seguir sólo el 0 y 1. Y así, por convención, se sabe que en un árbol de Huffman los 0 Indique izquierdo y el 1s indicar derecha. Así que si usted lee en poco a poco, cada vez que se obtiene un 0 podrás seguir la rama izquierda, y luego cada vez que se lee en un 1 usted va a seguir la rama derecha. Y entonces usted va a continuar hasta llegar a una hoja porque las hojas van a estar en el extremo de las ramas. ¿Cómo podemos saber si nos hemos topado con una hoja o no? Lo hemos dicho antes. [Estudiante] Si los punteros son NULL. Sí >>. Podemos saber si nos hemos topado con una hoja si los punteros a los árboles de la izquierda y la derecha son NULL. Perfecto. Sabemos que queremos leer en poco a poco en nuestro archivo de Huff. Como vimos antes en dump.c, lo que hicieron es que leen en poco a poco en el archivo de Huff y acaba de imprimir lo que los bits eran. No vamos a estar haciendo eso. Vamos a estar haciendo algo que es un poco más complejo. Pero lo que podemos hacer es que podemos tomar ese trozo de código que lee a la broca. Aquí tenemos el bit entero que representa el bit actual que estamos. Este se encarga de la iteración de todos los bits en el archivo hasta que llegue al final del archivo. Basado en esto, entonces usted va a querer tener algún tipo de iterador para recorrer el árbol. Y a continuación, en función de si el bit es 0 o 1, usted va a querer mover cualquiera que iterador hacia la izquierda o moverlo a la derecha todo el camino hasta llegar a una hoja, por lo que todo el camino hasta ese nodo que está en no apunta a ningún nodos más. ¿Por qué le vamos a hacer esto con un archivo de Huffman, pero no el código Morse? Porque en código Morse que hay un poco de ambigüedad. Podríamos ser como, oh espera, nos hemos topado con una carta en el camino, así que tal vez esta es nuestra carta, mientras que si seguimos un poco más, entonces habría golpeado otra carta. Pero eso no va a suceder en la codificación Huffman, por lo que podemos estar seguros de que la única manera que vamos a golpear un carácter es si los hijos izquierdo y derecho que nodo son NULL. 

Por último, queremos liberar a todos de nuestra memoria. Queremos tanto a cerrar el archivo Huff que hemos estado tratando con así como eliminar todos los árboles de nuestro bosque. De acuerdo con su aplicación, usted está probablemente va a querer llamar quitar bosque lugar de realmente ir a través de todos los árboles usted mismo. Pero si usted hizo los árboles temporales, tendrá que liberar a eso. Usted sabe que su mejor código, para que sepa dónde está la asignación de memoria. Así que si vas en, comience incluso para el Control f'ing malloc, viendo cada vez que malloc y asegurarse de que te libere de todo eso pero entonces sólo va a través de su código, entender en las que podría haber asignado la memoria. Por lo general, usted podría decir: "Al final de un archivo que sólo voy a quitar mi bosque en bosque" así que básicamente borrar ese recuerdo, sin que, "Y entonces yo también voy a cerrar el archivo y entonces mi programa va a dejar de fumar." Pero es que la única vez que el programa se cierra? No, porque a veces puede haber habido un error que ocurrió. Tal vez no hemos podido abrir un archivo o no podíamos hacer otra árbol o algún tipo de error ocurrido en el proceso de asignación de memoria y así lo devolvió NULL. Un error ocurrió y luego volvimos y dejar de fumar. Así que usted quiere asegurarse de que cualquier momento es posible que el programa puede dejar de fumar, desea liberar toda la memoria allí. No sólo va a estar en la final de la función principal que sale de su código. ¿Quieres ver de nuevo a todos los casos que el código potencialmente podría regresar antes de tiempo y luego liberar la memoria todo lo que tiene sentido. Diga que lo había llamado a hacer del bosque y que devuelve false. Entonces probablemente no tendrá que quitar su bosque porque usted no tiene un bosque todavía. Pero en todos los puntos del código en el que podría regresar antes de tiempo usted querrá asegurarse de que usted liberar cualquier memoria posible. 

Así que cuando nos enfrentamos a la liberación de memoria y tener fugas potenciales, Queremos no sólo utilizaremos nuestro juicio y nuestra lógica sino también utilizar Valgrind para determinar si se ha liberado toda nuestra memoria correctamente o no. Puede ejecutar Valgrind en Puff y entonces usted tiene que pasar también el número correcto de argumentos de línea de comandos para Valgrind. Puedes correr, pero la salida es un poco críptico. Nos hemos vuelto un poco acostumbrado a ello con el revisor ortográfico, pero todavía necesitamos la ayuda de un poco más, por lo que también se ejecuta con algunas banderas más como la fuga-check = completo, que probablemente nos va a dar una salida más útil sobre Valgrind. 

Luego, otro consejo útil cuando se está depurando es el comando diff. Puede acceder a la aplicación al personal de Huff, correr que en un archivo de texto, y luego la salida a un archivo binario, un archivo binario Huff, que es específica. Entonces si ejecuta su propio soplo sobre ese archivo binario, entonces lo ideal, el archivo de texto de salida tipo va a ser idéntico a la original que pasa pulg Aquí estoy usando hth.txt como ejemplo, y esa es la que se habla en su especificación. Eso es, literalmente, sólo HTH y luego un salto de línea. Pero definitivamente se siente libre y que son sin duda anima a utilizar más ejemplos para el archivo de texto. 

Usted puede incluso tomar una foto en tal vez la compresión y descompresión de entonces algunos de los archivos que se utilizan en Speller como Guerra y Paz o Jane Austen o algo por el estilo - que sería una especie de fresco - o Austin Powers, tipo de tratar con archivos más grandes, ya que no habría llegado hasta él si usamos la siguiente herramienta aquí, ls-l. Estamos acostumbrados a ls, que básicamente muestra todos los contenidos en nuestro directorio actual. Al pasar por la bandera-l en realidad muestra el tamaño de los archivos. Si usted va a través de la especificación del conjunto de procesadores, lo que realmente le guía a través de la creación del archivo binario, de soplar, y se ve que para archivos muy pequeños el coste del espacio de comprimirlo y traducir toda esa información de todas las frecuencias y cosas por el estilo que sea mayor que el beneficio real de comprimir el archivo en el primer lugar. Pero si lo ejecuta en algunos archivos de texto más largos, entonces es posible que vea que usted comienza a conseguir algún beneficio en la compresión de los archivos. 

Y, finalmente, tenemos a nuestro viejo amigo GDB, que sin duda va a ser muy útil también. 

¿Tenemos alguna pregunta sobre los árboles Huff o el proceso tal vez de hacer que los árboles o cualquier otra pregunta sobre Puff Huff'n? Bien. Me quedaré alrededor para un poco. 

Gracias a todos. Esto era Tutorial 6. Y buena suerte. 

[CS50.TV]