1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Tutorial - Boletín de problemas 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvard University]

3
00:00:04,810 --> 00:00:07,240
[Esta es CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hola a todos y bienvenidos a Tutorial 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
En Puff Huff'n lo que estamos haciendo va a estar tratando con un archivo comprimido Huffman

6
00:00:17,440 --> 00:00:20,740
y luego soplar una copia de seguridad, por lo que la descompresión,

7
00:00:20,740 --> 00:00:25,810
por lo que podemos traducir de el 0 y 1 que el usuario nos envía

8
00:00:25,810 --> 00:00:30,660
y convertir de nuevo en el texto original.

9
00:00:30,660 --> 00:00:34,360
Pset 6 va a ser muy bueno porque vas a ver algunas de las herramientas

10
00:00:34,360 --> 00:00:41,730
que utilizó en el conjunto de procesadores 4 y 5 y el conjunto de procesadores tipo de combinación en un concepto bastante limpio

11
00:00:41,730 --> 00:00:43,830
cuando se llega a pensar en ello.

12
00:00:43,830 --> 00:00:50,110
>> También, sin duda, pset 4 y 5 fueron los conjuntos de procesadores más difíciles que hemos tenido que ofrecer.

13
00:00:50,110 --> 00:00:53,950
Así que a partir de ahora, tenemos este conjunto de procesadores 1 más en C,

14
00:00:53,950 --> 00:00:56,480
y después de eso estamos en la programación web.

15
00:00:56,480 --> 00:01:02,310
Así que os felicito por conseguir sobre la chepa más dura en CS50.

16
00:01:03,630 --> 00:01:09,760
>> Pasando por Puff Huff'n, nuestra caja de herramientas para este conjunto de procesadores van a ser árboles de Huffman,

17
00:01:09,760 --> 00:01:14,700
por lo que entender no sólo cómo funcionan los árboles binarios, sino también específicamente árboles Huffman,

18
00:01:14,700 --> 00:01:16,240
cómo están construidos.

19
00:01:16,240 --> 00:01:20,210
Y entonces vamos a tener una gran cantidad de código distribución en este conjunto de procesadores,

20
00:01:20,210 --> 00:01:22,480
y vamos a llegar a ver que en realidad parte del código

21
00:01:22,480 --> 00:01:24,670
no podría ser capaz de entender completamente todavía,

22
00:01:24,670 --> 00:01:30,080
por lo que esos serán los archivos. C, pero entonces sus archivos adjuntos. h

23
00:01:30,080 --> 00:01:34,300
nos dará suficiente entendimiento que necesitamos para que podamos saber cómo esas funciones se

24
00:01:34,300 --> 00:01:38,100
o por lo menos lo que tienen que hacer - las entradas y salidas -

25
00:01:38,100 --> 00:01:40,760
incluso si no sabemos lo que está pasando en el cuadro negro

26
00:01:40,760 --> 00:01:44,090
o no entiende lo que está pasando en el cuadro negro en su interior.

27
00:01:44,090 --> 00:01:49,400
Y, por último, como siempre, se trata de nuevas estructuras de datos,

28
00:01:49,400 --> 00:01:51,840
determinados tipos de nodos que apuntan a ciertas cosas,

29
00:01:51,840 --> 00:01:56,080
y aquí tiene una pluma y un papel, no sólo para el proceso de diseño

30
00:01:56,080 --> 00:01:58,470
y cuando usted está tratando de averiguar cómo el conjunto de procesadores deben trabajar

31
00:01:58,470 --> 00:02:00,520
pero también durante la depuración.

32
00:02:00,520 --> 00:02:06,140
Usted puede tener GDB junto a su lápiz y papel mientras se toma por lo que los valores son,

33
00:02:06,140 --> 00:02:09,320
donde las flechas están apuntando, y cosas por el estilo.

34
00:02:09,320 --> 00:02:13,720
>> Primero echemos un vistazo a los árboles de Huffman.

35
00:02:13,720 --> 00:02:19,600
Árboles Huffman son árboles binarios, lo que significa que cada nodo sólo tiene 2 hijos.

36
00:02:19,600 --> 00:02:24,870
En árboles Huffman la característica es que los valores más frecuentes

37
00:02:24,870 --> 00:02:27,140
están representados por los menos bits.

38
00:02:27,140 --> 00:02:32,690
Hemos visto en los ejemplos de conferencias de código Morse, que tipo de consolidado algunas letras.

39
00:02:32,690 --> 00:02:38,030
Si usted está tratando de traducir una A o una E, por ejemplo,

40
00:02:38,030 --> 00:02:43,940
estás traduciendo a menudo, así que en lugar de tener que utilizar todo el conjunto de bits

41
00:02:43,940 --> 00:02:48,640
previstas para este tipo de datos es habitual, se comprime a menos,

42
00:02:48,640 --> 00:02:53,730
y luego esas cartas que están representados con menos frecuencia se representan con más bits de

43
00:02:53,730 --> 00:02:59,840
ya que puede darse el lujo de que cuando usted pesa las frecuencias que esas cartas aparecen.

44
00:02:59,840 --> 00:03:03,020
Tenemos la misma idea aquí en los árboles de Huffman

45
00:03:03,020 --> 00:03:12,360
donde estamos haciendo una cadena, una especie de camino para llegar a los determinados caracteres.

46
00:03:12,360 --> 00:03:14,470
Y luego los personajes que tienen más frecuencia

47
00:03:14,470 --> 00:03:17,940
van a ser representados con el menor número de bits.

48
00:03:17,940 --> 00:03:22,020
>> La forma en que se construye un árbol de Huffman

49
00:03:22,020 --> 00:03:27,430
es mediante la colocación de todos los caracteres que aparecen en el texto

50
00:03:27,430 --> 00:03:30,630
y el cálculo de su frecuencia, la frecuencia con la que aparecen.

51
00:03:30,630 --> 00:03:33,880
Esto podría ser un recuento de las veces que las letras aparecen

52
00:03:33,880 --> 00:03:40,270
o tal vez un porcentaje de entre todos los personajes de la cantidad de cada uno de ellos aparece.

53
00:03:40,270 --> 00:03:44,270
Y así, lo que haces es una vez que tienes todo eso fuera asignada,

54
00:03:44,270 --> 00:03:49,060
entonces busque las 2 frecuencias más bajas y luego unirlos como hermanos

55
00:03:49,060 --> 00:03:55,660
donde entonces el nodo padre tiene una frecuencia que es la suma de sus 2 niños.

56
00:03:55,660 --> 00:04:00,870
Y entonces, por convención, decir que el nodo izquierdo,

57
00:04:00,870 --> 00:04:03,770
usted sigue que, siguiendo la ramificación 0,

58
00:04:03,770 --> 00:04:08,140
y luego el nodo más a la derecha es la rama 1.

59
00:04:08,140 --> 00:04:16,040
Como vimos en el código Morse, el gotcha una era que si tenías un bip bip y el

60
00:04:16,040 --> 00:04:18,120
era ambigua.

61
00:04:18,120 --> 00:04:22,430
Es bien podría ser 1 carta o podría ser una secuencia de letras 2.

62
00:04:22,430 --> 00:04:27,790
¿Y qué árboles Huffman hace es porque por la naturaleza de los personajes

63
00:04:27,790 --> 00:04:34,140
o la final los personajes reales que son los nodos anteriores en el ramo -

64
00:04:34,140 --> 00:04:39,300
nos referimos a aquellas como hojas - en virtud de que no puede haber ninguna ambigüedad

65
00:04:39,300 --> 00:04:45,160
en términos de la carta que usted está tratando de codificar con la serie de bits

66
00:04:45,160 --> 00:04:50,670
porque en ninguna parte a lo largo de los bits que representan una carta

67
00:04:50,670 --> 00:04:55,960
se encuentra otra carta entera, y no habrá ninguna confusión allí.

68
00:04:55,960 --> 00:04:58,430
Pero vamos a entrar en ejemplos que ustedes pueden ver realmente que

69
00:04:58,430 --> 00:05:02,120
en lugar de nosotros simplemente le dice que eso es cierto.

70
00:05:02,120 --> 00:05:06,390
>> Veamos un ejemplo simple de un árbol de Huffman.

71
00:05:06,390 --> 00:05:09,380
Tengo una cadena que aquí es de 12 caracteres.

72
00:05:09,380 --> 00:05:14,010
Tengo 4 As, 6 B, y C 2.

73
00:05:14,010 --> 00:05:17,270
Mi primer paso sería contar.

74
00:05:17,270 --> 00:05:20,760
¿Cuántas veces Una aparecer? Parece 4 veces en la cadena.

75
00:05:20,760 --> 00:05:25,060
B aparece 6 veces, y C aparece 2 veces.

76
00:05:25,060 --> 00:05:28,970
Naturalmente, yo voy a decir que estoy usando B con mayor frecuencia,

77
00:05:28,970 --> 00:05:35,970
así que quiero representar B con el menor número de bits, el menor número de 0s y 1s.

78
00:05:35,970 --> 00:05:42,600
Y entonces yo también voy a esperar C y requieren mayor cantidad de 0s y 1s también.

79
00:05:42,600 --> 00:05:48,550
En primer lugar lo que hice aquí se los puse en orden ascendente en términos de frecuencia.

80
00:05:48,550 --> 00:05:52,710
Vemos que la C y la A, esas son nuestras dos frecuencias más bajas.

81
00:05:52,710 --> 00:06:00,290
Creamos un nodo padre, y que el nodo padre no tiene una carta asociada a él,

82
00:06:00,290 --> 00:06:05,070
pero tiene una frecuencia, que es la suma.

83
00:06:05,070 --> 00:06:08,780
La suma se convierte en 2 + 4, que es 6.

84
00:06:08,780 --> 00:06:10,800
Luego seguimos la rama izquierda.

85
00:06:10,800 --> 00:06:14,970
Si estuviéramos en ese nodo 6, entonces seguiríamos 0 a llegar a C

86
00:06:14,970 --> 00:06:17,450
y luego 1 para llegar a A.

87
00:06:17,450 --> 00:06:20,300
Así que ahora tenemos dos nodos.

88
00:06:20,300 --> 00:06:23,920
Tenemos el valor 6 y luego también tenemos otro nodo con el valor 6.

89
00:06:23,920 --> 00:06:28,550
Y así, los dos no son sólo el más bajo 2, pero también sólo el 2 que quedan,

90
00:06:28,550 --> 00:06:33,820
Por eso con los de otros padres, con la suma es 12.

91
00:06:33,820 --> 00:06:36,300
Así que aquí tenemos nuestro árbol de Huffman

92
00:06:36,300 --> 00:06:40,020
donde para llegar a B, que no sería más que el bit 1

93
00:06:40,020 --> 00:06:45,430
y luego de llegar a un tendríamos 01 y luego C, con 00.

94
00:06:45,430 --> 00:06:51,300
Así que aquí vemos que básicamente estamos representando estos caracteres con 1 ó 2 bits

95
00:06:51,300 --> 00:06:55,160
donde el B, como se predijo, tiene la menor.

96
00:06:55,160 --> 00:07:01,730
Y entonces lo que esperábamos C a los que más tienen, pero ya que es un pequeño árbol de Huffman,

97
00:07:01,730 --> 00:07:06,020
A continuación, el también está representado por 2 bits en lugar de en algún lugar en el medio.

98
00:07:07,820 --> 00:07:11,070
>> Sólo para repasar otro ejemplo simple del árbol de Huffman,

99
00:07:11,070 --> 00:07:19,570
dice que tiene la cadena "Hola".

100
00:07:19,570 --> 00:07:25,360
Lo que hace es primero que diría cuántas veces H aparezcan en el presente?

101
00:07:25,360 --> 00:07:34,200
H aparece una vez y luego e aparece una vez y luego tenemos l aparece dos veces

102
00:07:34,200 --> 00:07:36,580
y o una vez que aparece.

103
00:07:36,580 --> 00:07:44,310
Y entonces esperamos que la carta de ser representado por el menor número de bits?

104
00:07:44,310 --> 00:07:47,450
[Estudiante] l. >> L. Si. l es correcto.

105
00:07:47,450 --> 00:07:50,730
Esperamos l a estar representado por el menor número de bits

106
00:07:50,730 --> 00:07:55,890
porque l se utiliza más en la cadena "Hola".

107
00:07:55,890 --> 00:08:04,280
¿Qué voy a hacer ahora es sacar estos nodos.

108
00:08:04,280 --> 00:08:15,580
Tengo 1, que es H, y luego otro 1, que es e, y luego un 1, que es O -

109
00:08:15,580 --> 00:08:23,410
ahora mismo me estoy poniendo en orden - y luego 2, que es l.

110
00:08:23,410 --> 00:08:32,799
Entonces me dicen que el camino que voy a construir un árbol de Huffman es encontrar los 2 nodos que tienen menos frecuencias

111
00:08:32,799 --> 00:08:38,010
y hacerlos hermanos mediante la creación de un nodo padre.

112
00:08:38,010 --> 00:08:41,850
Aquí tenemos 3 nodos con la frecuencia más baja. Son todos 1.

113
00:08:41,850 --> 00:08:50,620
Así que aquí tenemos que elegir uno que vamos a vincular primero.

114
00:08:50,620 --> 00:08:54,850
Digamos que elegir el H y el correo.

115
00:08:54,850 --> 00:09:01,150
La suma de 1 + 1 es 2, pero este nodo no tiene una letra asociada con ella.

116
00:09:01,150 --> 00:09:04,440
Sólo tiene el valor.

117
00:09:04,440 --> 00:09:10,950
Ahora nos centraremos en los próximos 2 frecuencias más bajas.

118
00:09:10,950 --> 00:09:15,590
Eso es 2 y 1. Eso podría ser cualquiera de los 2, pero yo voy a elegir este.

119
00:09:15,590 --> 00:09:18,800
La suma es 3.

120
00:09:18,800 --> 00:09:26,410
Y, finalmente, sólo tengo 2 a la izquierda, por lo que se convierte luego 5.

121
00:09:26,410 --> 00:09:32,010
Entonces aquí, como era de esperar, si cumplimento la codificación para que,

122
00:09:32,010 --> 00:09:37,480
1s siempre la rama derecha y 0s son el de la izquierda.

123
00:09:37,480 --> 00:09:45,880
Entonces tenemos l representada por sólo 1 bit y luego o el 2 por

124
00:09:45,880 --> 00:09:52,360
y entonces el correo por 2 y luego el H cae a 3 bits.

125
00:09:52,360 --> 00:09:59,750
Así que usted puede transmitir este mensaje "Hola" en lugar de utilizar realmente los personajes

126
00:09:59,750 --> 00:10:02,760
con sólo 0s y 1s.

127
00:10:02,760 --> 00:10:07,910
Sin embargo, recuerde que en varios casos hemos tenido lazos con nuestra frecuencia.

128
00:10:07,910 --> 00:10:11,900
Podríamos haber ni se unió a la H y O tal vez el primero.

129
00:10:11,900 --> 00:10:15,730
O entonces más adelante, cuando tuvimos la l representado por 2

130
00:10:15,730 --> 00:10:19,410
así como el unido uno representado por 2, podríamos haber vinculado cualquiera de ellos.

131
00:10:19,410 --> 00:10:23,630
>> Y así, cuando se envía el 0 y 1, que en realidad no garantiza

132
00:10:23,630 --> 00:10:27,090
que el destinatario puede leer completamente el mensaje de buenas a primeras

133
00:10:27,090 --> 00:10:30,490
porque no se puede saber qué decisión que ha realizado.

134
00:10:30,490 --> 00:10:34,920
Así que cuando nos enfrentamos con la compresión Huffman,

135
00:10:34,920 --> 00:10:40,090
de alguna manera tenemos que decirle al receptor de nuestro mensaje como decidimos -

136
00:10:40,090 --> 00:10:43,470
Necesita saber algún tipo de información adicional

137
00:10:43,470 --> 00:10:46,580
Además del mensaje comprimido.

138
00:10:46,580 --> 00:10:51,490
Ellos necesitan entender lo que el árbol se ve realmente como,

139
00:10:51,490 --> 00:10:55,450
la forma en que realmente hizo esas decisiones.

140
00:10:55,450 --> 00:10:59,100
>> Aquí estábamos haciendo ejemplos basados ​​en el recuento real,

141
00:10:59,100 --> 00:11:01,550
pero a veces también puede tener un árbol de Huffman

142
00:11:01,550 --> 00:11:05,760
basado en la frecuencia con la que aparecen las letras, y es exactamente el mismo proceso.

143
00:11:05,760 --> 00:11:09,090
Aquí me estoy expresando en términos de porcentajes o fracción,

144
00:11:09,090 --> 00:11:11,290
y aquí exactamente lo mismo.

145
00:11:11,290 --> 00:11:15,300
Me parece el más bajo 2, los suma, la más baja 2 siguiente, sumarlos,

146
00:11:15,300 --> 00:11:19,390
hasta que tenga un árbol completo.

147
00:11:19,390 --> 00:11:23,610
A pesar de que podría hacerlo de cualquier manera, cuando estamos tratando con porcentajes,

148
00:11:23,610 --> 00:11:27,760
eso significa que estamos dividiendo las cosas y tratar con decimales o más bien flota

149
00:11:27,760 --> 00:11:30,900
si estamos pensando en estructuras de datos de una cabeza.

150
00:11:30,900 --> 00:11:32,540
¿Qué sabemos acerca de los flotadores?

151
00:11:32,540 --> 00:11:35,180
¿Qué es un problema común cuando nos enfrentamos con flotadores?

152
00:11:35,180 --> 00:11:38,600
[Estudiante] aritmética imprecisa. Sí >>. La imprecisión.

153
00:11:38,600 --> 00:11:43,760
Debido a la imprecisión de coma flotante, para este conjunto de procesadores por lo que nos aseguramos de

154
00:11:43,760 --> 00:11:49,450
que no se pierde ningún valor, entonces estamos realmente va a estar tratando con el conde.

155
00:11:49,450 --> 00:11:54,880
Así que si usted fuera a pensar en un nodo Huffman, si miramos hacia atrás a la estructura de aquí,

156
00:11:54,880 --> 00:12:01,740
si nos fijamos en los verdes tiene una frecuencia asociada a ella

157
00:12:01,740 --> 00:12:08,760
así como que apunta a un nodo a su izquierda, así como un nodo a su derecha.

158
00:12:08,760 --> 00:12:13,970
Y a continuación, los rojos no tienen también un carácter asociado con ellos.

159
00:12:13,970 --> 00:12:18,900
No vamos a hacer otras distintas para los padres y luego los nodos finales,

160
00:12:18,900 --> 00:12:23,680
la cual nos referimos como hojas, sino más bien los que acaban tendrán valores NULL.

161
00:12:23,680 --> 00:12:31,050
Por cada nodo que vamos a tener un carácter, el símbolo que representa a ese nodo,

162
00:12:31,050 --> 00:12:40,490
a continuación, una frecuencia, así como un puntero a su hijo izquierdo, así como su hijo derecho.

163
00:12:40,490 --> 00:12:45,680
Las hojas, que se encuentran en la parte inferior, también tendría punteros a nodos

164
00:12:45,680 --> 00:12:49,550
a su izquierda ya su derecha, pero ya que esos valores no están apuntando a los nodos reales,

165
00:12:49,550 --> 00:12:53,970
lo que su valor sea? >> [Estudiante] NULL. >> NULL. Exactamente.

166
00:12:53,970 --> 00:12:58,430
He aquí un ejemplo de cómo se puede representar la frecuencia en carrozas,

167
00:12:58,430 --> 00:13:02,130
pero vamos a tratar con él con números enteros,

168
00:13:02,130 --> 00:13:06,780
así que todo lo que he hecho es cambiar el tipo de datos allí.

169
00:13:06,780 --> 00:13:09,700
>> Vamos a ir a un poco más de un ejemplo complejo.

170
00:13:09,700 --> 00:13:13,360
Pero ahora que hemos hecho los más simples, es solo el mismo proceso.

171
00:13:13,360 --> 00:13:20,290
Usted encontrará las 2 frecuencias más bajas, sume las frecuencias

172
00:13:20,290 --> 00:13:22,450
y esa es la nueva frecuencia de su nodo padre,

173
00:13:22,450 --> 00:13:29,310
que a su vez apunta a su izquierda con la ramificación 0 y el derecho a la sucursal 1.

174
00:13:29,310 --> 00:13:34,200
Si tenemos la cadena "This is CS50", entonces cuente las veces que se menciona T,

175
00:13:34,200 --> 00:13:38,420
h mencionado, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Entonces lo que hice aquí es con los nodos rojos Acabo de plantados,

177
00:13:42,010 --> 00:13:48,530
He dicho que voy a tener estos personajes finalmente en el fondo de mi árbol.

178
00:13:48,530 --> 00:13:51,740
Los que van a ser todas las hojas.

179
00:13:51,740 --> 00:13:58,200
Entonces lo que hice es que ellos ordenados por frecuencia en orden ascendente,

180
00:13:58,200 --> 00:14:02,950
y esto es en realidad la forma en que el código de conjunto de procesadores que hace

181
00:14:02,950 --> 00:14:07,550
¿Vale la clase de frecuencia y luego por orden alfabético.

182
00:14:07,550 --> 00:14:13,870
Por lo tanto, tiene los números primero y luego alfabéticamente por la frecuencia.

183
00:14:13,870 --> 00:14:18,520
Entonces lo que yo haría es que iba a encontrar la más baja 2. Eso es 0 y 5.

184
00:14:18,520 --> 00:14:22,390
Yo les suma, y ​​eso es 2. A continuación, me gustaría seguir, encontrar el próximo 2 bajo.

185
00:14:22,390 --> 00:14:26,100
Esos son los dos 1s, y luego convertirse en los 2 también.

186
00:14:26,100 --> 00:14:31,570
Ahora sé que mi próximo paso va a unirse a la cifra más baja,

187
00:14:31,570 --> 00:14:41,380
que es la T, el 1, y después elegir uno de los nodos que tiene 2 como la frecuencia.

188
00:14:41,380 --> 00:14:44,560
Así que aquí tenemos 3 opciones.

189
00:14:44,560 --> 00:14:47,980
Lo que voy a hacer por el tobogán es sólo visualmente reordenarlos para usted

190
00:14:47,980 --> 00:14:51,790
para que pueda ver cómo lo estoy construyendo.

191
00:14:51,790 --> 00:14:59,040
Lo que el código y el código de distribución se va a hacer sería unirse a la T un

192
00:14:59,040 --> 00:15:01,410
con el nodo 0 y 5.

193
00:15:01,410 --> 00:15:05,060
Así que las sumas a 3, y luego continuamos el proceso.

194
00:15:05,060 --> 00:15:08,660
El 2 y el 2 ahora son los más bajos, para que luego los suma a 4.

195
00:15:08,660 --> 00:15:12,560
Todo el mundo siguiendo hasta ahora? Bien.

196
00:15:12,560 --> 00:15:16,410
Luego, después de que tenemos el 3 y el 3 que deben ser sumados,

197
00:15:16,410 --> 00:15:21,650
así que de nuevo sólo lo estoy cambiando de modo que usted puede ver visualmente para que no sea demasiado complicado.

198
00:15:21,650 --> 00:15:25,740
Entonces tenemos un 6, y luego nuestro paso final es ahora que sólo tenemos dos nodos

199
00:15:25,740 --> 00:15:30,440
sumamos aquellos a los que la raíz de nuestro árbol, que es 10.

200
00:15:30,440 --> 00:15:34,100
Y el número 10 tiene sentido porque cada nodo representado,

201
00:15:34,100 --> 00:15:40,750
su valor, su número de frecuencia, era cuántas veces apareció en la cadena,

202
00:15:40,750 --> 00:15:46,350
y luego tenemos 5 caracteres en nuestra cadena, por lo que tiene sentido.

203
00:15:48,060 --> 00:15:52,320
Si miramos a la forma en que realmente lo codificar,

204
00:15:52,320 --> 00:15:56,580
como se esperaba, la i y la s, que aparecen con más frecuencia

205
00:15:56,580 --> 00:16:01,350
están representados por el menor número de bits.

206
00:16:03,660 --> 00:16:05,660
>> Tenga cuidado aquí.

207
00:16:05,660 --> 00:16:09,780
En el caso de árboles Huffman realmente importa.

208
00:16:09,780 --> 00:16:13,670
Una S mayúscula es diferente a una s minúscula.

209
00:16:13,670 --> 00:16:21,260
Si tuviéramos "Este es CS50" con letras mayúsculas, la s minúscula sólo aparecen dos veces,

210
00:16:21,260 --> 00:16:27,120
Sería un nodo con dos como su valor, y luego S mayúscula sólo sería una vez.

211
00:16:27,120 --> 00:16:33,440
Así que el árbol podría cambiar las estructuras, ya que en realidad tienen una hoja adicional aquí.

212
00:16:33,440 --> 00:16:36,900
Pero la suma todavía sería 10.

213
00:16:36,900 --> 00:16:39,570
Eso es lo que realmente va a estar llamando a la suma de comprobación,

214
00:16:39,570 --> 00:16:44,060
la adición de todos los recuentos.

215
00:16:46,010 --> 00:16:50,990
>> Ahora que hemos cubierto los árboles Huffman, podemos sumergirnos en Huff'n Puff, el conjunto de procesadores.

216
00:16:50,990 --> 00:16:52,900
Vamos a empezar con una sección de preguntas,

217
00:16:52,900 --> 00:16:57,990
y esto se va a poner usted acostumbrado con los árboles binarios y la forma de operar en torno a lo siguiente:

218
00:16:57,990 --> 00:17:03,230
nodos de dibujo, la creación de su propia estructura typedef para un nodo,

219
00:17:03,230 --> 00:17:07,230
y ver cómo se puede insertar en un árbol binario, que está clasificado,

220
00:17:07,230 --> 00:17:09,050
atravesando, y cosas por el estilo.

221
00:17:09,050 --> 00:17:14,560
Ese conocimiento es, sin duda va a ayudar cuando te sumerjas en la parte Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
del conjunto de procesadores.

223
00:17:19,150 --> 00:17:26,329
En la edición estándar del conjunto de procesadores, su tarea es implementar Puff,

224
00:17:26,329 --> 00:17:30,240
y en la versión pirata de su tarea es implementar Huff.

225
00:17:30,240 --> 00:17:38,490
¿Qué Huff hace es que toma el texto y luego se traduce en el 0 y 1,

226
00:17:38,490 --> 00:17:41,990
por lo que el proceso que hemos hecho anteriormente, donde contamos con las frecuencias

227
00:17:41,990 --> 00:17:50,970
y luego hizo el árbol y luego dijo: "¿Cómo puedo obtener T?"

228
00:17:50,970 --> 00:17:54,840
T está representado por 100, cosas así,

229
00:17:54,840 --> 00:17:58,860
Huff y luego tomaría el texto y luego la salida que binaria.

230
00:17:58,860 --> 00:18:04,920
Pero también porque sabemos que queremos permitir que nuestro destinatario del mensaje

231
00:18:04,920 --> 00:18:11,790
para volver a crear el mismo árbol exacta, sino que también incluye información sobre las cuentas de la frecuencia.

232
00:18:11,790 --> 00:18:17,980
Luego, con Puff se nos da un archivo binario de 0 y 1

233
00:18:17,980 --> 00:18:21,740
y dada también la información sobre las frecuencias.

234
00:18:21,740 --> 00:18:26,740
Traducimos todos los de vuelta 0s y 1s en el mensaje original que fue,

235
00:18:26,740 --> 00:18:29,350
por lo que estamos descomprimiendo eso.

236
00:18:29,350 --> 00:18:36,450
Si usted está haciendo la edición estándar, no es necesario implementar Huff,

237
00:18:36,450 --> 00:18:39,290
así entonces usted puede utilizar la aplicación personal de Huff.

238
00:18:39,290 --> 00:18:42,080
Hay instrucciones en la especificación de cómo hacer eso.

239
00:18:42,080 --> 00:18:48,780
Puede ejecutar la aplicación personal de Huff en un archivo de texto determinado

240
00:18:48,780 --> 00:18:53,270
y luego usar esa salida como la entrada a Puff.

241
00:18:53,270 --> 00:18:59,330
>> Como ya he dicho antes, tenemos una gran cantidad de código de distribución de ésta.

242
00:18:59,330 --> 00:19:01,810
Voy a empezar a ir a través de él.

243
00:19:01,810 --> 00:19:04,400
Voy a pasar la mayor parte del tiempo en el. Archivos h

244
00:19:04,400 --> 00:19:07,660
porque en el expediente. c, porque tenemos la h.

245
00:19:07,660 --> 00:19:11,650
y que nos proporciona los prototipos de las funciones,

246
00:19:11,650 --> 00:19:15,520
no acabamos de entender exactamente que -

247
00:19:15,520 --> 00:19:20,280
Si usted no entiende lo que está pasando en el expediente. C, entonces no te preocupes demasiado,

248
00:19:20,280 --> 00:19:23,600
pero sin duda prueba a echar un vistazo, ya que podría dar algunas pistas

249
00:19:23,600 --> 00:19:29,220
y es útil para acostumbrarse a la lectura de código de otras personas.

250
00:19:38,940 --> 00:19:48,270
>> En cuanto a huffile.h, en los comentarios se declara una capa de abstracción para con código de Huffman archivos.

251
00:19:48,270 --> 00:20:01,660
Si vamos hacia abajo, vemos que hay un máximo de 256 símbolos que puede ser que necesite para códigos.

252
00:20:01,660 --> 00:20:05,480
Esto incluye todas las letras del alfabeto en mayúsculas y minúsculas - -

253
00:20:05,480 --> 00:20:08,250
y luego los símbolos y números, etc

254
00:20:08,250 --> 00:20:11,930
Entonces aquí tenemos un número mágico que identifica un archivo con codificación Huffman.

255
00:20:11,930 --> 00:20:15,890
Dentro de un código Huffman que van a tener un número de cierta magia

256
00:20:15,890 --> 00:20:18,560
asociado con la cabecera.

257
00:20:18,560 --> 00:20:21,110
Esto podría parecer sólo un número mágico al azar,

258
00:20:21,110 --> 00:20:27,160
pero si en realidad se traducen en ASCII, entonces lo que realmente explica Huff.

259
00:20:27,160 --> 00:20:34,290
Aquí tenemos una estructura de un archivo con codificación Huffman.

260
00:20:34,290 --> 00:20:39,670
No todas estas características asociadas con un archivo de Huff.

261
00:20:39,670 --> 00:20:47,080
Entonces aquí tenemos el encabezado de un archivo de Huff, por eso lo llamamos Huffeader

262
00:20:47,080 --> 00:20:50,810
en lugar de agregar la h extra porque suena igual de todos modos.

263
00:20:50,810 --> 00:20:52,720
Cute.

264
00:20:52,720 --> 00:20:57,790
Tenemos un número mágico asociado con él.

265
00:20:57,790 --> 00:21:09,040
Si se trata de un verdadero archivo de Huff, que va a ser el número de arriba, este mágico.

266
00:21:09,040 --> 00:21:14,720
Y entonces tendrá una matriz.

267
00:21:14,720 --> 00:21:18,750
Así, para cada símbolo, de los cuales hay 256,

268
00:21:18,750 --> 00:21:24,760
que va a enumerar lo que la frecuencia de dichos símbolos se encuentran en el archivo de Huff.

269
00:21:24,760 --> 00:21:28,090
Y, finalmente, tenemos una suma de comprobación de las frecuencias,

270
00:21:28,090 --> 00:21:32,160
que debe ser la suma de esas frecuencias.

271
00:21:32,160 --> 00:21:36,520
Así que eso es lo que un Huffeader es.

272
00:21:36,520 --> 00:21:44,600
Entonces tenemos algunas funciones que devuelven el siguiente bit en el archivo de Huff

273
00:21:44,600 --> 00:21:52,580
así como escribe un bit en el fichero de Huff, y entonces esta función aquí, hfclose,

274
00:21:52,580 --> 00:21:54,650
que en realidad cierra el archivo Huff.

275
00:21:54,650 --> 00:21:57,290
Antes, se trataba de recta justo fclose,

276
00:21:57,290 --> 00:22:01,190
pero cuando se tiene un archivo de Huff, en lugar de lo fclosing

277
00:22:01,190 --> 00:22:06,080
lo que realmente va a hacer es hfclose y hfopen ella.

278
00:22:06,080 --> 00:22:13,220
Son funciones específicas a los archivos Huff que vamos a estar tratando.

279
00:22:13,220 --> 00:22:19,230
Entonces aquí se lee en el encabezado y luego escribir el encabezado.

280
00:22:19,230 --> 00:22:25,700
>> Con sólo leer el archivo. H podamos tipo de tener una idea de qué es un archivo Huff podría ser,

281
00:22:25,700 --> 00:22:32,480
¿qué características tiene, sin tener que ir a la huffile.c,

282
00:22:32,480 --> 00:22:36,750
que, si nos sumergimos en, va a ser un poco más complejo.

283
00:22:36,750 --> 00:22:41,270
Tiene todo el archivo I / O aquí tratando con punteros.

284
00:22:41,270 --> 00:22:48,010
Aquí vemos que cuando llamamos hfread, por ejemplo, todavía se trata de fread.

285
00:22:48,010 --> 00:22:53,050
No vamos a deshacernos de esas funciones por completo, pero estamos enviando a los que se ocuparon de

286
00:22:53,050 --> 00:22:59,760
dentro del archivo de Huff en lugar de hacer todo nosotros mismos.

287
00:22:59,760 --> 00:23:02,300
Usted puede sentirse libre para explorar a través de esto si usted es curioso

288
00:23:02,300 --> 00:23:08,410
e ir a pelar la capa de nuevo un poco.

289
00:23:20,650 --> 00:23:24,060
>> El siguiente archivo que vamos a mirar es tree.h.

290
00:23:24,060 --> 00:23:30,210
Antes del Tutorial desliza dijimos que esperar un nodo Huffman

291
00:23:30,210 --> 00:23:32,960
e hicimos un nodo typedef struct.

292
00:23:32,960 --> 00:23:38,360
Esperamos que tenga un símbolo, una frecuencia, y luego 2 estrellas nodo.

293
00:23:38,360 --> 00:23:41,870
En este caso lo que estamos haciendo es que este es esencialmente el mismo

294
00:23:41,870 --> 00:23:46,880
pero en lugar de nodo vamos a llamarlos árboles.

295
00:23:48,790 --> 00:23:56,760
Tenemos una función que cuando se llama a hacer árbol que le devuelve un puntero árbol.

296
00:23:56,760 --> 00:24:03,450
Regreso a Speller, cuando estaban haciendo un nuevo nodo

297
00:24:03,450 --> 00:24:11,410
usted ha dicho nodo palabra * nuevo = malloc (sizeof) y cosas por el estilo.

298
00:24:11,410 --> 00:24:17,510
Básicamente, mktree se va a tratar con eso por ti.

299
00:24:17,510 --> 00:24:20,990
Del mismo modo, cuando se desea quitar un árbol,

300
00:24:20,990 --> 00:24:24,810
por lo que es esencialmente liberando al árbol cuando haya terminado con él,

301
00:24:24,810 --> 00:24:33,790
en vez de llamar explícitamente libre en que, en realidad estás sólo va a utilizar la función de rmtree

302
00:24:33,790 --> 00:24:40,360
donde se pasa el puntero a ese árbol y luego tree.c se hará cargo de eso por ti.

303
00:24:40,360 --> 00:24:42,490
>> Analizamos tree.c.

304
00:24:42,490 --> 00:24:47,240
Esperamos que las mismas funciones, excepto para ver la implementación.

305
00:24:47,240 --> 00:24:57,720
Como era de esperar, cuando se llama mktree lo mallocs el tamaño de un árbol en un puntero,

306
00:24:57,720 --> 00:25:03,190
inicializa todos los valores para el valor NULL, por lo que 0 º o nulos,

307
00:25:03,190 --> 00:25:08,280
y devuelve el puntero a ese árbol que acaba de malloc'd a usted.

308
00:25:08,280 --> 00:25:13,340
Aquí cuando se llama a eliminar árbol por primera vez se asegura de que usted no está liberando doble.

309
00:25:13,340 --> 00:25:18,320
Se asegura de que usted realmente tiene un árbol que desea eliminar.

310
00:25:18,320 --> 00:25:23,330
He aquí porque un árbol también incluye a sus hijos,

311
00:25:23,330 --> 00:25:29,560
lo que esto hace es que llama de forma recursiva eliminar árbol en el nodo izquierdo del árbol

312
00:25:29,560 --> 00:25:31,650
así como el nodo derecho.

313
00:25:31,650 --> 00:25:37,790
Antes de que se libera a los padres, tiene que liberar a los niños también.

314
00:25:37,790 --> 00:25:42,770
Padres también es intercambiable con la raíz.

315
00:25:42,770 --> 00:25:46,500
El padre por primera vez, así que como el tatara-tatara-tatara-tatara-abuelo

316
00:25:46,500 --> 00:25:52,130
o árbol abuela, primero tenemos que liberar por los primeros niveles.

317
00:25:52,130 --> 00:25:58,490
Así que recorrer hasta el fondo, sin ellos, y luego volver a subir, sin ellos, etc

318
00:26:00,400 --> 00:26:02,210
Así que eso es árbol.

319
00:26:02,210 --> 00:26:04,240
>> Ahora nos centraremos en los bosques.

320
00:26:04,240 --> 00:26:09,860
Bosque es donde se colocan todos los árboles de Huffman.

321
00:26:09,860 --> 00:26:12,910
Es como decir que vamos a tener algo que se llama una parcela

322
00:26:12,910 --> 00:26:22,320
que contiene un puntero a un árbol, así como un puntero a una trama llamada siguiente.

323
00:26:22,320 --> 00:26:28,480
¿Qué estructura tiene este tipo de parece?

324
00:26:29,870 --> 00:26:32,490
En cierto modo se dice por ahí.

325
00:26:34,640 --> 00:26:36,700
Justo por aquí.

326
00:26:37,340 --> 00:26:39,170
Una lista enlazada.

327
00:26:39,170 --> 00:26:44,590
Vemos que cuando tenemos un argumento que es como una lista enlazada de parcelas.

328
00:26:44,590 --> 00:26:53,020
Un bosque se define como una lista enlazada de parcelas,

329
00:26:53,020 --> 00:26:58,100
por lo que la estructura del bosque es sólo vamos a tener un puntero a nuestra primera parcela

330
00:26:58,100 --> 00:27:02,740
y que la parcela tiene un árbol dentro de ella o, más bien apunta a un árbol

331
00:27:02,740 --> 00:27:06,190
y luego apunta a la trama siguiente, así sucesivamente y así sucesivamente.

332
00:27:06,190 --> 00:27:11,100
Para que un bosque que llamamos mkforest.

333
00:27:11,100 --> 00:27:14,930
A continuación tenemos algunas funciones muy útiles aquí.

334
00:27:14,930 --> 00:27:23,240
Tenemos que elegir donde se pasa en un bosque y luego el valor de retorno es un * Árbol,

335
00:27:23,240 --> 00:27:25,210
un puntero a un árbol.

336
00:27:25,210 --> 00:27:29,370
¿Qué selección va a hacer es que voy a entrar en el bosque que está apuntando a

337
00:27:29,370 --> 00:27:35,240
luego retire un árbol con la frecuencia más baja de ese bosque

338
00:27:35,240 --> 00:27:38,330
y luego darle el puntero a ese árbol.

339
00:27:38,330 --> 00:27:43,030
Una vez que usted llame a recoger, el árbol no existirá nunca más en el bosque,

340
00:27:43,030 --> 00:27:48,550
pero el valor de retorno es el puntero a ese árbol.

341
00:27:48,550 --> 00:27:50,730
Entonces usted tiene la planta.

342
00:27:50,730 --> 00:27:57,420
Siempre y cuando se pasa un puntero a un árbol que tiene una frecuencia de no-0,

343
00:27:57,420 --> 00:28:04,040
qué planta va a hacer es que tomará el bosque, tome el árbol, y que dentro de la planta del árbol de la selva.

344
00:28:04,040 --> 00:28:06,370
Aquí tenemos rmforest.

345
00:28:06,370 --> 00:28:11,480
Similar a eliminar árbol, que básicamente liberó a todos nuestros árboles para nosotros,

346
00:28:11,480 --> 00:28:16,600
quitar bosque que para toda realidad libre contenido en ese bosque.

347
00:28:16,600 --> 00:28:24,890
>> Si nos fijamos en forest.c, vamos a esperar a ver por lo menos un comando rmtree allí,

348
00:28:24,890 --> 00:28:30,090
porque para liberar memoria en el bosque si un bosque tiene árboles en ella,

349
00:28:30,090 --> 00:28:32,930
luego, eventualmente vas a tener que quitar esos árboles también.

350
00:28:32,930 --> 00:28:41,020
Si nos fijamos en forest.c, tenemos nuestra mkforest, que es lo que esperamos.

351
00:28:41,020 --> 00:28:42,890
Tenemos cosas malloc.

352
00:28:42,890 --> 00:28:51,740
Nos inicializar la primera parcela en el bosque como NULL porque está vacío, para empezar,

353
00:28:51,740 --> 00:29:05,940
entonces vemos selección, que devuelve el árbol con el peso más bajo, la frecuencia más baja,

354
00:29:05,940 --> 00:29:13,560
y luego se deshace de ese nodo particular que apunta a ese árbol y el que viene,

355
00:29:13,560 --> 00:29:16,760
por lo que toma que de la lista enlazada de la selva.

356
00:29:16,760 --> 00:29:24,510
Y entonces aquí tenemos planta, que inserta un árbol en la lista enlazada.

357
00:29:24,510 --> 00:29:29,960
Lo que hace es que los bosques bien mantiene ordenados para nosotros.

358
00:29:29,960 --> 00:29:37,910
Y, finalmente, tenemos rmforest y, como era de esperar, tenemos rmtree llamado allí.

359
00:29:46,650 --> 00:29:55,440
>> En cuanto a la distribución de código hasta ahora, huffile.c fue probablemente con mucho más difícil de entender,

360
00:29:55,440 --> 00:29:59,990
mientras que los otros archivos en sí eran bastante fáciles de seguir.

361
00:29:59,990 --> 00:30:03,090
Con nuestro conocimiento de los punteros y listas enlazadas y tal,

362
00:30:03,090 --> 00:30:04,860
hemos sido capaces de seguir bastante bien.

363
00:30:04,860 --> 00:30:10,500
Pero todo lo que necesitamos hacer realmente seguro de que estamos totalmente de entender son los archivos. H

364
00:30:10,500 --> 00:30:15,840
porque hay que estar llamando a esas funciones, que trata de los valores de retorno,

365
00:30:15,840 --> 00:30:20,590
así que asegúrese de que comprende perfectamente la acción que se va a realizar

366
00:30:20,590 --> 00:30:24,290
cada vez que se llame a una de esas funciones.

367
00:30:24,290 --> 00:30:33,020
Pero en realidad la comprensión dentro de la misma no es muy necesario porque tenemos esos. Archivos h.

368
00:30:35,170 --> 00:30:39,490
Tenemos 2 más archivos que quedan en nuestro código de distribución.

369
00:30:39,490 --> 00:30:41,640
>> Echemos un vistazo a vertedero.

370
00:30:41,640 --> 00:30:47,230
Volcado por su comentario aquí toma un archivo comprimido Huffman-

371
00:30:47,230 --> 00:30:55,580
y luego traduce y vertederos de todo su contenido fuera.

372
00:31:01,010 --> 00:31:04,260
Aquí vemos que se está llamando hfopen.

373
00:31:04,260 --> 00:31:10,770
Esta es una especie de espejo para presentar de entrada * = fopen,

374
00:31:10,770 --> 00:31:13,500
y luego se le pasa la información.

375
00:31:13,500 --> 00:31:18,240
Es casi idéntico excepto que en lugar de un archivo * que estés pasando un Huffile;

376
00:31:18,240 --> 00:31:22,030
en lugar de fopen que está pasando en hfopen.

377
00:31:22,030 --> 00:31:29,280
Aquí leemos en la primera cabecera, que es una especie de forma similar a como se lee en el encabezado

378
00:31:29,280 --> 00:31:33,580
para un archivo de mapa de bits.

379
00:31:33,580 --> 00:31:38,000
Lo que estamos haciendo aquí es la comprobación para ver si la información del encabezado

380
00:31:38,000 --> 00:31:44,330
contiene el número mágico correcto que indica que es un archivo real Huff,

381
00:31:44,330 --> 00:31:53,610
entonces todas estas comprobaciones para asegurarse de que el archivo abierto que es un archivo real huffed o no.

382
00:31:53,610 --> 00:32:05,330
Lo que esto hace es que emite las frecuencias de todos los símbolos que podemos ver

383
00:32:05,330 --> 00:32:09,790
dentro de un terminal en una tabla gráfica.

384
00:32:09,790 --> 00:32:15,240
Esta parte va a ser útil.

385
00:32:15,240 --> 00:32:24,680
Tiene un poco y lee poco a poco en la variable de bits y luego imprime.

386
00:32:28,220 --> 00:32:35,430
Así que si yo fuera a llamar volcado en hth.bin, que es el resultado de inhalar un archivo

387
00:32:35,430 --> 00:32:39,490
utilizando la solución personal, me gustaría tener esto.

388
00:32:39,490 --> 00:32:46,000
Es la salida de todos estos personajes y luego poner la frecuencia con la que aparecen.

389
00:32:46,000 --> 00:32:51,180
Si nos fijamos, la mayoría de ellos son 0s excepto por esto: H, que aparece dos veces,

390
00:32:51,180 --> 00:32:54,820
y entonces T, que aparece una vez.

391
00:32:54,820 --> 00:33:07,860
Y aquí tenemos el mensaje real en 0s y 1s.

392
00:33:07,860 --> 00:33:15,450
Si nos fijamos en hth.txt, que presumiblemente es el mensaje original que se bufó,

393
00:33:15,450 --> 00:33:22,490
esperamos ver algunos Hs y Ts en ese país.

394
00:33:22,490 --> 00:33:28,720
En concreto, se espera ver a sólo 1 T y HS 2.

395
00:33:32,510 --> 00:33:37,440
Aquí estamos en hth.txt. En efecto, tiene HTH.

396
00:33:37,440 --> 00:33:41,270
Incluido en allí, aunque no lo podemos ver, es un carácter de nueva línea.

397
00:33:41,270 --> 00:33:53,190
El hth.bin archivo Huff también se codifica el carácter de nueva línea también.

398
00:33:55,680 --> 00:34:01,330
He aquí porque sabemos que el orden es HTH y luego salto de línea,

399
00:34:01,330 --> 00:34:07,340
podemos ver que probablemente el H está representada por sólo un único 1

400
00:34:07,340 --> 00:34:17,120
y luego la T es probablemente 01 y luego el siguiente es H 1, así

401
00:34:17,120 --> 00:34:21,139
y entonces tenemos una nueva línea indicada por dos 0s.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> Y finalmente, porque estamos tratando múltiple. Cy. Archivos h,

404
00:34:31,600 --> 00:34:36,350
vamos a tener un argumento bastante complejo para el compilador,

405
00:34:36,350 --> 00:34:40,460
y aquí tenemos un Makefile que hace volcado para usted.

406
00:34:40,460 --> 00:34:47,070
Pero en realidad, hay que ir sobre la fabricación de su propio archivo puff.c.

407
00:34:47,070 --> 00:34:54,330
El Makefile en realidad no trata de hacer puff.c para usted.

408
00:34:54,330 --> 00:34:59,310
Estamos dejando que depende de usted para editar el Makefile.

409
00:34:59,310 --> 00:35:05,930
Cuando se introduce un comando como hacen todos, por ejemplo, hará todo por usted.

410
00:35:05,930 --> 00:35:10,760
Siéntase libre de mirar los ejemplos de Makefile del conjunto de procesadores pasado

411
00:35:10,760 --> 00:35:17,400
así como salirse de éste para ver cómo podría ser capaz de hacer que el archivo Puff

412
00:35:17,400 --> 00:35:20,260
mediante la edición de este Makefile.

413
00:35:20,260 --> 00:35:22,730
Eso es todo por nuestro código de distribución.

414
00:35:22,730 --> 00:35:28,380
>> Una vez que haya pasado por eso, entonces aquí es sólo otro recordatorio

415
00:35:28,380 --> 00:35:30,980
de la forma en que vamos a tener trato con los nodos de Huffman.

416
00:35:30,980 --> 00:35:35,400
No vamos a estar llamando a los nodos más, nosotros vamos a estar llamando árboles

417
00:35:35,400 --> 00:35:39,260
donde vamos a representar a su símbolo con un char,

418
00:35:39,260 --> 00:35:43,340
su frecuencia, el número de ocurrencias, con un número entero.

419
00:35:43,340 --> 00:35:47,370
Estamos usando esto porque es más preciso que un flotador.

420
00:35:47,370 --> 00:35:52,980
Y luego tenemos otro puntero al hijo izquierdo y el hijo derecho.

421
00:35:52,980 --> 00:35:59,630
Un bosque, como hemos visto, es sólo una lista enlazada de árboles.

422
00:35:59,630 --> 00:36:04,670
En última instancia, cuando estamos construyendo nuestro archivo Huff,

423
00:36:04,670 --> 00:36:07,580
queremos que nuestro bosque para contener sólo 1 árbol -

424
00:36:07,580 --> 00:36:12,420
Un árbol, una raíz con varios niños.

425
00:36:12,420 --> 00:36:20,840
Anteriormente cuando estábamos haciendo nuestros árboles Huffman,

426
00:36:20,840 --> 00:36:25,360
empezamos poniendo todos los nodos en nuestra pantalla

427
00:36:25,360 --> 00:36:27,790
y decir que vamos a tener estos nodos,

428
00:36:27,790 --> 00:36:32,920
eventualmente van a ser las hojas, y esta es su símbolo, se trata de su frecuencia.

429
00:36:32,920 --> 00:36:42,070
En nuestro bosque si solo tenemos tres cartas, que es un bosque de 3 árboles.

430
00:36:42,070 --> 00:36:45,150
Y luego, a medida que avanzamos, cuando se agregó el primer padre,

431
00:36:45,150 --> 00:36:48,080
hicimos un bosque de 2 árboles.

432
00:36:48,080 --> 00:36:54,930
Hemos eliminado dos de los hijos de nuestro bosque y luego lo reemplazó con un nodo padre

433
00:36:54,930 --> 00:36:58,820
que tenía esos dos nodos como los niños.

434
00:36:58,820 --> 00:37:05,600
Y, por último, nuestro último paso con la fabricación de nuestro ejemplo con el As, Bs y Cs

435
00:37:05,600 --> 00:37:08,030
sería hacer la matriz final,

436
00:37:08,030 --> 00:37:13,190
y es así, que traería a nuestra cuenta total de los árboles en el bosque a 1.

437
00:37:13,190 --> 00:37:18,140
¿Todo el mundo ve cómo se inicia con varios árboles en el bosque

438
00:37:18,140 --> 00:37:22,520
y terminar con 1? Bien. Cool.

439
00:37:25,530 --> 00:37:28,110
>> ¿Qué es lo que tenemos que hacer para Puff?

440
00:37:28,110 --> 00:37:37,110
Lo que tenemos que hacer es asegurarse de que, como siempre, nos dan el tipo de entrada

441
00:37:37,110 --> 00:37:39,090
para que pueda ejecutar el programa.

442
00:37:39,090 --> 00:37:43,130
En este caso, vamos a estar dándonos después de su primer argumento de la línea de comandos

443
00:37:43,130 --> 00:37:53,440
2 más: el archivo que desea descomprimir y la salida del archivo descomprimido.

444
00:37:53,440 --> 00:38:00,410
Pero una vez que nos aseguramos de que nos pase en la cantidad correcta de los valores,

445
00:38:00,410 --> 00:38:05,820
queremos asegurar que la entrada es un archivo Huff o no.

446
00:38:05,820 --> 00:38:10,420
Y una vez te garantizamos que es un archivo de Huff, entonces queremos construir nuestro árbol,

447
00:38:10,420 --> 00:38:20,940
construir el árbol de manera que coincida con el árbol que la persona que envió el mensaje construido.

448
00:38:20,940 --> 00:38:25,840
A continuación, después de construir el árbol, entonces podemos tratar con el, 0s y 1s que pasaron en

449
00:38:25,840 --> 00:38:29,590
siguen a los largo de nuestro árbol porque es idéntico,

450
00:38:29,590 --> 00:38:33,510
y luego escribir ese mensaje, interpretar los bits de nuevo en chars.

451
00:38:33,510 --> 00:38:35,880
Y luego, al final, ya que estamos tratando con punteros aquí,

452
00:38:35,880 --> 00:38:38,110
queremos asegurarnos de que no tenemos pérdidas de memoria

453
00:38:38,110 --> 00:38:41,330
y que todo sea gratis.

454
00:38:42,820 --> 00:38:46,430
>> Velar por el uso adecuado es algo viejo para nosotros por ahora.

455
00:38:46,430 --> 00:38:51,980
Tomamos en una entrada, que va a ser el nombre del archivo que se hinchan,

456
00:38:51,980 --> 00:38:56,010
y entonces especificar una salida,

457
00:38:56,010 --> 00:39:01,580
por lo que el nombre del archivo para la salida de inflado, que será el archivo de texto.

458
00:39:03,680 --> 00:39:08,820
Esa es su uso. Y ahora queremos asegurarnos de que la entrada está resopló como si no.

459
00:39:08,820 --> 00:39:16,420
Pensándolo bien, ¿había algo en el código de distribución que nos pueden ayudar a

460
00:39:16,420 --> 00:39:21,570
con la comprensión de si un archivo está resopló o no?

461
00:39:21,570 --> 00:39:26,910
No había información en huffile.c sobre la Huffeader.

462
00:39:26,910 --> 00:39:33,430
Sabemos que todos los archivos Huff tiene un Huffeader asociado con un número mágico

463
00:39:33,430 --> 00:39:37,240
así como una matriz de las frecuencias para cada símbolo

464
00:39:37,240 --> 00:39:39,570
así como una suma de comprobación.

465
00:39:39,570 --> 00:39:43,180
Lo sabemos, pero que también nos llevó un vistazo a dump.c,

466
00:39:43,180 --> 00:39:49,120
en el que se lee en un archivo de Huff.

467
00:39:49,120 --> 00:39:53,990
Y para hacer eso, tenía que comprobar si realmente se sopló como si no.

468
00:39:53,990 --> 00:40:03,380
Así que tal vez podríamos usar dump.c como una estructura para nuestro puff.c.

469
00:40:03,380 --> 00:40:12,680
Volver al conjunto de procesadores 4 cuando tuvimos la copy.c archivo que copió en triples RGB

470
00:40:12,680 --> 00:40:14,860
y se interpretó que para Whodunit y cambio de tamaño,

471
00:40:14,860 --> 00:40:20,390
del mismo modo, lo que se puede hacer es ejecutar el comando como cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
y el uso de una parte del código allí.

473
00:40:23,600 --> 00:40:28,210
Sin embargo, no va a ser tan sencillo de un proceso

474
00:40:28,210 --> 00:40:33,010
para la traducción de su dump.c en puff.c,

475
00:40:33,010 --> 00:40:36,160
pero al menos le da un lugar para empezar

476
00:40:36,160 --> 00:40:40,540
en la forma de garantizar que la entrada está realmente o no resopló

477
00:40:40,540 --> 00:40:43,240
así como algunas otras cosas.

478
00:40:45,930 --> 00:40:50,250
Nos hemos asegurado el uso adecuado y asegurarse de que la entrada está resopló.

479
00:40:50,250 --> 00:40:53,570
Cada vez que hemos hecho lo que hemos hecho nuestro chequeo de errores adecuado,

480
00:40:53,570 --> 00:41:01,520
lo que volver y dejar la función si se produce algún fallo, si hay un problema.

481
00:41:01,520 --> 00:41:07,170
>> Ahora lo que quiero hacer es construir el árbol real.

482
00:41:08,840 --> 00:41:12,640
Si nos fijamos en el bosque, hay 2 funciones principales

483
00:41:12,640 --> 00:41:15,800
que vamos a querer conocer muy bien.

484
00:41:15,800 --> 00:41:23,870
Ahí está la planta función booleana que planta un árbol frecuencia no-0 en el interior de nuestro bosque.

485
00:41:23,870 --> 00:41:29,250
Y así se pasa un puntero a un bosque y un puntero a un árbol.

486
00:41:32,530 --> 00:41:40,340
Una pregunta rápida: ¿Cómo muchos bosques se tiene cuando usted está construyendo un árbol de Huffman?

487
00:41:44,210 --> 00:41:46,650
Nuestro bosque es como nuestro lienzo, ¿no?

488
00:41:46,650 --> 00:41:50,800
Así que sólo vamos a tener un bosque, pero vamos a tener varios árboles.

489
00:41:50,800 --> 00:41:57,590
Así que antes de llamar a la planta, que está probablemente va a querer hacer su bosque.

490
00:41:57,590 --> 00:42:04,430
Hay un comando para que si nos fijamos en forest.h sobre cómo usted puede hacer un bosque.

491
00:42:04,430 --> 00:42:09,270
Usted puede plantar un árbol. Sabemos cómo hacerlo.

492
00:42:09,270 --> 00:42:11,590
Y entonces usted puede también elegir un árbol del bosque,

493
00:42:11,590 --> 00:42:17,540
la eliminación de un árbol con el peso más bajo y que le da el puntero a eso.

494
00:42:17,540 --> 00:42:23,090
Pensando de nuevo a cuando estábamos haciendo los ejemplos de nosotros mismos,

495
00:42:23,090 --> 00:42:27,980
cuando la estábamos sacando, simplemente acaba de añadir los enlaces.

496
00:42:27,980 --> 00:42:31,680
Pero aquí, en lugar de limitarse a añadir los enlaces,

497
00:42:31,680 --> 00:42:40,630
Creo que es más como estás quitando 2 de los nodos y luego reemplazarlo por otro.

498
00:42:40,630 --> 00:42:44,200
Para expresar que en términos de cosecha y siembra,

499
00:42:44,200 --> 00:42:48,840
usted está recogiendo dos árboles y luego plantar otro árbol

500
00:42:48,840 --> 00:42:54,060
que tiene esos dos árboles que usted escogió como niños.

501
00:42:57,950 --> 00:43:05,280
Para construir árbol de Huffman, se puede leer en los símbolos y las frecuencias con el fin de

502
00:43:05,280 --> 00:43:10,790
porque el Huffeader da a ti,

503
00:43:10,790 --> 00:43:14,250
te ofrece una amplia gama de las frecuencias.

504
00:43:14,250 --> 00:43:19,660
Así que usted puede seguir adelante y simplemente hacer caso omiso de cualquier cosa con el 0 en el mismo

505
00:43:19,660 --> 00:43:23,760
porque no queremos 256 hojas al final de la misma.

506
00:43:23,760 --> 00:43:27,960
Sólo queremos que el número de hojas que son personajes

507
00:43:27,960 --> 00:43:31,600
que se utiliza realmente en el archivo.

508
00:43:31,600 --> 00:43:37,590
Usted puede leer en esos símbolos, y cada uno de esos símbolos que tienen frecuencias no-0,

509
00:43:37,590 --> 00:43:40,440
los que van a ser árboles.

510
00:43:40,440 --> 00:43:45,990
Lo que puede hacer es que cada vez que se lee en un símbolo de frecuencia no-0,

511
00:43:45,990 --> 00:43:50,660
usted puede plantar ese árbol en el bosque.

512
00:43:50,660 --> 00:43:56,620
Una vez que plantar los árboles en el bosque, usted puede unirse a los árboles como hermanos,

513
00:43:56,620 --> 00:44:01,130
así que ir de nuevo a la siembra y la cosecha en el que recoger 2 y luego la planta 1,

514
00:44:01,130 --> 00:44:05,820
donde esa planta 1 que usted es el padre de los dos niños que usted escogió.

515
00:44:05,820 --> 00:44:11,160
Así que el resultado final va a ser un solo árbol en el bosque.

516
00:44:16,180 --> 00:44:18,170
Esa es la forma de construir su árbol.

517
00:44:18,170 --> 00:44:21,850
>> Hay varias cosas que podrían salir mal aquí

518
00:44:21,850 --> 00:44:26,580
porque estamos tratando con la fabricación de nuevos árboles y hacer frente a los punteros y cosas por el estilo.

519
00:44:26,580 --> 00:44:30,450
Antes, cuando estábamos tratando con punteros,

520
00:44:30,450 --> 00:44:36,580
siempre que malloc'd queríamos asegurarnos de que no nos devuelven un valor de puntero NULL.

521
00:44:36,580 --> 00:44:42,770
Así que en varios pasos dentro de este proceso no van a ser varios casos

522
00:44:42,770 --> 00:44:45,920
donde el programa podría fallar.

523
00:44:45,920 --> 00:44:51,310
Lo que quiero hacer es que usted quiere asegurarse de que usted maneja esos errores,

524
00:44:51,310 --> 00:44:54,580
y en la especificación que dice manejarlos con gracia,

525
00:44:54,580 --> 00:45:00,280
así como imprimir un mensaje al usuario diciéndole por qué el programa tiene que dejar de fumar

526
00:45:00,280 --> 00:45:03,050
y luego rápidamente salir de ella.

527
00:45:03,050 --> 00:45:09,490
Para ello, el control de errores, recuerde que usted desee comprobar

528
00:45:09,490 --> 00:45:12,160
cada vez que hay podría ser un fracaso.

529
00:45:12,160 --> 00:45:14,660
Cada vez que usted está haciendo un nuevo puntero

530
00:45:14,660 --> 00:45:17,040
usted quiere asegurarse de que eso es un éxito.

531
00:45:17,040 --> 00:45:20,320
Antes de lo que solemos hacer es hacer un nuevo puntero y malloc ella,

532
00:45:20,320 --> 00:45:22,380
y entonces podríamos comprobar si ese puntero es NULL.

533
00:45:22,380 --> 00:45:25,670
Así que ahí va a haber algunos casos donde sólo se puede hacer eso,

534
00:45:25,670 --> 00:45:28,610
pero a veces en realidad está llamando a una función

535
00:45:28,610 --> 00:45:33,100
y dentro de esa función, que es la que está haciendo el mallocing.

536
00:45:33,100 --> 00:45:39,110
En ese caso, si echamos la vista atrás a algunas de las funciones dentro del código,

537
00:45:39,110 --> 00:45:42,260
algunos de ellos son funciones booleanas.

538
00:45:42,260 --> 00:45:48,480
En el caso abstracto si tenemos una función booleana llamada foo,

539
00:45:48,480 --> 00:45:54,580
Básicamente, podemos suponer que, además de hacer lo que hace foo,

540
00:45:54,580 --> 00:45:57,210
ya que es una función booleana, devuelve verdadero o falso -

541
00:45:57,210 --> 00:46:01,300
true si es correcto, false en caso contrario.

542
00:46:01,300 --> 00:46:06,270
Así que queremos comprobar si el valor de retorno de foo es verdadero o falso.

543
00:46:06,270 --> 00:46:10,400
Si es falso, eso significa que vamos a querer imprimir algún tipo de mensaje

544
00:46:10,400 --> 00:46:14,390
y salga del programa.

545
00:46:14,390 --> 00:46:18,530
Lo que queremos hacer es comprobar el valor devuelto de foo.

546
00:46:18,530 --> 00:46:23,310
Si foo devuelve false, entonces sabemos que nos encontramos con algún tipo de error

547
00:46:23,310 --> 00:46:25,110
y tenemos que salir de nuestro programa.

548
00:46:25,110 --> 00:46:35,600
Una manera de hacer esto es tener una condición donde la función en sí es su condición.

549
00:46:35,600 --> 00:46:39,320
Diga foo toma en x.

550
00:46:39,320 --> 00:46:43,390
Podemos tener como condición if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Básicamente, esto significa que si al final de la ejecución de foo devuelve verdadero,

552
00:46:50,900 --> 00:46:57,390
entonces no podemos hacer esto porque la función tiene que evaluar foo

553
00:46:57,390 --> 00:47:00,500
con el fin de evaluar la condición general.

554
00:47:00,500 --> 00:47:06,500
Así que así es como se puede hacer algo si la función devuelve cierto y es un éxito.

555
00:47:06,500 --> 00:47:11,800
Pero cuando uno es la comprobación de errores, sólo quieren dejar de fumar si su función devuelve false.

556
00:47:11,800 --> 00:47:16,090
Lo que podría hacer es añadir un == false o simplemente añadir una explosión en frente de ella

557
00:47:16,090 --> 00:47:21,010
y luego tienes if (! foo).

558
00:47:21,010 --> 00:47:29,540
Dentro de ese conjunto de condiciones que usted tendría todo el control de errores,

559
00:47:29,540 --> 00:47:36,940
así como, "No se pudo crear este árbol" y luego devolver 1 o algo por el estilo.

560
00:47:36,940 --> 00:47:43,340
Lo que hace, sin embargo, es que a pesar de foo devuelto false -

561
00:47:43,340 --> 00:47:46,980
Diga foo devuelve true.

562
00:47:46,980 --> 00:47:51,060
Entonces usted no tiene que llamar a foo nuevo. Eso es un error común.

563
00:47:51,060 --> 00:47:54,730
Debido a que fue en su condición, ya está evaluado,

564
00:47:54,730 --> 00:47:59,430
por lo que ya tienen el resultado si usted está usando make árbol o algo por el estilo

565
00:47:59,430 --> 00:48:01,840
o de la planta o de la selección o algo así.

566
00:48:01,840 --> 00:48:07,460
Ya tiene ese valor. Ya está ejecutado.

567
00:48:07,460 --> 00:48:10,730
Así que es útil el uso de funciones booleanas como la condición

568
00:48:10,730 --> 00:48:13,890
porque si en realidad se ejecuta el cuerpo del bucle,

569
00:48:13,890 --> 00:48:18,030
ejecuta la función de todos modos.

570
00:48:22,070 --> 00:48:27,330
>> Nuestro segundo a último paso es escribir el mensaje en el archivo.

571
00:48:27,330 --> 00:48:33,070
Una vez que construir el árbol de Huffman, a continuación, escribir el mensaje en el archivo es bastante sencillo.

572
00:48:33,070 --> 00:48:39,260
Es bastante sencillo ahora a seguir sólo el 0 y 1.

573
00:48:39,260 --> 00:48:45,480
Y así, por convención, se sabe que en un árbol de Huffman los 0 Indique izquierdo

574
00:48:45,480 --> 00:48:48,360
y el 1s indicar derecha.

575
00:48:48,360 --> 00:48:53,540
Así que si usted lee en poco a poco, cada vez que se obtiene un 0

576
00:48:53,540 --> 00:48:59,100
podrás seguir la rama izquierda, y luego cada vez que se lee en un 1

577
00:48:59,100 --> 00:49:02,100
usted va a seguir la rama derecha.

578
00:49:02,100 --> 00:49:07,570
Y entonces usted va a continuar hasta llegar a una hoja

579
00:49:07,570 --> 00:49:11,550
porque las hojas van a estar en el extremo de las ramas.

580
00:49:11,550 --> 00:49:16,870
¿Cómo podemos saber si nos hemos topado con una hoja o no?

581
00:49:19,800 --> 00:49:21,690
Lo hemos dicho antes.

582
00:49:21,690 --> 00:49:24,040
[Estudiante] Si los punteros son NULL. Sí >>.

583
00:49:24,040 --> 00:49:32,220
Podemos saber si nos hemos topado con una hoja si los punteros a los árboles de la izquierda y la derecha son NULL.

584
00:49:32,220 --> 00:49:34,110
Perfecto.

585
00:49:34,110 --> 00:49:40,320
Sabemos que queremos leer en poco a poco en nuestro archivo de Huff.

586
00:49:43,870 --> 00:49:51,220
Como vimos antes en dump.c, lo que hicieron es que leen en poco a poco en el archivo de Huff

587
00:49:51,220 --> 00:49:54,560
y acaba de imprimir lo que los bits eran.

588
00:49:54,560 --> 00:49:58,430
No vamos a estar haciendo eso. Vamos a estar haciendo algo que es un poco más complejo.

589
00:49:58,430 --> 00:50:03,620
Pero lo que podemos hacer es que podemos tomar ese trozo de código que lee a la broca.

590
00:50:03,620 --> 00:50:10,250
Aquí tenemos el bit entero que representa el bit actual que estamos.

591
00:50:10,250 --> 00:50:15,520
Este se encarga de la iteración de todos los bits en el archivo hasta que llegue al final del archivo.

592
00:50:15,520 --> 00:50:21,270
Basado en esto, entonces usted va a querer tener algún tipo de iterador

593
00:50:21,270 --> 00:50:26,760
para recorrer el árbol.

594
00:50:26,760 --> 00:50:31,460
Y a continuación, en función de si el bit es 0 o 1,

595
00:50:31,460 --> 00:50:36,920
usted va a querer mover cualquiera que iterador hacia la izquierda o moverlo a la derecha

596
00:50:36,920 --> 00:50:44,080
todo el camino hasta llegar a una hoja, por lo que todo el camino hasta ese nodo que está en

597
00:50:44,080 --> 00:50:48,260
no apunta a ningún nodos más.

598
00:50:48,260 --> 00:50:54,300
¿Por qué le vamos a hacer esto con un archivo de Huffman, pero no el código Morse?

599
00:50:54,300 --> 00:50:56,610
Porque en código Morse que hay un poco de ambigüedad.

600
00:50:56,610 --> 00:51:04,440
Podríamos ser como, oh espera, nos hemos topado con una carta en el camino, así que tal vez esta es nuestra carta,

601
00:51:04,440 --> 00:51:08,150
mientras que si seguimos un poco más, entonces habría golpeado otra carta.

602
00:51:08,150 --> 00:51:13,110
Pero eso no va a suceder en la codificación Huffman,

603
00:51:13,110 --> 00:51:17,540
por lo que podemos estar seguros de que la única manera que vamos a golpear un carácter

604
00:51:17,540 --> 00:51:23,480
es si los hijos izquierdo y derecho que nodo son NULL.

605
00:51:28,280 --> 00:51:32,350
>> Por último, queremos liberar a todos de nuestra memoria.

606
00:51:32,350 --> 00:51:37,420
Queremos tanto a cerrar el archivo Huff que hemos estado tratando con

607
00:51:37,420 --> 00:51:41,940
así como eliminar todos los árboles de nuestro bosque.

608
00:51:41,940 --> 00:51:46,470
De acuerdo con su aplicación, usted está probablemente va a querer llamar quitar bosque

609
00:51:46,470 --> 00:51:49,780
lugar de realmente ir a través de todos los árboles usted mismo.

610
00:51:49,780 --> 00:51:53,430
Pero si usted hizo los árboles temporales, tendrá que liberar a eso.

611
00:51:53,430 --> 00:51:59,060
Usted sabe que su mejor código, para que sepa dónde está la asignación de memoria.

612
00:51:59,060 --> 00:52:04,330
Así que si vas en, comience incluso para el Control f'ing malloc,

613
00:52:04,330 --> 00:52:08,330
viendo cada vez que malloc y asegurarse de que te libere de todo eso

614
00:52:08,330 --> 00:52:10,190
pero entonces sólo va a través de su código,

615
00:52:10,190 --> 00:52:14,260
entender en las que podría haber asignado la memoria.

616
00:52:14,260 --> 00:52:21,340
Por lo general, usted podría decir: "Al final de un archivo que sólo voy a quitar mi bosque en bosque"

617
00:52:21,340 --> 00:52:23,850
así que básicamente borrar ese recuerdo, sin que,

618
00:52:23,850 --> 00:52:28,310
"Y entonces yo también voy a cerrar el archivo y entonces mi programa va a dejar de fumar."

619
00:52:28,310 --> 00:52:33,810
Pero es que la única vez que el programa se cierra?

620
00:52:33,810 --> 00:52:37,880
No, porque a veces puede haber habido un error que ocurrió.

621
00:52:37,880 --> 00:52:42,080
Tal vez no hemos podido abrir un archivo o no podíamos hacer otra árbol

622
00:52:42,080 --> 00:52:49,340
o algún tipo de error ocurrido en el proceso de asignación de memoria y así lo devolvió NULL.

623
00:52:49,340 --> 00:52:56,710
Un error ocurrió y luego volvimos y dejar de fumar.

624
00:52:56,710 --> 00:53:02,040
Así que usted quiere asegurarse de que cualquier momento es posible que el programa puede dejar de fumar,

625
00:53:02,040 --> 00:53:06,980
desea liberar toda la memoria allí.

626
00:53:06,980 --> 00:53:13,370
No sólo va a estar en la final de la función principal que sale de su código.

627
00:53:13,370 --> 00:53:20,780
¿Quieres ver de nuevo a todos los casos que el código potencialmente podría regresar antes de tiempo

628
00:53:20,780 --> 00:53:25,070
y luego liberar la memoria todo lo que tiene sentido.

629
00:53:25,070 --> 00:53:30,830
Diga que lo había llamado a hacer del bosque y que devuelve false.

630
00:53:30,830 --> 00:53:34,230
Entonces probablemente no tendrá que quitar su bosque

631
00:53:34,230 --> 00:53:37,080
porque usted no tiene un bosque todavía.

632
00:53:37,080 --> 00:53:42,130
Pero en todos los puntos del código en el que podría regresar antes de tiempo

633
00:53:42,130 --> 00:53:46,160
usted querrá asegurarse de que usted liberar cualquier memoria posible.

634
00:53:46,160 --> 00:53:50,020
>> Así que cuando nos enfrentamos a la liberación de memoria y tener fugas potenciales,

635
00:53:50,020 --> 00:53:55,440
Queremos no sólo utilizaremos nuestro juicio y nuestra lógica

636
00:53:55,440 --> 00:54:01,850
sino también utilizar Valgrind para determinar si se ha liberado toda nuestra memoria correctamente o no.

637
00:54:01,850 --> 00:54:09,460
Puede ejecutar Valgrind en Puff y entonces usted tiene que pasar también

638
00:54:09,460 --> 00:54:14,020
el número correcto de argumentos de línea de comandos para Valgrind.

639
00:54:14,020 --> 00:54:18,100
Puedes correr, pero la salida es un poco críptico.

640
00:54:18,100 --> 00:54:21,630
Nos hemos vuelto un poco acostumbrado a ello con el revisor ortográfico, pero todavía necesitamos la ayuda de un poco más,

641
00:54:21,630 --> 00:54:26,450
por lo que también se ejecuta con algunas banderas más como la fuga-check = completo,

642
00:54:26,450 --> 00:54:32,040
que probablemente nos va a dar una salida más útil sobre Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Luego, otro consejo útil cuando se está depurando es el comando diff.

644
00:54:39,040 --> 00:54:48,520
Puede acceder a la aplicación al personal de Huff, correr que en un archivo de texto,

645
00:54:48,520 --> 00:54:55,400
y luego la salida a un archivo binario, un archivo binario Huff, que es específica.

646
00:54:55,400 --> 00:54:59,440
Entonces si ejecuta su propio soplo sobre ese archivo binario,

647
00:54:59,440 --> 00:55:03,950
entonces lo ideal, el archivo de texto de salida tipo va a ser idéntico

648
00:55:03,950 --> 00:55:08,200
a la original que pasa pulg

649
00:55:08,200 --> 00:55:15,150
Aquí estoy usando hth.txt como ejemplo, y esa es la que se habla en su especificación.

650
00:55:15,150 --> 00:55:21,040
Eso es, literalmente, sólo HTH y luego un salto de línea.

651
00:55:21,040 --> 00:55:30,970
Pero definitivamente se siente libre y que son sin duda anima a utilizar más ejemplos

652
00:55:30,970 --> 00:55:32,620
para el archivo de texto.

653
00:55:32,620 --> 00:55:38,110
>> Usted puede incluso tomar una foto en tal vez la compresión y descompresión de entonces

654
00:55:38,110 --> 00:55:41,600
algunos de los archivos que se utilizan en Speller como Guerra y Paz

655
00:55:41,600 --> 00:55:46,710
o Jane Austen o algo por el estilo - que sería una especie de fresco - o Austin Powers,

656
00:55:46,710 --> 00:55:51,880
tipo de tratar con archivos más grandes, ya que no habría llegado hasta él

657
00:55:51,880 --> 00:55:55,590
si usamos la siguiente herramienta aquí, ls-l.

658
00:55:55,590 --> 00:56:01,150
Estamos acostumbrados a ls, que básicamente muestra todos los contenidos en nuestro directorio actual.

659
00:56:01,150 --> 00:56:07,860
Al pasar por la bandera-l en realidad muestra el tamaño de los archivos.

660
00:56:07,860 --> 00:56:12,690
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,

661
00:56:12,690 --> 00:56:16,590
de soplar, y se ve que para archivos muy pequeños

662
00:56:16,590 --> 00:56:23,910
el coste del espacio de comprimirlo y traducir toda esa información

663
00:56:23,910 --> 00:56:26,980
de todas las frecuencias y cosas por el estilo que sea mayor que el beneficio real

664
00:56:26,980 --> 00:56:30,000
de comprimir el archivo en el primer lugar.

665
00:56:30,000 --> 00:56:37,450
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

666
00:56:37,450 --> 00:56:40,930
en la compresión de los archivos.

667
00:56:40,930 --> 00:56:46,210
>> Y, finalmente, tenemos a nuestro viejo amigo GDB, que sin duda va a ser muy útil también.

668
00:56:48,360 --> 00:56:55,320
>> ¿Tenemos alguna pregunta sobre los árboles Huff o el proceso tal vez de hacer que los árboles

669
00:56:55,320 --> 00:56:58,590
o cualquier otra pregunta sobre Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Bien. Me quedaré alrededor para un poco.

671
00:57:02,570 --> 00:57:06,570
>> Gracias a todos. Esto era Tutorial 6. Y buena suerte.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]