1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Paso a paso - conxunto 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 é CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Ola, todos, e ben benvida ao Paso a paso 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
En Puff Huff'n o que estamos facendo vai estar lidando con un arquivo comprimido Huffman

6
00:00:17,440 --> 00:00:20,740
e despois golpe-lo de volta para descompactá-lo,

7
00:00:20,740 --> 00:00:25,810
para que poidamos traducir do 0s e 1s que o usuario envía-nos

8
00:00:25,810 --> 00:00:30,660
e convertela-lo de volta para o texto orixinal.

9
00:00:30,660 --> 00:00:34,360
Pset 6 vai ser moi legal porque está indo a ver algunhas das ferramentas

10
00:00:34,360 --> 00:00:41,730
que usou na pset 4 e 5 e pset tipo de combina-los nun concepto moi ordenado

11
00:00:41,730 --> 00:00:43,830
cando chegou a pensar sobre iso.

12
00:00:43,830 --> 00:00:50,110
>> Ademais, sen dúbida, pset 4 e 5 foron os máis reto serie de exercicios que tiñamos para ofrecer.

13
00:00:50,110 --> 00:00:53,950
Entón, a partir de agora, temos esa pset un máis en C,

14
00:00:53,950 --> 00:00:56,480
e despois diso que estamos diante de programación web.

15
00:00:56,480 --> 00:01:02,310
Entón felicitar-vos para estar máis a máis difícil corcova na CS50.

16
00:01:03,630 --> 00:01:09,760
>> Pasando para Puff Huff'n, a nosa caixa de ferramentas a este pset van ser árbores Huffman,

17
00:01:09,760 --> 00:01:14,700
para a comprensión non só como traballo árbores binarias, pero tamén árbores especialmente Huffman,

18
00:01:14,700 --> 00:01:16,240
como son construídos.

19
00:01:16,240 --> 00:01:20,210
E entón nós imos ter un monte de código distribución neste pset,

20
00:01:20,210 --> 00:01:22,480
e nós imos chegar a ver que, en realidade, parte do código

21
00:01:22,480 --> 00:01:24,670
Podemos non ser capaces de comprender plenamente aínda,

22
00:01:24,670 --> 00:01:30,080
e así eses serán os ficheiros. C, pero despois os seus acompañantes. arquivos h

23
00:01:30,080 --> 00:01:34,300
nos dará o suficiente comprensión de que necesitamos para que poidamos saber como esas funcións funcionan

24
00:01:34,300 --> 00:01:38,100
ou polo menos o que se quere facer - as súas entradas e saídas -

25
00:01:38,100 --> 00:01:40,760
mesmo se non sabemos o que está a suceder na caixa negra

26
00:01:40,760 --> 00:01:44,090
ou non entenden o que está a suceder na caixa negra dentro.

27
00:01:44,090 --> 00:01:49,400
E entón, finalmente, como de costume, estamos a tratar con estruturas de datos novos,

28
00:01:49,400 --> 00:01:51,840
tipos específicos de nós que ligan con certas cousas,

29
00:01:51,840 --> 00:01:56,080
e por iso aquí ter unha pluma e un papel non só para o proceso de deseño

30
00:01:56,080 --> 00:01:58,470
e cando está tentando descubrir como o seu pset debe funcionar

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

32
00:02:00,520 --> 00:02:06,140
Pode ter GDB á beira da súa pluma e papel, mentres toma para abaixo o que os valores son,

33
00:02:06,140 --> 00:02:09,320
onde as súas frechas están apuntando, e cousas así.

34
00:02:09,320 --> 00:02:13,720
>> En primeiro lugar, imos ollar para as árbores Huffman.

35
00:02:13,720 --> 00:02:19,600
Árbores Huffman son árbores binarias, o que significa que cada nodo só ten 2 fillos.

36
00:02:19,600 --> 00:02:24,870
En árbores Huffman característica é a de que os valores máis frecuentes

37
00:02:24,870 --> 00:02:27,140
son representados por menor número de bits.

38
00:02:27,140 --> 00:02:32,690
Nós vimos nos exemplos de conferencias do Código Morse, que tipo de consolidada algunhas letras.

39
00:02:32,690 --> 00:02:38,030
Se está tentando traducir un A ou E, por exemplo,

40
00:02:38,030 --> 00:02:43,940
está traducindo que, moitas veces, entón en vez de ter que usar todo o conxunto de bits

41
00:02:43,940 --> 00:02:48,640
alocados para ese tipo de datos de costume, comprimi-lo para abaixo, a menos,

42
00:02:48,640 --> 00:02:53,730
e despois as cartas que son representados con menos frecuencia son representados con anacos máis longos

43
00:02:53,730 --> 00:02:59,840
porque pode pagar que cando pesar as frecuencias que estas letras aparecen.

44
00:02:59,840 --> 00:03:03,020
Temos a mesma idea aquí en árbores Huffman

45
00:03:03,020 --> 00:03:12,360
onde estamos facendo unha corrente, unha especie de camiño para chegar aos personaxes certas.

46
00:03:12,360 --> 00:03:14,470
E entón os personaxes que teñen máis frecuencia

47
00:03:14,470 --> 00:03:17,940
vai ser representado con menor número de bits.

48
00:03:17,940 --> 00:03:22,020
>> O xeito que construír unha árbore de Huffman

49
00:03:22,020 --> 00:03:27,430
é a colocación de todos os personaxes que aparecen no texto

50
00:03:27,430 --> 00:03:30,630
e calcular a súa frecuencia, cantas veces aparecen.

51
00:03:30,630 --> 00:03:33,880
Isto podería ser unha conta de cantas veces as letras aparecen

52
00:03:33,880 --> 00:03:40,270
ou quizais unha porcentaxe de fóra de todos os personaxes cantos cada un aparece.

53
00:03:40,270 --> 00:03:44,270
E entón o que fai é cando ten todo isto para fóra mapeado,

54
00:03:44,270 --> 00:03:49,060
entón mira para as dúas frecuencias máis baixas e despois Xunta-los como irmáns

55
00:03:49,060 --> 00:03:55,660
onde, entón, o nodo pai ten unha frecuencia que é a suma dos seus dous fillos.

56
00:03:55,660 --> 00:04:00,870
E entón por convención dicir que o nodo esquerdo,

57
00:04:00,870 --> 00:04:03,770
vostede segue que, seguindo a rama 0,

58
00:04:03,770 --> 00:04:08,140
e despois o nó máis á dereita é a rama 1.

59
00:04:08,140 --> 00:04:16,040
Como vimos en código Morse, o único pegadinha é que, se tivese só un bip e bip

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

61
00:04:18,120 --> 00:04:22,430
Podería ser unha letra ou pode ser unha secuencia de dúas letras.

62
00:04:22,430 --> 00:04:27,790
E entón o que Huffman árbores fai é porque, por natureza dos personaxes

63
00:04:27,790 --> 00:04:34,140
ou finais nosos personaxes reais, sendo os nos últimos no sector -

64
00:04:34,140 --> 00:04:39,300
nos referimos aos que como as follas - en virtude de que non pode haber ningún ambigüidade

65
00:04:39,300 --> 00:04:45,160
en termos de que a letra que está intentando codificar coa serie de bits

66
00:04:45,160 --> 00:04:50,670
porque en ningún lugar ao longo dos bits que representan unha carta

67
00:04:50,670 --> 00:04:55,960
vai atopar outra carta enteira, e non haberá ningunha confusión alí.

68
00:04:55,960 --> 00:04:58,430
Pero imos entrar en exemplos que vostedes poden realmente ver que

69
00:04:58,430 --> 00:05:02,120
en vez de simplemente dicindo que iso é verdade.

70
00:05:02,120 --> 00:05:06,390
>> Vexamos un exemplo simple de unha árbore de Huffman.

71
00:05:06,390 --> 00:05:09,380
Eu teño unha secuencia aquí que é de 12 carácteres.

72
00:05:09,380 --> 00:05:14,010
Eu teño 4 Como, 6 BS, Cs e 2.

73
00:05:14,010 --> 00:05:17,270
O meu primeiro paso sería contar.

74
00:05:17,270 --> 00:05:20,760
Cantas veces é que unha opinión? Aparece catro veces na secuencia.

75
00:05:20,760 --> 00:05:25,060
B aparece 6 veces, e C é exhibida dúas veces.

76
00:05:25,060 --> 00:05:28,970
Por suposto, eu vou dicir que estou usando B na maioría das veces,

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

78
00:05:35,970 --> 00:05:42,600
E entón eu tamén vou esperar C para esixir a maior cantidade de 0s e 1s tamén.

79
00:05:42,600 --> 00:05:48,550
Primeiro o que eu fixen aquí é que eu colocaba en orde crecente en termos de frecuencia.

80
00:05:48,550 --> 00:05:52,710
Vemos que o C e A, esas son as nosas dúas frecuencias máis baixas.

81
00:05:52,710 --> 00:06:00,290
Creamos un nó pai, e que o nodo pai non ten unha carta a ela asociados,

82
00:06:00,290 --> 00:06:05,070
pero ten unha frecuencia, que é a suma.

83
00:06:05,070 --> 00:06:08,780
A suma torna-se 2 + 4, o cal é 6.

84
00:06:08,780 --> 00:06:10,800
Entón, seguimos a rama esquerda.

85
00:06:10,800 --> 00:06:14,970
Se estivésemos naquel no 6, entón poderiamos seguir 0 para chegar a C

86
00:06:14,970 --> 00:06:17,450
e, a continuación, 1 para a A.

87
00:06:17,450 --> 00:06:20,300
Polo tanto, agora temos dous nós.

88
00:06:20,300 --> 00:06:23,920
Temos o valor 6 e despois tamén temos outro no co valor 6.

89
00:06:23,920 --> 00:06:28,550
E así os dous non son só o menor 2, pero tamén a só 2 que sobraron,

90
00:06:28,550 --> 00:06:33,820
para que unirse aos que por outro pai, coa suma sendo 12.

91
00:06:33,820 --> 00:06:36,300
Polo tanto, temos aquí a nosa árbore de Huffman

92
00:06:36,300 --> 00:06:40,020
onde para chegar a B, que sería só o bit 1

93
00:06:40,020 --> 00:06:45,430
e, a continuación, para chegar a un teriamos 01 e, a continuación, C con 00.

94
00:06:45,430 --> 00:06:51,300
Entón aquí vemos que, basicamente, estamos representando estes chars con 1 ou 2 bits

95
00:06:51,300 --> 00:06:55,160
en que a B, como previsto, ten polo menos.

96
00:06:55,160 --> 00:07:01,730
E entón esperabamos C para ter máis, pero xa que é tal unha árbore de Huffman pequeno,

97
00:07:01,730 --> 00:07:06,020
entón o A é tamén representada por 2 bits en lugar de algures no medio.

98
00:07:07,820 --> 00:07:11,070
>> Só para pasar por riba de outro exemplo simple da árbore de Huffman,

99
00:07:11,070 --> 00:07:19,570
dicir que ten a cadea "Ola".

100
00:07:19,570 --> 00:07:25,360
O que é primeiro diría cantas veces H aparecer nesta?

101
00:07:25,360 --> 00:07:34,200
H aparece unha vez e logo e aparece unha vez e entón temos l aparecendo dúas veces

102
00:07:34,200 --> 00:07:36,580
é a aparición vez.

103
00:07:36,580 --> 00:07:44,310
E entón esperamos que carta a ser representado polo menor número de bits?

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

105
00:07:47,450 --> 00:07:50,730
Esperamos l ser representado por polo menos o número de bits

106
00:07:50,730 --> 00:07:55,890
porque eu se usa máis na cadea "Ola".

107
00:07:55,890 --> 00:08:04,280
O que eu vou facer agora é aproveitar eses nós.

108
00:08:04,280 --> 00:08:15,580
I ter 1, que é H, e, a continuación, outro 1, que é a e, a continuación, un 1, que é o -

109
00:08:15,580 --> 00:08:23,410
agora eu estou poñendo-os en orde - e, a continuación, 2, que é l.

110
00:08:23,410 --> 00:08:32,799
Entón eu digo o xeito que eu construír unha árbore de Huffman é atopar os dous nós coas menores frecuencias

111
00:08:32,799 --> 00:08:38,010
e sexa los irmáns creando un nodo pai.

112
00:08:38,010 --> 00:08:41,850
Aquí temos tres nós coa menor frecuencia. Son todos un.

113
00:08:41,850 --> 00:08:50,620
Entón aquí nós escoller cal imos chamar primeiro.

114
00:08:50,620 --> 00:08:54,850
Imos dicir que eu escoller o H e e.

115
00:08:54,850 --> 00:09:01,150
A suma de 1 + 1 e 2, pero este nó non ten unha carta a ela asociados.

116
00:09:01,150 --> 00:09:04,440
El só ten o valor.

117
00:09:04,440 --> 00:09:10,950
Agora imos ollar para os próximos 2 frecuencias máis baixas.

118
00:09:10,950 --> 00:09:15,590
Isto é 2 e 1. Isto podería ser un deses dous, pero eu vou escoller un regalo.

119
00:09:15,590 --> 00:09:18,800
A suma é 3.

120
00:09:18,800 --> 00:09:26,410
E entón, finalmente, eu só teño 2 esquerda, de modo que se fai entón 5.

121
00:09:26,410 --> 00:09:32,010
Entón, aquí, como esperaba, se eu encher a codificación para que,

122
00:09:32,010 --> 00:09:37,480
1s son sempre o brazo dereito e 0s son a esquerda.

123
00:09:37,480 --> 00:09:45,880
Entón temos l representadas por só un pouco e despois o por 2

124
00:09:45,880 --> 00:09:52,360
e, a continuación, o correo por 2 e, a continuación, o H cae 3 bits.

125
00:09:52,360 --> 00:09:59,750
Entón pode transmitir esta mensaxe "Ola" en vez de realmente usando os personaxes

126
00:09:59,750 --> 00:10:02,760
por só 0s e 1s.

127
00:10:02,760 --> 00:10:07,910
Con todo, lembre que en varios casos que lazos coa nosa frecuencia.

128
00:10:07,910 --> 00:10:11,900
Poderiamos ter ou xuntou o H e O primeiro quizais.

129
00:10:11,900 --> 00:10:15,730
Ou, máis tarde, cando tivemos a l representada por 2

130
00:10:15,730 --> 00:10:19,410
así como a que se xuntou un representado por 2, pódese ter ligado un ou outro.

131
00:10:19,410 --> 00:10:23,630
>> E así, cando envía os 0s e 1s, que en realidade non garante

132
00:10:23,630 --> 00:10:27,090
que o destinatario pode enteiramente ler a súa mensaxe pronto de cara

133
00:10:27,090 --> 00:10:30,490
porque poden non saber que a decisión que fixo.

134
00:10:30,490 --> 00:10:34,920
Entón, cando estamos lidando con compresión Huffman,

135
00:10:34,920 --> 00:10:40,090
de algunha maneira, debemos dicir o destinatario da nosa mensaxe como decidimos -

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

137
00:10:43,470 --> 00:10:46,580
ademais da mensaxe comprimida.

138
00:10:46,580 --> 00:10:51,490
Eles necesitan entender o que a árbore realmente parece,

139
00:10:51,490 --> 00:10:55,450
como realmente fixo estas decisións.

140
00:10:55,450 --> 00:10:59,100
>> Aquí foron só facendo exemplos baseados na conta real,

141
00:10:59,100 --> 00:11:01,550
pero ás veces pode ter tamén unha árbore de Huffman

142
00:11:01,550 --> 00:11:05,760
con base na frecuencia en que as letras aparecen, e é exactamente o mesmo proceso.

143
00:11:05,760 --> 00:11:09,090
Aquí estou expresando a en termos de porcentaxes ou fracción,

144
00:11:09,090 --> 00:11:11,290
e por iso aquí exactamente a mesma cousa.

145
00:11:11,290 --> 00:11:15,300
Creo menor 2, suma-los, o 2 menor seguinte suma-los,

146
00:11:15,300 --> 00:11:19,390
ata eu ter unha árbore chea.

147
00:11:19,390 --> 00:11:23,610
Aínda que puidésemos facelo de calquera xeito, cando estamos lidando con porcentaxes,

148
00:11:23,610 --> 00:11:27,760
iso significa que estamos dividindo as cousas e xestionar decimais ou mellor, flutúa

149
00:11:27,760 --> 00:11:30,900
se estamos a pensar en estruturas de datos dunha cabeza.

150
00:11:30,900 --> 00:11:32,540
O que sabemos sobre coches alegóricos?

151
00:11:32,540 --> 00:11:35,180
¿Que é un problema común cando estamos lidando con coches alegóricos?

152
00:11:35,180 --> 00:11:38,600
[Alumno] aritmética imprecisa. Si >>. Imprecisión.

153
00:11:38,600 --> 00:11:43,760
Por mor da imprecisión de punto flotante, a este pset para que comprobe se

154
00:11:43,760 --> 00:11:49,450
que non perdemos ningún valor, entón estamos realmente vai ser xestione o contador.

155
00:11:49,450 --> 00:11:54,880
Entón, se pensar en un nó Huffman, se ollar cara atrás, a estrutura aquí,

156
00:11:54,880 --> 00:12:01,740
Se ollar para os verdes que ten unha frecuencia asociada a el

157
00:12:01,740 --> 00:12:08,760
así como el apunta a un nodo polo seu lado esquerdo, así como un nó á dereita.

158
00:12:08,760 --> 00:12:13,970
E, a continuación, as pinturas teñen tamén un carácter que lles están asociados.

159
00:12:13,970 --> 00:12:18,900
Non imos facer os separados para os pais e, a continuación, os nodos finais,

160
00:12:18,900 --> 00:12:23,680
a que nos referimos como as follas, senón aqueles que só teñen valores nulos.

161
00:12:23,680 --> 00:12:31,050
Para cada nodo teremos un personaxe, o símbolo que representa ese nodo,

162
00:12:31,050 --> 00:12:40,490
a continuación, a frecuencia, así como un indicador para o seu fillo esquerdo, así como a súa neno dereita.

163
00:12:40,490 --> 00:12:45,680
As follas, que son ben no fondo, tamén tería punteiros nodo

164
00:12:45,680 --> 00:12:49,550
á súa esquerda e á súa dereita, pero sempre que estes valores non están apuntando para nós reais,

165
00:12:49,550 --> 00:12:53,970
o que sería o seu valor ser? >> [Alumno] NULL. NULL. >> Exactamente.

166
00:12:53,970 --> 00:12:58,430
Aquí está un exemplo de como pode representar a miúdo en coches alegóricos,

167
00:12:58,430 --> 00:13:02,130
pero imos estar lidando con iso con números enteiros,

168
00:13:02,130 --> 00:13:06,780
entón todo o que eu fixen é cambiar o tipo de datos alí.

169
00:13:06,780 --> 00:13:09,700
>> Imos a un pouco máis de un exemplo complexo.

170
00:13:09,700 --> 00:13:13,360
Pero agora que temos feito as máis simples, é só o mesmo proceso.

171
00:13:13,360 --> 00:13:20,290
Vostede está as dúas frecuencias máis baixas, sumar as frecuencias

172
00:13:20,290 --> 00:13:22,450
e esa é a nova frecuencia do seu nodo pai

173
00:13:22,450 --> 00:13:29,310
que, entón, apunta a súa esquerda co ramo do dereito 0 e co sector 1.

174
00:13:29,310 --> 00:13:34,200
Se temos a cadea "Este é CS50," entón nós contar cantas veces é mencionado 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
Entón o que eu fixen aquí é os nós vermellos eu só plantas,

177
00:13:42,010 --> 00:13:48,530
Eu dixen que eu vou ter eses personaxes, eventualmente, na parte inferior da miña árbore.

178
00:13:48,530 --> 00:13:51,740
Aqueles van ser todas as follas.

179
00:13:51,740 --> 00:13:58,200
Entón o que eu fixen é que eu clasificados los pola frecuencia en orde crecente,

180
00:13:58,200 --> 00:14:02,950
e esta é realmente a forma que o código fai pset

181
00:14:02,950 --> 00:14:07,550
é el clasifica-lo por frecuencia e, a continuación, en orde alfabética.

182
00:14:07,550 --> 00:14:13,870
Por iso, ten os números primeiro e logo en orde alfabética polo miúdo.

183
00:14:13,870 --> 00:14:18,520
Entón o que me gustaría facer é que eu ía atopar a menor 2. Isto é 0 e 5.

184
00:14:18,520 --> 00:14:22,390
Quere suma-los, e iso é 2. Entón quere continuar, o seguinte 2 menor.

185
00:14:22,390 --> 00:14:26,100
Estes son os 1s dous, e, a continuación, os dous se fan tamén.

186
00:14:26,100 --> 00:14:31,570
Agora sei que o meu seguinte paso será engadir o menor número,

187
00:14:31,570 --> 00:14:41,380
Que é o T, 1, e en seguida, selecciona un dos nós que ten 2 como a miúdo.

188
00:14:41,380 --> 00:14:44,560
Polo tanto, temos aquí tres opcións.

189
00:14:44,560 --> 00:14:47,980
O que eu vou facer a foto é só visualmente reorganiza-los para ti

190
00:14:47,980 --> 00:14:51,790
de xeito que se pode ver como eu estou construíndo-o.

191
00:14:51,790 --> 00:14:59,040
O que o código eo código de distribución vai facer sería xuntar a unha T

192
00:14:59,040 --> 00:15:01,410
co nodo 0 e 5.

193
00:15:01,410 --> 00:15:05,060
Entón que resume a 3, e entón continuar o proceso.

194
00:15:05,060 --> 00:15:08,660
O 2 a 2 e agora son os máis baixos, de xeito entón aqueles suma a 4.

195
00:15:08,660 --> 00:15:12,560
Todos seguindo ata agora? Okay.

196
00:15:12,560 --> 00:15:16,410
A continuación, despois de que temos a 3 e 3 que necesitan ser engadidos,

197
00:15:16,410 --> 00:15:21,650
así outra vez eu estou só liga-lo de modo que pode ver visualmente, de forma que non quede moi confuso.

198
00:15:21,650 --> 00:15:25,740
Entón temos un 6, e entón o noso paso final é agora cando temos só 2 nós

199
00:15:25,740 --> 00:15:30,440
sumamos os para facer a base da nosa árbore, que é 10.

200
00:15:30,440 --> 00:15:34,100
E o número 10 ten sentido, porque cada nodo representado,

201
00:15:34,100 --> 00:15:40,750
o seu valor, o seu número de frecuencia, era cantas veces eles apareceron na secuencia,

202
00:15:40,750 --> 00:15:46,350
e entón temos 5 personaxes na nosa cadea, de xeito que ten sentido.

203
00:15:48,060 --> 00:15:52,320
Se ollar para coma nós, en realidade, codifica-lo,

204
00:15:52,320 --> 00:15:56,580
como esperaba, o I eo s, que aparecen con máis frecuencia

205
00:15:56,580 --> 00:16:01,350
son representados polo número mínimo de bits.

206
00:16:03,660 --> 00:16:05,660
>> Teña coidado aquí.

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

208
00:16:09,780 --> 00:16:13,670
Un S maiúsculo é distinto de un s minúsculo.

209
00:16:13,670 --> 00:16:21,260
Se tivésemos "Este é CS50" con letras maiúsculas, o s minúsculo só aparecen dúas veces,

210
00:16:21,260 --> 00:16:27,120
Sería un nó con 2 como o seu valor e, a continuación, S maiúsculo sería só unha vez.

211
00:16:27,120 --> 00:16:33,440
Entón a súa árbore cambiaría as estruturas, porque realmente ten unha folla extra aquí.

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

213
00:16:36,900 --> 00:16:39,570
Isto é o que estamos realmente vai ser chamar o checksum,

214
00:16:39,570 --> 00:16:44,060
a adición de todas as contas.

215
00:16:46,010 --> 00:16:50,990
>> Agora que nós Cubrimos árbores Huffman, podemos mergullar en Huff'n Puff, o pset.

216
00:16:50,990 --> 00:16:52,900
Nós imos comezar con unha sección de preguntas,

217
00:16:52,900 --> 00:16:57,990
e iso vai leva-lo acostumado con árbores binarias e como operar en torno a que:

218
00:16:57,990 --> 00:17:03,230
Nós deseño, creando a súa propia estrutura typedef a un nodo,

219
00:17:03,230 --> 00:17:07,230
e ver como pode inserir nunha árbore binaria, un que está clasificado,

220
00:17:07,230 --> 00:17:09,050
atravesando, e cousas así.

221
00:17:09,050 --> 00:17:14,560
Este coñecemento é sempre vai axudar cando mergulla na porción Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
do pset.

223
00:17:19,150 --> 00:17:26,329
Na edición estándar do pset, a súa tarefa é aplicar Puff,

224
00:17:26,329 --> 00:17:30,240
e na versión pirata súa tarefa é aplicar Huff.

225
00:17:30,240 --> 00:17:38,490
O Huff fai é que leva o texto e entón o traduce para os 0s e 1s,

226
00:17:38,490 --> 00:17:41,990
así o proceso que fixemos anteriormente, onde contamos as frecuencias

227
00:17:41,990 --> 00:17:50,970
e en seguida, fixo a árbore e, a continuación, dixo: "Como podo obter T?"

228
00:17:50,970 --> 00:17:54,840
T é representado por 100, cousas así,

229
00:17:54,840 --> 00:17:58,860
Huff e despois levaría o texto e, a continuación, saída que binario.

230
00:17:58,860 --> 00:18:04,920
Pero tamén porque sabemos que queremos facer que o noso destinatario da mensaxe

231
00:18:04,920 --> 00:18:11,790
para recrear a mesma árbore que, tamén inclúe información sobre as contas de frecuencia.

232
00:18:11,790 --> 00:18:17,980
Entón, con Puff nos é dado un arquivo binario de 0s e 1s

233
00:18:17,980 --> 00:18:21,740
e atendendo tamén á información sobre as frecuencias.

234
00:18:21,740 --> 00:18:26,740
Traducimos todo 0s e 1s de volta para a mensaxe orixinal que foi,

235
00:18:26,740 --> 00:18:29,350
por iso estamos descompactando iso.

236
00:18:29,350 --> 00:18:36,450
Se está facendo a edición estándar, non aplicar Huff,

237
00:18:36,450 --> 00:18:39,290
, Entón podes simplemente usar a aplicación equipo de Huff.

238
00:18:39,290 --> 00:18:42,080
Hai instrucións na especificación de como facelo.

239
00:18:42,080 --> 00:18:48,780
Pode realizar a implementación equipo de Huff enriba dun arquivo de texto certa

240
00:18:48,780 --> 00:18:53,270
e despois usar esta saída como a súa entrada para Puff.

241
00:18:53,270 --> 00:18:59,330
>> Cómo mencionen antes, temos unha morea de código de distribución a este.

242
00:18:59,330 --> 00:19:01,810
Vou comezar a pasar por iso.

243
00:19:01,810 --> 00:19:04,400
Vou pasar a maior parte do tempo no. Arquivos h

244
00:19:04,400 --> 00:19:07,660
porque nos arquivos. c, porque temos o h.

245
00:19:07,660 --> 00:19:11,650
e que nos ofrece os prototipos de funcións,

246
00:19:11,650 --> 00:19:15,520
non é totalmente precisa entender exactamente -

247
00:19:15,520 --> 00:19:20,280
Se non entende o que está a suceder nos arquivos. C, entón non se preocupe moito,

248
00:19:20,280 --> 00:19:23,600
pero sempre tentar dar un ollo porque pode dar algúns consellos

249
00:19:23,600 --> 00:19:29,220
e é útil para acostumar lectura de código de outras persoas.

250
00:19:38,940 --> 00:19:48,270
>> Mirando huffile.h, nos comentarios que declara unha capa de abstracción para Huffman codificados arquivos.

251
00:19:48,270 --> 00:20:01,660
Se descermos, vemos que hai un máximo de 256 símbolos que podemos ter códigos para.

252
00:20:01,660 --> 00:20:05,480
Isto inclúe todas as letras do alfabeto - maiúsculas e minúsculas -

253
00:20:05,480 --> 00:20:08,250
e, a continuación, os símbolos e números, etc

254
00:20:08,250 --> 00:20:11,930
Entón aquí temos un número máxico identificar un ficheiro Huffman-codificado.

255
00:20:11,930 --> 00:20:15,890
Dentro dun código de Huffman eles van ter un número de certa maxia

256
00:20:15,890 --> 00:20:18,560
asociados a cabeceira.

257
00:20:18,560 --> 00:20:21,110
Isto pode parecer só un número máxico ao chou,

258
00:20:21,110 --> 00:20:27,160
pero se realmente traducir-lo en ASCII, entón realmente explicita Huff.

259
00:20:27,160 --> 00:20:34,290
Aquí temos unha estrutura para un ficheiro Huffman-codificado.

260
00:20:34,290 --> 00:20:39,670
Hai todas estas características asociadas cun ficheiro de Huff.

261
00:20:39,670 --> 00:20:47,080
Entón aquí temos a cabeceira dun arquivo de Huff, por iso nós dicimos que Huffeader

262
00:20:47,080 --> 00:20:50,810
en vez de engadir o h extra porque parece o mesmo de calquera maneira.

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

264
00:20:52,720 --> 00:20:57,790
Temos un número máxico asociado a el.

265
00:20:57,790 --> 00:21:09,040
Se é un ficheiro de Huff real, que vai ser o número anterior, esta maxia.

266
00:21:09,040 --> 00:21:14,720
E entón el vai ter unha matriz.

267
00:21:14,720 --> 00:21:18,750
Así, para cada símbolo, dos cales existen 256,

268
00:21:18,750 --> 00:21:24,760
vai incluír o que a frecuencia destes símbolos están dentro do ficheiro de Huff.

269
00:21:24,760 --> 00:21:28,090
E entón, finalmente, temos unha suma de verificación para as frecuencias,

270
00:21:28,090 --> 00:21:32,160
cal debe ser a suma destas frecuencias.

271
00:21:32,160 --> 00:21:36,520
Entón é iso que un Huffeader é.

272
00:21:36,520 --> 00:21:44,600
Entón, temos algunhas funcións que retornan ao seguinte bit no arquivo Huff

273
00:21:44,600 --> 00:21:52,580
así como escribe algo para o ficheiro de Huff, e entón esta función aquí, hfclose,

274
00:21:52,580 --> 00:21:54,650
que realmente pecha o ficheiro Huff.

275
00:21:54,650 --> 00:21:57,290
Antes, estabamos lidando con recta só fclose,

276
00:21:57,290 --> 00:22:01,190
pero cando ten un arquivo de Huff, en vez de fclosing

277
00:22:01,190 --> 00:22:06,080
o que en realidade está indo facer é hfclose e hfopen-lo.

278
00:22:06,080 --> 00:22:13,220
Esas son funcións específicas para os ficheiros de Huff que imos tratar.

279
00:22:13,220 --> 00:22:19,230
Entón aquí nós lemos na cabeceira e logo escribir a cabeceira.

280
00:22:19,230 --> 00:22:25,700
>> Só lendo o. Arquivo h podemos tipo de obter unha noción do que un arquivo pode ser Huff,

281
00:22:25,700 --> 00:22:32,480
cales as características que ten, sen realmente ir ao huffile.c,

282
00:22:32,480 --> 00:22:36,750
que, se mergullar, vai ser un pouco máis complexa.

283
00:22:36,750 --> 00:22:41,270
El ten todo o arquivo I / O lidando aquí con punteiros.

284
00:22:41,270 --> 00:22:48,010
Aquí vemos que cando chamamos hfread, por exemplo, que aínda está lidando con fread.

285
00:22:48,010 --> 00:22:53,050
Non vai se librar destas funcións totalmente, pero estamos enviando as medidas a tomar conta de

286
00:22:53,050 --> 00:22:59,760
dentro do arquivo Huff en vez de facer todo nós mesmos.

287
00:22:59,760 --> 00:23:02,300
Pode sentirse libre para facer a pescudas a través deste se está curioso

288
00:23:02,300 --> 00:23:08,410
e ir descascada a capa de volta un pouco.

289
00:23:20,650 --> 00:23:24,060
>> O seguinte ficheiro que imos ollar é tree.h.

290
00:23:24,060 --> 00:23:30,210
Antes do paso a paso desliza dixemos que esperar un nodo Huffman

291
00:23:30,210 --> 00:23:32,960
e fixemos un nó typedef struct.

292
00:23:32,960 --> 00:23:38,360
Esperamos que ten un símbolo, unha frecuencia, e despois dúas estrelas no.

293
00:23:38,360 --> 00:23:41,870
Neste caso, o que estamos facendo é que este é esencialmente o mesmo

294
00:23:41,870 --> 00:23:46,880
excepto en vez de nodo imos chamalos de árbores.

295
00:23:48,790 --> 00:23:56,760
Temos unha función que cando chamar facer árbore que retorna un punteiro de árbore.

296
00:23:56,760 --> 00:24:03,450
Volver Speller, cando estaba facendo un novo nodo

297
00:24:03,450 --> 00:24:11,410
vostede dixo no palabra * novo = malloc (sizeof) e cousas así.

298
00:24:11,410 --> 00:24:17,510
Basicamente, mktree vai ser tratar con isto para ti.

299
00:24:17,510 --> 00:24:20,990
Do mesmo xeito, cando quere eliminar unha árbore,

300
00:24:20,990 --> 00:24:24,810
de xeito que é esencialmente liberar a árbore cando rematar con el,

301
00:24:24,810 --> 00:24:33,790
en vez de chamar explicitamente libre en que, en realidade está indo só para usar a función rmtree

302
00:24:33,790 --> 00:24:40,360
onde pasar o punteiro para a árbore e, a continuación, tree.c vai coidar diso para ti.

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

304
00:24:42,490 --> 00:24:47,240
Agardamos que as mesmas funcións, excepto para ver a execución tamén.

305
00:24:47,240 --> 00:24:57,720
Como esperabamos, cando chamalo mktree mallocs do tamaño dunha árbore nun punteiro,

306
00:24:57,720 --> 00:25:03,190
arrincar todos os valores para o valor NULL, así 0s ou nulos,

307
00:25:03,190 --> 00:25:08,280
e retorna o punteiro para a árbore que acaba de malloc'd para ti.

308
00:25:08,280 --> 00:25:13,340
Aquí cando chamar eliminar árbore primeiro asegura que non está liberando dobre.

309
00:25:13,340 --> 00:25:18,320
El asegura que realmente ten unha árbore que quere eliminar.

310
00:25:18,320 --> 00:25:23,330
Aquí porque unha árbore tamén inclúe os seus fillos,

311
00:25:23,330 --> 00:25:29,560
O que isto significa é que chama recursivamente eliminar árbore no nodo esquerdo da árbore

312
00:25:29,560 --> 00:25:31,650
así como o nó dereito.

313
00:25:31,650 --> 00:25:37,790
Antes que libera o pai, precisa liberar os fillos tamén.

314
00:25:37,790 --> 00:25:42,770
Pai tamén é intercambiable con raíz.

315
00:25:42,770 --> 00:25:46,500
O primeiro pai nunca, así como o gran-gran-gran-gran-avó

316
00:25:46,500 --> 00:25:52,130
ou árbore avoa, primeiro temos que liberarse os primeiros niveis.

317
00:25:52,130 --> 00:25:58,490
Entón, atravesar para o fondo, sen aqueles, e en seguida, volver-se, libre daqueles, etc

318
00:26:00,400 --> 00:26:02,210
Entón, iso é árbore.

319
00:26:02,210 --> 00:26:04,240
>> Agora imos ollar para bosque.

320
00:26:04,240 --> 00:26:09,860
Bosque é onde se pon todas as súas árbores de Huffman.

321
00:26:09,860 --> 00:26:12,910
Está dicindo que nós imos ter unha cousa chamada trama

322
00:26:12,910 --> 00:26:22,320
que contén un enlace a unha árbore, así como un indicador para unha trama chamada seguinte.

323
00:26:22,320 --> 00:26:28,480
Que estrutura fai este tipo de ollar como?

324
00:26:29,870 --> 00:26:32,490
É o tipo de di por aí.

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

326
00:26:37,340 --> 00:26:39,170
Unha lista ligada.

327
00:26:39,170 --> 00:26:44,590
Vemos que, cando temos unha trama que é como unha lista ligada de parcelas.

328
00:26:44,590 --> 00:26:53,020
O bosque é definida como unha lista ligada de parcelas,

329
00:26:53,020 --> 00:26:58,100
e así a estrutura do bosque é que estamos indo só para ter un punteiro para o noso primeiro lote

330
00:26:58,100 --> 00:27:02,740
e que a trama ten unha árbore dentro del, ou mellor apunta a unha árbore

331
00:27:02,740 --> 00:27:06,190
e, a continuación, apunta para o lote seguinte, así por diante e así por diante.

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

333
00:27:11,100 --> 00:27:14,930
Entón, temos algunhas funcións moi útiles aquí.

334
00:27:14,930 --> 00:27:23,240
Temos escoller onde pasa nun bosque e, a continuación, o valor de retorno é un * Árbore,

335
00:27:23,240 --> 00:27:25,210
un punteiro para unha árbore.

336
00:27:25,210 --> 00:27:29,370
O que vai facer é escoller vai para o bosque que está a apuntar cara

337
00:27:29,370 --> 00:27:35,240
a continuación, eliminar unha árbore coa menor frecuencia que o bosque

338
00:27:35,240 --> 00:27:38,330
e despois darlle o punteiro para esa árbore.

339
00:27:38,330 --> 00:27:43,030
Unha vez que chama a elixir, a árbore non vai existir no bosque máis,

340
00:27:43,030 --> 00:27:48,550
pero o valor de retorno é o punteiro para a árbore.

341
00:27:48,550 --> 00:27:50,730
Entón tes planta.

342
00:27:50,730 --> 00:27:57,420
Dende que pasar un punteiro para unha árbore que ten unha frecuencia non-0,

343
00:27:57,420 --> 00:28:04,040
que planta vai facer é que vai levar o bosque, tomar a árbore, e planta que árbore dentro do bosque.

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

345
00:28:06,370 --> 00:28:11,480
Similar para eliminar árbore, que, basicamente, liberou todos os nosos árbores para nós,

346
00:28:11,480 --> 00:28:16,600
eliminar bosque vai todo libre contida no bosque.

347
00:28:16,600 --> 00:28:24,890
>> Se olharmos para forest.c, imos esperar a ver polo menos un comando rmtree alí,

348
00:28:24,890 --> 00:28:30,090
porque a memoria libre no bosque unha bosque ten árbores que,

349
00:28:30,090 --> 00:28:32,930
despois, eventualmente, vai ter que eliminar as árbores tamén.

350
00:28:32,930 --> 00:28:41,020
Se olharmos para forest.c, temos a nosa mkforest, que é como esperamos.

351
00:28:41,020 --> 00:28:42,890
Nós malloc cousas.

352
00:28:42,890 --> 00:28:51,740
Nós arrincar a primeira parcela no bosque coma NULL porque está baleiro, para comezar,

353
00:28:51,740 --> 00:29:05,940
entón vemos cabeza, que retorna a árbore co menor peso, menor frecuencia,

354
00:29:05,940 --> 00:29:13,560
e entón se librar dese nó especial que apunta a que a árbore eo próximo,

355
00:29:13,560 --> 00:29:16,760
por iso é preciso que fóra da lista ligada do bosque.

356
00:29:16,760 --> 00:29:24,510
E entón aquí temos planta, que introduce unha árbore á lista ligada.

357
00:29:24,510 --> 00:29:29,960
O que mata non é así mantén clasificados para nós.

358
00:29:29,960 --> 00:29:37,910
E, a continuación, finalmente, temos rmforest e, como esperaba, temos chamado rmtree alí.

359
00:29:46,650 --> 00:29:55,440
>> Mirando cara o código de distribución, ata agora, huffile.c foi probablemente, de lonxe, o máis difícil de entender,

360
00:29:55,440 --> 00:29:59,990
mentres que os outros arquivos en si eran ben sinxelo de seguir.

361
00:29:59,990 --> 00:30:03,090
Co noso coñecemento de punteiros e listas ligadas e tal,

362
00:30:03,090 --> 00:30:04,860
fomos capaces de seguir moi ben.

363
00:30:04,860 --> 00:30:10,500
Pero todo o que necesitamos para realmente estar seguro de que entendemos plenamente. Son os arquivos h

364
00:30:10,500 --> 00:30:15,840
porque ten que estar chamando estas funcións, xestionar eses valores de retorno,

365
00:30:15,840 --> 00:30:20,590
para asegurarse que entendeu o que a acción vai ser realizada

366
00:30:20,590 --> 00:30:24,290
sempre que chamar a unha desas funcións.

367
00:30:24,290 --> 00:30:33,020
Pero, en realidade, a comprensión dentro do que non é absolutamente necesario, porque temos os. Arquivos h.

368
00:30:35,170 --> 00:30:39,490
Temos dous arquivos deixados no noso código de distribución.

369
00:30:39,490 --> 00:30:41,640
>> Imos ollar para despejo.

370
00:30:41,640 --> 00:30:47,230
Despejo polo seu comentario aquí leva un ficheiro Huffman-comprimido

371
00:30:47,230 --> 00:30:55,580
e, a continuación, traduce e depósitos de todo o seu contido para fóra.

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

373
00:31:04,260 --> 00:31:10,770
Esta é unha especie de espelhamento para o ficheiro de entrada * = fopen,

374
00:31:10,770 --> 00:31:13,500
e entón pasa a información.

375
00:31:13,500 --> 00:31:18,240
É case idéntico, excepto en vez de un * ficheiro que está pasando nun Huffile;

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

377
00:31:22,030 --> 00:31:29,280
Aquí lemos na cabeceira da primeira, que é unha especie de similar a como se le na cabeceira

378
00:31:29,280 --> 00:31:33,580
para un ficheiro bitmap.

379
00:31:33,580 --> 00:31:38,000
O que estamos facendo aquí é comprobar a ver se a información de cabeceira

380
00:31:38,000 --> 00:31:44,330
contén o número máxico dereito que indica que é un ficheiro de Huff real,

381
00:31:44,330 --> 00:31:53,610
a continuación, todas estas comprobacións para asegurarse de que o arquivo que está aberto un arquivo real xingou ou non.

382
00:31:53,610 --> 00:32:05,330
O que isto significa que xera as frecuencias de todos os símbolos que podemos ver

383
00:32:05,330 --> 00:32:09,790
dentro dun terminal para unha táboa gráfica.

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

385
00:32:15,240 --> 00:32:24,680
El ten un pouco e le pouco a pouco a pouco variable e imprime o.

386
00:32:28,220 --> 00:32:35,430
Entón, se eu fose chamar despejo en hth.bin, que é o resultado dun ficheiro huffing

387
00:32:35,430 --> 00:32:39,490
utilizando a solución persoal, quere obter isto.

388
00:32:39,490 --> 00:32:46,000
É a saída de todos eses personaxes e despois poñer a miúdo en que aparecen.

389
00:32:46,000 --> 00:32:51,180
Se miramos, a maioría deles son 0s excepto para iso: H, que aparece dúas veces,

390
00:32:51,180 --> 00:32:54,820
T e, a continuación, unha vez que aparece.

391
00:32:54,820 --> 00:33:07,860
E aquí temos a verdadeira mensaxe 0s e 1s.

392
00:33:07,860 --> 00:33:15,450
Se olharmos para hth.txt, que é probablemente a mensaxe orixinal que foi bufou,

393
00:33:15,450 --> 00:33:22,490
Esperamos ver algúns hs e Ts alí.

394
00:33:22,490 --> 00:33:28,720
Especificamente, esperamos ver só 1 T e 2 hs.

395
00:33:32,510 --> 00:33:37,440
Aquí estamos hth.txt. De feito, ten HTH.

396
00:33:37,440 --> 00:33:41,270
Incluído, aínda que non poidamos velo, é un carácter de nova liña.

397
00:33:41,270 --> 00:33:53,190
O hth.bin arquivo Huff tamén é a codificación de caracteres de nova liña tamén.

398
00:33:55,680 --> 00:34:01,330
Aquí porque sabemos que a orde é HTH e despois de nova liña,

399
00:34:01,330 --> 00:34:07,340
podemos ver que, probablemente, o H é representado por só un único 1

400
00:34:07,340 --> 00:34:17,120
e, a continuación, o T é probablemente 01 e, a continuación, o seguinte é un H, así

401
00:34:17,120 --> 00:34:21,139
e entón temos unha nova liña indicada por dous 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> E entón, finalmente, arquivos, porque estamos lidando con múltiples. C e. H,

404
00:34:31,600 --> 00:34:36,350
nós imos ter un argumento moi complexo para o compilador,

405
00:34:36,350 --> 00:34:40,460
e aquí temos un Makefile que fai despejo para ti.

406
00:34:40,460 --> 00:34:47,070
Pero, en realidade, ten que ir sobre como facer o seu propio arquivo puff.c.

407
00:34:47,070 --> 00:34:54,330
O Makefile en realidade, non se trata de facer puff.c para ti.

408
00:34:54,330 --> 00:34:59,310
Estamos deixando isto para vostede editar o Makefile.

409
00:34:59,310 --> 00:35:05,930
Cando escribe unha orde como facer todo, por exemplo, que vai facer todos eles para ti.

410
00:35:05,930 --> 00:35:10,760
Sinto-se libre para ollar os exemplos de Makefile das pset pasado

411
00:35:10,760 --> 00:35:17,400
así como saír dun agasallo para ver como pode ser capaz de facer o seu arquivo Puff

412
00:35:17,400 --> 00:35:20,260
editando este Makefile.

413
00:35:20,260 --> 00:35:22,730
É sobre iso para o noso código de distribución.

414
00:35:22,730 --> 00:35:28,380
>> Unha vez que temos obtido a través diso, entón aquí é só un recordatorio

415
00:35:28,380 --> 00:35:30,980
de como imos estar lidando cos nós Huffman.

416
00:35:30,980 --> 00:35:35,400
Non imos estar chamando-os de nós máis, nós imos estar chamando-os de árbores

417
00:35:35,400 --> 00:35:39,260
onde imos estar representando o seu símbolo cun char,

418
00:35:39,260 --> 00:35:43,340
a súa frecuencia, o número de ocorrencias, con un número enteiro.

419
00:35:43,340 --> 00:35:47,370
Estamos a usar iso porque é máis preciso que un coche alegórico.

420
00:35:47,370 --> 00:35:52,980
E entón temos outro punteiro para o fillo esquerdo, así como o dereito do neno.

421
00:35:52,980 --> 00:35:59,630
Un bosque, como vimos, é só unha lista encadeada de árbores.

422
00:35:59,630 --> 00:36:04,670
Por fin, cando estamos construíndo o noso arquivo Huff,

423
00:36:04,670 --> 00:36:07,580
queremos que a nosa bosque para conter unha árbore 1 -

424
00:36:07,580 --> 00:36:12,420
Unha árbore, unha raíz con varios fillos.

425
00:36:12,420 --> 00:36:20,840
A principios de cando estabamos facendo as nosas árbores de Huffman,

426
00:36:20,840 --> 00:36:25,360
comezamos por poñer todos os nós na nosa pantalla

427
00:36:25,360 --> 00:36:27,790
e dicindo que nós imos ter eses nós,

428
00:36:27,790 --> 00:36:32,920
finalmente, eles van ser as follas, e este é o seu símbolo, esta é a súa frecuencia.

429
00:36:32,920 --> 00:36:42,070
Na nosa bosque só temos 3 letras, que é un bosque de tres árbores.

430
00:36:42,070 --> 00:36:45,150
E entón, como imos, cando engadimos o primeiro pai,

431
00:36:45,150 --> 00:36:48,080
fixemos un bosque de dúas árbores.

432
00:36:48,080 --> 00:36:54,930
Nós eliminamos 2 dos nenos da nosa bosque e, a continuación, substitúe-lo con un nó pai

433
00:36:54,930 --> 00:36:58,820
que eses dous nós como fillos.

434
00:36:58,820 --> 00:37:05,600
E entón, finalmente, o noso último paso con facer o noso exemplo, o As, Bs e Cs

435
00:37:05,600 --> 00:37:08,030
sería facer o proxenitor final,

436
00:37:08,030 --> 00:37:13,190
e así, entón, que ía traer a nosa conta total de árbores no bosque para 1.

437
00:37:13,190 --> 00:37:18,140
Será que todo o mundo ver como comeza con varias árbores na súa bosque

438
00:37:18,140 --> 00:37:22,520
e acabar con un? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> O que necesitamos facer para Puff?

440
00:37:28,110 --> 00:37:37,110
O que necesitamos facer é garantir que, como sempre, eles nos dan o dereito tipo de entrada

441
00:37:37,110 --> 00:37:39,090
para que poidamos realmente executar o programa.

442
00:37:39,090 --> 00:37:43,130
Neste caso, eles van estar dando-nos logo do seu argumento de liña de comandos primeiro

443
00:37:43,130 --> 00:37:53,440
2 máis: o ficheiro que queremos descomprimir e saída do ficheiro descomprimido.

444
00:37:53,440 --> 00:38:00,410
Pero unha vez que temos a certeza de que eles pasan connosco a cantidade correcta de valores,

445
00:38:00,410 --> 00:38:05,820
queremos garantir que a entrada é un ficheiro Huff ou non.

446
00:38:05,820 --> 00:38:10,420
E entón, xa que asegura que é un arquivo de Huff, entón nós queremos construír a nosa árbore,

447
00:38:10,420 --> 00:38:20,940
construír a árbore de tal forma que corresponda a árbore que a persoa que enviou a mensaxe construída.

448
00:38:20,940 --> 00:38:25,840
A continuación, despois de construír a árbore, entón podemos manexar o, 0s e 1s que pasaron en

449
00:38:25,840 --> 00:38:29,590
seguir os ao longo da nosa árbore porque é idéntico,

450
00:38:29,590 --> 00:38:33,510
e logo escribir esta mensaxe, interpretar os bits de volta para chars.

451
00:38:33,510 --> 00:38:35,880
E entón, ao final, porque estamos lidando con punteiros aquí,

452
00:38:35,880 --> 00:38:38,110
queremos estar seguro de que non temos ningunha derrames de memoria

453
00:38:38,110 --> 00:38:41,330
e que todo libre.

454
00:38:42,820 --> 00:38:46,430
>> Garantir o uso axeitado é vello sombreiro para nós agora.

455
00:38:46,430 --> 00:38:51,980
Nós levamos unha entrada, que vai ser o nome do ficheiro a golpe,

456
00:38:51,980 --> 00:38:56,010
e, entón, indicar unha saída,

457
00:38:56,010 --> 00:39:01,580
de xeito que o nome do ficheiro de saída para o tufado, que será o ficheiro de texto.

458
00:39:03,680 --> 00:39:08,820
Isto é uso. E agora queremos garantir que a entrada é xingou ou non.

459
00:39:08,820 --> 00:39:16,420
Pensando ben, estaba alí nada no código de distribución que nos pode axudar a

460
00:39:16,420 --> 00:39:21,570
coa comprensión un ficheiro xingou ou non?

461
00:39:21,570 --> 00:39:26,910
Houbo información sobre o huffile.c Huffeader.

462
00:39:26,910 --> 00:39:33,430
Sabemos que cada ficheiro ten un Huff Huffeader asociada cun número máxico

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

464
00:39:37,240 --> 00:39:39,570
, Así como unha suma de verificación.

465
00:39:39,570 --> 00:39:43,180
Nós sabemos diso, pero nós tamén levou un ollo a dump.c,

466
00:39:43,180 --> 00:39:49,120
no que se le nun arquivo Huff.

467
00:39:49,120 --> 00:39:53,990
E así, para facelo, tiña que comprobar que realmente foi xingou ou non.

468
00:39:53,990 --> 00:40:03,380
Entón, talvez puidésemos utilizar dump.c como unha estrutura para o noso puff.c.

469
00:40:03,380 --> 00:40:12,680
Volver pset 4, cando tivemos a copy.c arquivo que copiou no triplica RGB

470
00:40:12,680 --> 00:40:14,860
e Interpreta que para Whodunit e redimensionar,

471
00:40:14,860 --> 00:40:20,390
Do mesmo xeito, o que podería facer é executar o comando como cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
e utilizar parte do código alí.

473
00:40:23,600 --> 00:40:28,210
Con todo, non vai ser tan sinxelo dun proceso

474
00:40:28,210 --> 00:40:33,010
para traducir o seu dump.c en puff.c,

475
00:40:33,010 --> 00:40:36,160
pero polo menos el dálle un lugar para comezar

476
00:40:36,160 --> 00:40:40,540
sobre a forma de garantir que a entrada é efectivamente ou non bufou

477
00:40:40,540 --> 00:40:43,240
así como algunhas outras cousas.

478
00:40:45,930 --> 00:40:50,250
Temos asegurado o uso adecuado e asegurou que a entrada é bufou.

479
00:40:50,250 --> 00:40:53,570
Cada vez que fixemos o que fixemos nosa comprobación de erros adecuada,

480
00:40:53,570 --> 00:41:01,520
para volver e pechar a función algunha falla ocorre, se hai un problema.

481
00:41:01,520 --> 00:41:07,170
>> Agora, o que queremos facer é construír a árbore real.

482
00:41:08,840 --> 00:41:12,640
Se miramos en Bosque, hai dúas principais funcións

483
00:41:12,640 --> 00:41:15,800
que imos querer facer-se moi familiarizado.

484
00:41:15,800 --> 00:41:23,870
Hai a planta función booleana que planta unha árbore de frecuencia non-0 dentro da nosa bosque.

485
00:41:23,870 --> 00:41:29,250
E así, alí pasar un punteiro para un bosque e un punteiro para unha árbore.

486
00:41:32,530 --> 00:41:40,340
Pregunta rápida: Cantos bosques que ten cando está construíndo unha árbore de Huffman?

487
00:41:44,210 --> 00:41:46,650
A nosa bosque é como a nosa pantalla, non?

488
00:41:46,650 --> 00:41:50,800
Entón, nós estamos indo só para ter un bosque, pero imos ter varias árbores.

489
00:41:50,800 --> 00:41:57,590
Entón, antes de chamar planta, está probablemente vai querer facer a súa bosque.

490
00:41:57,590 --> 00:42:04,430
Hai un comando para que, se ollar para forest.h de como pode facer un bosque.

491
00:42:04,430 --> 00:42:09,270
Pode plantar unha árbore. Nós sabemos como facelo.

492
00:42:09,270 --> 00:42:11,590
E entón tamén pode escoller unha árbore do bosque,

493
00:42:11,590 --> 00:42:17,540
eliminación dunha árbore co menor peso e dándolle o punteiro para iso.

494
00:42:17,540 --> 00:42:23,090
Pensando cando estabamos facendo os exemplos de nós mesmos,

495
00:42:23,090 --> 00:42:27,980
cando estabamos deseñando-o para fora, nós simplemente acaba de engadir as ligazóns.

496
00:42:27,980 --> 00:42:31,680
Pero aquí, no canto de só engadir as ligazóns,

497
00:42:31,680 --> 00:42:40,630
pensar máis como está eliminando dous deses nós e, a continuación, substituílo por outro.

498
00:42:40,630 --> 00:42:44,200
Para expresar iso en termos de colleita e cultivo,

499
00:42:44,200 --> 00:42:48,840
está escollendo dúas árbores e plantas outra árbore

500
00:42:48,840 --> 00:42:54,060
que esas dúas árbores que escolleu como nenos.

501
00:42:57,950 --> 00:43:05,280
Para construír árbore de Huffman, podes ler os símbolos e frecuencias en orde

502
00:43:05,280 --> 00:43:10,790
porque o que Huffeader dá para ti,

503
00:43:10,790 --> 00:43:14,250
dálle un conxunto de frecuencias.

504
00:43:14,250 --> 00:43:19,660
Entón pode ir adiante e simplemente ignorar calquera cousa con a 0 nel

505
00:43:19,660 --> 00:43:23,760
porque non queremos 256 follas ao final do mesmo.

506
00:43:23,760 --> 00:43:27,960
Nós só queremos o número de follas que son personaxes

507
00:43:27,960 --> 00:43:31,600
que son realmente utilizados no ficheiro.

508
00:43:31,600 --> 00:43:37,590
Podes ler neses símbolos, e cada un deses símbolos que frecuencias non-0,

509
00:43:37,590 --> 00:43:40,440
aqueles van ser árbores.

510
00:43:40,440 --> 00:43:45,990
O que podes facer é cada vez que ler un símbolo de frecuencias non-0,

511
00:43:45,990 --> 00:43:50,660
pode plantar a árbore no bosque.

512
00:43:50,660 --> 00:43:56,620
Despois de plantar as árbores no bosque, pode xuntarse esas árbores como irmáns,

513
00:43:56,620 --> 00:44:01,130
Entón, volvendo ao cultivo e escoller onde escolle 2 e despois planta 1,

514
00:44:01,130 --> 00:44:05,820
onde que unha planta que é o pai dos dous nenos que escolleu.

515
00:44:05,820 --> 00:44:11,160
Entón o resultado final vai ser unha única árbore no bosque.

516
00:44:16,180 --> 00:44:18,170
É como construír a súa árbore.

517
00:44:18,170 --> 00:44:21,850
>> Hai moitas cousas que poden dar mal aquí

518
00:44:21,850 --> 00:44:26,580
porque estamos lidando con facer novas árbores e xestionar punteiros e cousas así.

519
00:44:26,580 --> 00:44:30,450
Antes, cando estabamos lidando con punteiros,

520
00:44:30,450 --> 00:44:36,580
sempre que malloc'd nós queriamos estar seguro de que non nos devolver un valor de punteiro NULL.

521
00:44:36,580 --> 00:44:42,770
Entón, en varios pasos dentro deste proceso non van ser varios casos

522
00:44:42,770 --> 00:44:45,920
onde o programa podería fallar.

523
00:44:45,920 --> 00:44:51,310
O que quere facer é que quere estar seguro de que trata sobre estes erros,

524
00:44:51,310 --> 00:44:54,580
e na especificación di para seguro-los graciosamente,

525
00:44:54,580 --> 00:45:00,280
así como imprimir unha mensaxe para o usuario dicíndolles por iso que o programa ten para saír

526
00:45:00,280 --> 00:45:03,050
e entón rapidamente saír dela.

527
00:45:03,050 --> 00:45:09,490
Para iso o tratamento de erros, lembre que quere comprobar se

528
00:45:09,490 --> 00:45:12,160
cada vez que pode haber unha falla.

529
00:45:12,160 --> 00:45:14,660
Cada vez que está facendo un novo punteiro

530
00:45:14,660 --> 00:45:17,040
quere estar seguro de que iso é éxito.

531
00:45:17,040 --> 00:45:20,320
Antes de que estamos afeitos a facer é facer un novo punteiro e malloc-lo,

532
00:45:20,320 --> 00:45:22,380
e entón nós comprobar que ese punteiro é NULL.

533
00:45:22,380 --> 00:45:25,670
Polo tanto, non van ser algúns casos en que só se pode facer iso,

534
00:45:25,670 --> 00:45:28,610
pero ás veces realmente está chamando dunha función

535
00:45:28,610 --> 00:45:33,100
e dentro desta función, que é a única que está facendo a mallocing.

536
00:45:33,100 --> 00:45:39,110
Nese caso, se miramos para algunhas das funcións dentro do código,

537
00:45:39,110 --> 00:45:42,260
algúns deles son funcións booleanas.

538
00:45:42,260 --> 00:45:48,480
No caso abstracto, se temos unha función booleana chamada foo,

539
00:45:48,480 --> 00:45:54,580
Basicamente, podemos supoñer que, ademais de facer o que fai foo,

540
00:45:54,580 --> 00:45:57,210
xa que é unha función booleana, el retorna verdadeiro ou falso -

541
00:45:57,210 --> 00:46:01,300
certo caso de éxito, falso se non.

542
00:46:01,300 --> 00:46:06,270
Entón, queremos asegurarse de que o valor de retorno de foo é verdadeira ou falsa.

543
00:46:06,270 --> 00:46:10,400
Se é falso, o que significa que nós imos querer imprimir algún tipo de mensaxe

544
00:46:10,400 --> 00:46:14,390
e pecha o programa.

545
00:46:14,390 --> 00:46:18,530
O que queremos facer é comprobar o valor de retorno de foo.

546
00:46:18,530 --> 00:46:23,310
Se foo retorna falso, entón sabemos que atopamos algún tipo de erro

547
00:46:23,310 --> 00:46:25,110
e necesitamos deixar de noso programa.

548
00:46:25,110 --> 00:46:35,600
Unha forma de facelo é ter unha condición onde a función en si é a súa condición.

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

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

551
00:46:43,390 --> 00:46:50,900
Basicamente, isto significa que a finais de execución de foo el retorna true,

552
00:46:50,900 --> 00:46:57,390
entón podemos facelo porque a función ten que avaliar foo

553
00:46:57,390 --> 00:47:00,500
, A fin de avaliar a condición xeral.

554
00:47:00,500 --> 00:47:06,500
Entón é así que pode facer algo, a función volverá certo e é ben sucedido.

555
00:47:06,500 --> 00:47:11,800
Pero cando se está a comprobación de erros, só quere saír a súa función devolve falso.

556
00:47:11,800 --> 00:47:16,090
O que podería facer é só engadir un == false ou só engadir un estrondo na fronte del

557
00:47:16,090 --> 00:47:21,010
e entón tes if (! foo).

558
00:47:21,010 --> 00:47:29,540
Dentro dese corpo que condición tería todo o tratamento de erros,

559
00:47:29,540 --> 00:47:36,940
así como, "Non se puido crear esta árbore" e, a continuación, voltar 1 ou algo así.

560
00:47:36,940 --> 00:47:43,340
O que fai, porén, é que aínda que foo retornou falso -

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

562
00:47:46,980 --> 00:47:51,060
Entón non tes que chamar foo novo. Isto é un equívoco común.

563
00:47:51,060 --> 00:47:54,730
Porque estaba na súa condición, el xa está valorado,

564
00:47:54,730 --> 00:47:59,430
Entón xa tes o resultado, se está a usar facer árbore ou algo así

565
00:47:59,430 --> 00:48:01,840
ou planta ou cabeza ou algo así.

566
00:48:01,840 --> 00:48:07,460
Ela xa ten ese valor. El xa está executado.

567
00:48:07,460 --> 00:48:10,730
Por iso, é útil usar funcións booleanas como condición

568
00:48:10,730 --> 00:48:13,890
porque se está ou non realmente facer o corpo do loop,

569
00:48:13,890 --> 00:48:18,030
el executa a función de calquera maneira.

570
00:48:22,070 --> 00:48:27,330
>> O noso segundo a última etapa é escribir a mensaxe ao ficheiro.

571
00:48:27,330 --> 00:48:33,070
Unha vez que imos construír a árbore de Huffman, a continuación, escriba a mensaxe para o arquivo é moi sinxelo.

572
00:48:33,070 --> 00:48:39,260
É moi sinxelo agora só seguir os 0s e 1s.

573
00:48:39,260 --> 00:48:45,480
E así por convención, sabemos que nunha árbore Huffman os 0s indican que deixaron

574
00:48:45,480 --> 00:48:48,360
e os 1s indican correcto.

575
00:48:48,360 --> 00:48:53,540
Entón, se ler aos poucos, cada vez que recibir un 0

576
00:48:53,540 --> 00:48:59,100
vai seguir o sector da esquerda, e despois cada vez que ler un 1

577
00:48:59,100 --> 00:49:02,100
vai seguir a rama dereita.

578
00:49:02,100 --> 00:49:07,570
E entón vai continuar ata que bata unha folla

579
00:49:07,570 --> 00:49:11,550
porque as follas van ser a finais dos ramos.

580
00:49:11,550 --> 00:49:16,870
Como podemos dicir se se loita dunha folla ou non?

581
00:49:19,800 --> 00:49:21,690
Nós dixemos que antes.

582
00:49:21,690 --> 00:49:24,040
[Alumno] Se os punteiros son NULL. Si >>.

583
00:49:24,040 --> 00:49:32,220
Podemos dicir se se loita dunha folla os punteiros para árbores, tanto a esquerda e dereita son NULL.

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

585
00:49:34,110 --> 00:49:40,320
Sabemos que queremos ler aos poucos no noso arquivo Huff.

586
00:49:43,870 --> 00:49:51,220
Como vimos antes, en dump.c, o que eles fixeron é que len aos poucos para o arquivo Huff

587
00:49:51,220 --> 00:49:54,560
e só impresos que eses fragmentos eran.

588
00:49:54,560 --> 00:49:58,430
Non imos estar facendo iso. Estamos indo facer algo que é un pouco máis complexa.

589
00:49:58,430 --> 00:50:03,620
Pero o que podemos facer é que podemos tomar aquel anaco de código que le a bit.

590
00:50:03,620 --> 00:50:10,250
Aquí temos o bit enteiro que representa o bit actual que estamos no.

591
00:50:10,250 --> 00:50:15,520
Este coida de iteração todos os bits no ficheiro ata chegar ao final do arquivo.

592
00:50:15,520 --> 00:50:21,270
Con base niso, entón vai querer ter algún tipo de iterador

593
00:50:21,270 --> 00:50:26,760
para atravesar a súa árbore.

594
00:50:26,760 --> 00:50:31,460
E, a continuación, con base en que o bit é 0 ou 1,

595
00:50:31,460 --> 00:50:36,920
vai querer quere mover este iterador á esquerda ou movelo a dereita

596
00:50:36,920 --> 00:50:44,080
todo o camiño ata que bata unha folla, así todo o camiño ata ese nó que está en

597
00:50:44,080 --> 00:50:48,260
non ligan con nós nada máis.

598
00:50:48,260 --> 00:50:54,300
Por que podemos facelo cun ficheiro Huffman pero non o código Morse?

599
00:50:54,300 --> 00:50:56,610
Porque no código Morse hai un pouco de ambigüidade.

600
00:50:56,610 --> 00:51:04,440
Nós poderiamos ser como, oh wait, se loita unha carta ao longo do camiño, quizais por iso esta é a nosa carta,

601
00:51:04,440 --> 00:51:08,150
mentres que, se seguimos un pouco máis, entón tería atinxido outra carta.

602
00:51:08,150 --> 00:51:13,110
Pero iso non vai ocorrer en codificación de Huffman,

603
00:51:13,110 --> 00:51:17,540
para que poidamos estar seguro de que a única forma que nós imos bater un personaxe

604
00:51:17,540 --> 00:51:23,480
é se os nenos esquerdo e dereito que son NULL.

605
00:51:28,280 --> 00:51:32,350
>> Finalmente, queremos liberar toda a nosa memoria.

606
00:51:32,350 --> 00:51:37,420
Queremos ambos preto o arquivo Huff que estamos lidando con

607
00:51:37,420 --> 00:51:41,940
así como eliminar todas as árbores na nosa selva.

608
00:51:41,940 --> 00:51:46,470
Con base na súa implementación, probablemente vai querer chamar eliminar bosque

609
00:51:46,470 --> 00:51:49,780
en vez de realmente pasar por todas as árbores de si mesmo.

610
00:51:49,780 --> 00:51:53,430
Pero se fixo todas as árbores temporais, vai querer liberar isto.

611
00:51:53,430 --> 00:51:59,060
Vostede sabe o seu código de mellor, para que vostede sabe onde está alocando memoria.

612
00:51:59,060 --> 00:52:04,330
E por iso, se vostede poñerse, comezar por ata controlar f'ing para malloc,

613
00:52:04,330 --> 00:52:08,330
vendo sempre que malloc e asegurarse de que liberar de todo isto

614
00:52:08,330 --> 00:52:10,190
pero entón só pasando polo seu código,

615
00:52:10,190 --> 00:52:14,260
entender onde pode ter asignado memoria.

616
00:52:14,260 --> 00:52:21,340
Normalmente pode só dicir: "A finais de un arquivo que eu estou indo só para eliminar bosque na miña selva",

617
00:52:21,340 --> 00:52:23,850
Entón, basicamente claro que a memoria libre, que,

618
00:52:23,850 --> 00:52:28,310
"E entón eu tamén estou indo para pechar o ficheiro e entón o meu programa vai saír."

619
00:52:28,310 --> 00:52:33,810
Pero é que a única vez que o programa é pechado?

620
00:52:33,810 --> 00:52:37,880
Non, porque, ás veces, pode haber un erro que pasou.

621
00:52:37,880 --> 00:52:42,080
Quizais a xente non pode abrir un arquivo ou non poderíamos facer outra árbore

622
00:52:42,080 --> 00:52:49,340
ou algún tipo de erro ocorreu no proceso de asignación de memoria e por iso volveu NULL.

623
00:52:49,340 --> 00:52:56,710
Un erro ocorreu e, despois, devolto e saia.

624
00:52:56,710 --> 00:53:02,040
Entón quere estar seguro de que en calquera momento pode que o seu programa pode saír,

625
00:53:02,040 --> 00:53:06,980
quere liberar toda a súa memoria alí.

626
00:53:06,980 --> 00:53:13,370
Non só vai ser ao final da función principal que saia do seu código.

627
00:53:13,370 --> 00:53:20,780
Quere mirar para atrás cada instancia que o seu código potencialmente pode devolver prematuramente

628
00:53:20,780 --> 00:53:25,070
e memoria calquera libre ten sentido.

629
00:53:25,070 --> 00:53:30,830
Digamos que chamara facer bosque e que retornou falso.

630
00:53:30,830 --> 00:53:34,230
Entón probablemente non vai ter eliminar o bosque

631
00:53:34,230 --> 00:53:37,080
porque non ten un bosque aínda.

632
00:53:37,080 --> 00:53:42,130
Pero en todos os puntos do código onde podes voltar prematuramente

633
00:53:42,130 --> 00:53:46,160
quere ter seguro de que liberar calquera memoria posible.

634
00:53:46,160 --> 00:53:50,020
>> Entón, cando estamos lidando con liberar memoria e ter vazamentos potenciais,

635
00:53:50,020 --> 00:53:55,440
queremos non só usar o noso xuízo eo noso lóxica

636
00:53:55,440 --> 00:54:01,850
pero tamén usar Valgrind para determinar se nós liberou toda a nosa memoria correctamente ou non.

637
00:54:01,850 --> 00:54:09,460
Pode realizar Valgrind en Puff e entón tamén ten que pasalo

638
00:54:09,460 --> 00:54:14,020
o número correcto de liña de comandos argumentos para Valgrind.

639
00:54:14,020 --> 00:54:18,100
Pode realizar tanto, pero a saída é un pouco enigmática.

640
00:54:18,100 --> 00:54:21,630
Temos tido un pouco acostumado con Speller, pero aínda necesitamos de axuda un pouco máis,

641
00:54:21,630 --> 00:54:26,450
así entón executa-lo con algunhas bandeiras, como o baleirado de máis-check = full,

642
00:54:26,450 --> 00:54:32,040
que probablemente vai dar algunha saída máis útil en Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> A continuación, outra información útil cando está depurar é o comando diff.

644
00:54:39,040 --> 00:54:48,520
Pode acceder a implementación do persoal de Huff, que executar un arquivo de texto,

645
00:54:48,520 --> 00:54:55,400
e despois a saída a un ficheiro binario, un arquivo binario Huff, para ser específico.

646
00:54:55,400 --> 00:54:59,440
Entón, se executar o seu propio vento en que o ficheiro binario,

647
00:54:59,440 --> 00:55:03,950
a continuación, idealmente, o seu arquivo de texto outputted será idéntico

648
00:55:03,950 --> 00:55:08,200
ao orixinal que pasou dentro

649
00:55:08,200 --> 00:55:15,150
Aquí estou usando hth.txt como exemplo, e iso é o que falou na súa especificación.

650
00:55:15,150 --> 00:55:21,040
Iso é literalmente só HTH e entón unha nova liña.

651
00:55:21,040 --> 00:55:30,970
Pero, en definitiva, sentirse libre e está sempre animou a utilizar exemplos máis

652
00:55:30,970 --> 00:55:32,620
para o seu arquivo de texto.

653
00:55:32,620 --> 00:55:38,110
>> Podes incluso levar un tiro na cadra comprimir e despois descomprimir

654
00:55:38,110 --> 00:55:41,600
algúns dos arquivos que usou na Speller como Guerra e Paz

655
00:55:41,600 --> 00:55:46,710
ou Jane Austen, ou algo así - o que sería ben legal - ou Austin Powers,

656
00:55:46,710 --> 00:55:51,880
tipo de manexar arquivos maiores porque non teriamos chegado ata el

657
00:55:51,880 --> 00:55:55,590
se usan a ferramenta seguinte aquí, ls-l.

658
00:55:55,590 --> 00:56:01,150
Estamos acostumados a ls, que lista todos basicamente o contido no noso directorio actual.

659
00:56:01,150 --> 00:56:07,860
Pasando o sinalizador-l realmente mostra o tamaño dos arquivos.

660
00:56:07,860 --> 00:56:12,690
Se pasar por a especificación pset, realmente percorre a creación do ficheiro binario,

661
00:56:12,690 --> 00:56:16,590
de huffing-lo, e ve que a arquivos moi pequenos

662
00:56:16,590 --> 00:56:23,910
o custo do espazo de comprimi-lo e traducir toda esa información

663
00:56:23,910 --> 00:56:26,980
de todas as frecuencias e cousas así supera o beneficio real

664
00:56:26,980 --> 00:56:30,000
de comprimir o ficheiro primeiro.

665
00:56:30,000 --> 00:56:37,450
Pero se executa-lo en algúns arquivos de texto máis longos, entón podes ver que comeza a ter algún beneficio

666
00:56:37,450 --> 00:56:40,930
en comprimir os arquivos.

667
00:56:40,930 --> 00:56:46,210
>> E entón, finalmente, temos o noso GDB vello amigo, que, certamente, vai vir a cadra tamén.

668
00:56:48,360 --> 00:56:55,320
>> Non temos ningunha dúbida en árbores Huff ou o proceso pode facer as árbores

669
00:56:55,320 --> 00:56:58,590
ou calquera outras preguntas sobre Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Okay. Eu vou ir en torno a un bit.

671
00:57:02,570 --> 00:57:06,570
>> Grazas a todos. Este foi Walkthrough 6. , E boa sorte.

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