1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Passo a passo - Conjunto 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
>> Olá, todos, e bem vindo ao Passo a passo 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
Em Puff Huff'n o que estamos fazendo vai estar lidando com um arquivo compactado Huffman

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

7
00:00:20,740 --> 00:00:25,810
para que possamos traduzir do 0s e 1s que o usuário envia-nos

8
00:00:25,810 --> 00:00:30,660
e convertê-lo de volta para o texto original.

9
00:00:30,660 --> 00:00:34,360
Pset 6 vai ser muito legal, porque você está indo para ver algumas das ferramentas

10
00:00:34,360 --> 00:00:41,730
que você usou na pset 4 e 5 e pset tipo de combiná-los em um conceito muito arrumado

11
00:00:41,730 --> 00:00:43,830
quando você chegou a pensar sobre isso.

12
00:00:43,830 --> 00:00:50,110
>> Além disso, sem dúvida, pset 4 e 5 foram os mais desafiadores Série de Exercícios que tínhamos para oferecer.

13
00:00:50,110 --> 00:00:53,950
Então, a partir de agora, temos essa pset um mais em C,

14
00:00:53,950 --> 00:00:56,480
e depois disso que estamos diante de programação web.

15
00:00:56,480 --> 00:01:02,310
Então felicitar-vos para ficar mais a mais difícil corcova na CS50.

16
00:01:03,630 --> 00:01:09,760
>> Passando para Puff Huff'n, a nossa caixa de ferramentas para este pset vão ser árvores Huffman,

17
00:01:09,760 --> 00:01:14,700
de modo a compreensão não só como trabalho árvores binárias, mas também árvores especificamente Huffman,

18
00:01:14,700 --> 00:01:16,240
como eles são construídos.

19
00:01:16,240 --> 00:01:20,210
E então nós vamos ter um monte de código distribuição neste pset,

20
00:01:20,210 --> 00:01:22,480
e nós vamos chegar a ver que, na verdade, parte do código

21
00:01:22,480 --> 00:01:24,670
podemos não ser capazes de compreender plenamente ainda,

22
00:01:24,670 --> 00:01:30,080
e assim esses serão os arquivos. C, mas depois os seus acompanhantes. arquivos h

23
00:01:30,080 --> 00:01:34,300
nos dará o suficiente compreensão de que precisamos para que possamos saber como essas funções funcionam

24
00:01:34,300 --> 00:01:38,100
ou pelo menos o que é suposto fazer - suas entradas e saídas -

25
00:01:38,100 --> 00:01:40,760
mesmo se não sabemos o que está acontecendo na caixa preta

26
00:01:40,760 --> 00:01:44,090
ou não entendem o que está acontecendo na caixa preta dentro.

27
00:01:44,090 --> 00:01:49,400
E então, finalmente, como de costume, estamos a lidar com estruturas de dados novos,

28
00:01:49,400 --> 00:01:51,840
tipos específicos de nós que apontam para certas coisas,

29
00:01:51,840 --> 00:01:56,080
e por isso aqui ter uma caneta e um papel não apenas para o processo de design

30
00:01:56,080 --> 00:01:58,470
e quando você está tentando descobrir como o seu pset deve funcionar

31
00:01:58,470 --> 00:02:00,520
mas também durante a depuração.

32
00:02:00,520 --> 00:02:06,140
Você pode ter GDB ao lado de sua caneta e papel, enquanto você toma para baixo o que os valores são,

33
00:02:06,140 --> 00:02:09,320
onde suas setas estão apontando, e coisas assim.

34
00:02:09,320 --> 00:02:13,720
>> Primeiro, vamos olhar para as árvores Huffman.

35
00:02:13,720 --> 00:02:19,600
Árvores Huffman são árvores binárias, o que significa que cada nó só tem 2 filhos.

36
00:02:19,600 --> 00:02:24,870
Em árvores Huffman a característica é a de que os valores mais frequentes

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

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

39
00:02:32,690 --> 00:02:38,030
Se você está tentando traduzir um A ou um E, por exemplo,

40
00:02:38,030 --> 00:02:43,940
você está traduzindo que, muitas vezes, então ao invés de ter que usar todo o conjunto de bits

41
00:02:43,940 --> 00:02:48,640
alocados para esse tipo de dados de costume, comprimi-lo para baixo, para menos,

42
00:02:48,640 --> 00:02:53,730
e depois as cartas que são representados com menos frequência são representados com pedaços mais longos

43
00:02:53,730 --> 00:02:59,840
porque você pode pagar que quando você pesar as freqüências que essas letras aparecem.

44
00:02:59,840 --> 00:03:03,020
Nós temos a mesma idéia aqui em árvores Huffman

45
00:03:03,020 --> 00:03:12,360
onde estamos fazendo uma corrente, uma espécie de caminho para chegar aos personagens certas.

46
00:03:12,360 --> 00:03:14,470
E então os personagens que têm mais freqüência

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

48
00:03:17,940 --> 00:03:22,020
>> O jeito que você construir uma árvore de Huffman

49
00:03:22,020 --> 00:03:27,430
é a colocação de todos os personagens que aparecem no texto

50
00:03:27,430 --> 00:03:30,630
e calcular a sua freqüência, quantas vezes eles aparecem.

51
00:03:30,630 --> 00:03:33,880
Isto poderia ser uma contagem de quantas vezes as letras aparecem

52
00:03:33,880 --> 00:03:40,270
ou talvez uma porcentagem de fora de todos os personagens quantos cada um aparece.

53
00:03:40,270 --> 00:03:44,270
E então o que você faz é quando você tem tudo isso para fora mapeado,

54
00:03:44,270 --> 00:03:49,060
então você olha para as duas freqüências mais baixas e depois juntá-los como irmãos

55
00:03:49,060 --> 00:03:55,660
onde, então, o nó pai tem uma freqüência que é a soma de seus dois filhos.

56
00:03:55,660 --> 00:04:00,870
E então você por convenção dizer que o nó esquerdo,

57
00:04:00,870 --> 00:04:03,770
você segue que, seguindo o ramo 0,

58
00:04:03,770 --> 00:04:08,140
e depois o nó mais à direita é o ramo 1.

59
00:04:08,140 --> 00:04:16,040
Como vimos em código Morse, a única pegadinha é que, se você tivesse apenas um bip eo bip

60
00:04:16,040 --> 00:04:18,120
era ambígua.

61
00:04:18,120 --> 00:04:22,430
Poderia ser uma letra ou pode ser uma sequência de duas letras.

62
00:04:22,430 --> 00:04:27,790
E então o que Huffman árvores faz é porque, por natureza dos personagens

63
00:04:27,790 --> 00:04:34,140
ou finais nossos personagens reais, sendo os nós últimos no ramo -

64
00:04:34,140 --> 00:04:39,300
nos referimos aos que como as folhas - em virtude de que não pode haver qualquer ambiguidade

65
00:04:39,300 --> 00:04:45,160
em termos de qual a letra que você está tentando codificar com a série de bits

66
00:04:45,160 --> 00:04:50,670
porque em nenhum lugar ao longo dos bits que representam uma carta

67
00:04:50,670 --> 00:04:55,960
você vai encontrar outra carta inteira, e não haverá nenhuma confusão lá.

68
00:04:55,960 --> 00:04:58,430
Mas vamos entrar em exemplos que vocês podem realmente ver que

69
00:04:58,430 --> 00:05:02,120
em vez de nós simplesmente dizendo que isso é verdade.

70
00:05:02,120 --> 00:05:06,390
>> Vejamos um exemplo simples de uma árvore de Huffman.

71
00:05:06,390 --> 00:05:09,380
Eu tenho uma seqüência aqui que é de 12 caracteres.

72
00:05:09,380 --> 00:05:14,010
Eu tenho 4 Como, 6 Bs, Cs e 2.

73
00:05:14,010 --> 00:05:17,270
Meu primeiro passo seria contar.

74
00:05:17,270 --> 00:05:20,760
Quantas vezes é que um parecer? Ele aparece quatro vezes na seqüência.

75
00:05:20,760 --> 00:05:25,060
B aparece 6 vezes, e C é exibida duas vezes.

76
00:05:25,060 --> 00:05:28,970
Naturalmente, eu vou dizer que estou usando B na maioria das vezes,

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

78
00:05:35,970 --> 00:05:42,600
E então eu também vou esperar C para exigir a maior quantidade de 0s e 1s também.

79
00:05:42,600 --> 00:05:48,550
Primeiro o que eu fiz aqui é que eu colocava em ordem crescente em termos de frequência.

80
00:05:48,550 --> 00:05:52,710
Vemos que o C e A, essas são as nossas duas frequências mais baixas.

81
00:05:52,710 --> 00:06:00,290
Criamos um nó pai, e que o nó pai não tem uma carta a ela associados,

82
00:06:00,290 --> 00:06:05,070
mas tem uma frequência, que é a soma.

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

84
00:06:08,780 --> 00:06:10,800
Então, seguimos o ramo esquerdo.

85
00:06:10,800 --> 00:06:14,970
Se estivéssemos naquele nó 6, então poderíamos seguir 0 para chegar a C

86
00:06:14,970 --> 00:06:17,450
e, em seguida, 1 para obter a A.

87
00:06:17,450 --> 00:06:20,300
Portanto, agora temos dois nós.

88
00:06:20,300 --> 00:06:23,920
Nós temos o valor 6 e depois também temos outro nó com o valor 6.

89
00:06:23,920 --> 00:06:28,550
E assim os dois não são apenas o menor 2, mas também a apenas 2 que sobraram,

90
00:06:28,550 --> 00:06:33,820
para que se juntar aos que por outro pai, com a soma sendo 12.

91
00:06:33,820 --> 00:06:36,300
Portanto, temos aqui a nossa árvore de Huffman

92
00:06:36,300 --> 00:06:40,020
onde para chegar a B, que seria apenas o bit 1

93
00:06:40,020 --> 00:06:45,430
e, em seguida, para chegar a um teríamos 01 e, em seguida, C com 00.

94
00:06:45,430 --> 00:06:51,300
Então aqui nós vemos que, basicamente, estamos representando estes chars com 1 ou 2 bits

95
00:06:51,300 --> 00:06:55,160
em que a B, como previsto, tem pelo menos.

96
00:06:55,160 --> 00:07:01,730
E então esperávamos C para ter mais, mas já que é tal uma árvore de Huffman pequeno,

97
00:07:01,730 --> 00:07:06,020
então o A é também representada por 2 bits em vez de algures no meio.

98
00:07:07,820 --> 00:07:11,070
>> Só para passar por cima de outro exemplo simples da árvore de Huffman,

99
00:07:11,070 --> 00:07:19,570
dizer que você tem a string "Olá".

100
00:07:19,570 --> 00:07:25,360
O que você é primeiro você diria quantas vezes H aparecer nessa?

101
00:07:25,360 --> 00:07:34,200
H aparece uma vez e em seguida e aparece uma vez e então temos l aparecendo duas vezes

102
00:07:34,200 --> 00:07:36,580
e o aparecimento vez.

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

104
00:07:44,310 --> 00:07:47,450
[Aluno] l. L. >> Sim. l é certo.

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

106
00:07:50,730 --> 00:07:55,890
porque eu é usado mais na string "Olá".

107
00:07:55,890 --> 00:08:04,280
O que eu vou fazer agora é tirar esses nós.

108
00:08:04,280 --> 00:08:15,580
I ter 1, que é H, e, em seguida, um outro 1, que é o e, em seguida, um 1, que é o -

109
00:08:15,580 --> 00:08:23,410
agora eu estou colocando-os em ordem - e, em seguida, 2, que é l.

110
00:08:23,410 --> 00:08:32,799
Então eu digo a maneira que eu construir uma árvore de Huffman é encontrar os dois nós com as menores freqüências

111
00:08:32,799 --> 00:08:38,010
e torná-los irmãos criando um nó pai.

112
00:08:38,010 --> 00:08:41,850
Aqui temos três nós com a menor freqüência. Eles são todos um.

113
00:08:41,850 --> 00:08:50,620
Então aqui nós escolher qual vamos ligar primeiro.

114
00:08:50,620 --> 00:08:54,850
Vamos dizer que eu escolher o H eo e.

115
00:08:54,850 --> 00:09:01,150
A soma de 1 + 1 é 2, mas este nó não tiver uma carta a ela associados.

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

117
00:09:04,440 --> 00:09:10,950
Agora vamos olhar para os próximos 2 frequências mais baixas.

118
00:09:10,950 --> 00:09:15,590
Isso é 2 e 1. Isso poderia ser um desses dois, mas eu vou escolher um presente.

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

120
00:09:18,800 --> 00:09:26,410
E então, finalmente, eu só tenho 2 esquerda, de modo que se torna então 5.

121
00:09:26,410 --> 00:09:32,010
Então, aqui, como esperado, se eu preencher a codificação para que,

122
00:09:32,010 --> 00:09:37,480
1s são sempre o braço direito e 0s são a esquerda.

123
00:09:37,480 --> 00:09:45,880
Então nós temos l representadas por apenas um pouco e depois o o por 2

124
00:09:45,880 --> 00:09:52,360
e, em seguida, o e por 2 e, em seguida, o H cai para 3 bits.

125
00:09:52,360 --> 00:09:59,750
Então você pode transmitir esta mensagem "Olá" em vez de realmente usando os personagens

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

127
00:10:02,760 --> 00:10:07,910
No entanto, lembre-se que em vários casos que tinham laços com a nossa frequência.

128
00:10:07,910 --> 00:10:11,900
Poderíamos ter ou juntou o H eo O primeiro talvez.

129
00:10:11,900 --> 00:10:15,730
Ou então, mais tarde, quando tivemos a l representada por 2

130
00:10:15,730 --> 00:10:19,410
bem como a que se juntou um representado por 2, pode-se ter ligado um ou outro.

131
00:10:19,410 --> 00:10:23,630
>> E assim, quando você envia os 0s e 1s, que na verdade não garante

132
00:10:23,630 --> 00:10:27,090
que o destinatário pode inteiramente ler sua mensagem logo de cara

133
00:10:27,090 --> 00:10:30,490
porque eles podem não saber que a decisão que você fez.

134
00:10:30,490 --> 00:10:34,920
Então, quando estamos lidando com compressão Huffman,

135
00:10:34,920 --> 00:10:40,090
de alguma forma, temos de dizer o destinatário da nossa mensagem como decidimos -

136
00:10:40,090 --> 00:10:43,470
Eles precisam saber algum tipo de informação extra

137
00:10:43,470 --> 00:10:46,580
para além da mensagem comprimida.

138
00:10:46,580 --> 00:10:51,490
Eles precisam entender o que a árvore realmente se parece,

139
00:10:51,490 --> 00:10:55,450
como realmente fez essas decisões.

140
00:10:55,450 --> 00:10:59,100
>> Aqui foram apenas fazendo exemplos baseados na contagem real,

141
00:10:59,100 --> 00:11:01,550
mas às vezes você pode ter também uma árvore de Huffman

142
00:11:01,550 --> 00:11:05,760
com base na freqüência em que as letras aparecem, e é exatamente o mesmo processo.

143
00:11:05,760 --> 00:11:09,090
Aqui eu estou expressando-a em termos de percentagens ou fração,

144
00:11:09,090 --> 00:11:11,290
e por isso aqui exatamente a mesma coisa.

145
00:11:11,290 --> 00:11:15,300
Acho o menor 2, somá-los, o 2 menor seguinte, somá-los,

146
00:11:15,300 --> 00:11:19,390
até eu ter uma árvore cheia.

147
00:11:19,390 --> 00:11:23,610
Mesmo que pudéssemos fazê-lo de qualquer forma, quando estamos lidando com percentagens,

148
00:11:23,610 --> 00:11:27,760
isso significa que estamos dividindo as coisas e lidar com decimais ou melhor, flutua

149
00:11:27,760 --> 00:11:30,900
se estamos pensando em estruturas de dados de uma cabeça.

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

151
00:11:32,540 --> 00:11:35,180
O que é um problema comum quando estamos lidando com carros alegóricos?

152
00:11:35,180 --> 00:11:38,600
[Aluno] aritmética imprecisa. Sim >>. Imprecisão.

153
00:11:38,600 --> 00:11:43,760
Por causa da imprecisão de ponto flutuante, para este pset para que certifique-se

154
00:11:43,760 --> 00:11:49,450
que não perdemos nenhum valor, então estamos realmente vai ser lidar com a contagem.

155
00:11:49,450 --> 00:11:54,880
Então, se você pensar em um nó Huffman, se você olhar para trás, para a estrutura aqui,

156
00:11:54,880 --> 00:12:01,740
se você olhar para os verdes que tem uma freqüência associada a ele

157
00:12:01,740 --> 00:12:08,760
assim como ele aponta para um nó para o seu lado esquerdo, assim como um nó à direita.

158
00:12:08,760 --> 00:12:13,970
E, em seguida, as tintas têm também um carácter que lhes estão associados.

159
00:12:13,970 --> 00:12:18,900
Nós não vamos fazer os separados para os pais e, em seguida, os nós finais,

160
00:12:18,900 --> 00:12:23,680
a que nos referimos como as folhas, mas sim aqueles que só têm valores nulos.

161
00:12:23,680 --> 00:12:31,050
Para cada nó teremos um personagem, o símbolo que representa esse nó,

162
00:12:31,050 --> 00:12:40,490
em seguida, a frequência, bem como um indicador para o seu filho esquerdo, bem como a sua criança direita.

163
00:12:40,490 --> 00:12:45,680
As folhas, que são bem no fundo, também teria ponteiros nó

164
00:12:45,680 --> 00:12:49,550
à sua esquerda e à sua direita, mas desde que esses valores não estão apontando para nós reais,

165
00:12:49,550 --> 00:12:53,970
o que seria o seu valor ser? >> [Aluno] NULL. NULL. >> Exatamente.

166
00:12:53,970 --> 00:12:58,430
Aqui está um exemplo de como você pode representar a freqüência em carros alegóricos,

167
00:12:58,430 --> 00:13:02,130
mas vamos estar lidando com isso com números inteiros,

168
00:13:02,130 --> 00:13:06,780
então tudo que eu fiz é mudar o tipo de dados lá.

169
00:13:06,780 --> 00:13:09,700
>> Vamos a um pouco mais de um exemplo complexo.

170
00:13:09,700 --> 00:13:13,360
Mas agora que temos feito as mais simples, é apenas o mesmo processo.

171
00:13:13,360 --> 00:13:20,290
Você encontra as duas frequências mais baixas, somar as freqüências

172
00:13:20,290 --> 00:13:22,450
e essa é a nova freqüência de seu nó pai,

173
00:13:22,450 --> 00:13:29,310
que, então, aponta para a sua esquerda com o ramo do direito 0 e com o ramo 1.

174
00:13:29,310 --> 00:13:34,200
Se temos a string "Este é CS50," então nós contar quantas vezes é 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ão o que eu fiz aqui é com os nós vermelhos eu só plantadas,

177
00:13:42,010 --> 00:13:48,530
Eu disse que eu vou ter esses personagens, eventualmente, na parte inferior da minha árvore.

178
00:13:48,530 --> 00:13:51,740
Aqueles vão ser todas as folhas.

179
00:13:51,740 --> 00:13:58,200
Então o que eu fiz é que eu classificados los pela frequência em ordem crescente,

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

181
00:14:02,950 --> 00:14:07,550
é ele classifica-lo por freqüência e, em seguida, em ordem alfabética.

182
00:14:07,550 --> 00:14:13,870
Por isso, tem os números primeiro e depois em ordem alfabética pela freqüência.

183
00:14:13,870 --> 00:14:18,520
Então o que eu gostaria de fazer é que eu iria encontrar a menor 2. Isso é 0 e 5.

184
00:14:18,520 --> 00:14:22,390
Gostaria de somá-los, e isso é 2. Então gostaria de continuar, encontrar o próximo 2 menor.

185
00:14:22,390 --> 00:14:26,100
Esses são os 1s dois, e, em seguida, os dois se tornam também.

186
00:14:26,100 --> 00:14:31,570
Agora eu sei que o meu próximo passo vai ser juntar o menor número,

187
00:14:31,570 --> 00:14:41,380
que é o T, a 1, e em seguida, escolher um dos nós que tem 2 como a freqüência.

188
00:14:41,380 --> 00:14:44,560
Portanto, temos aqui três opções.

189
00:14:44,560 --> 00:14:47,980
O que eu vou fazer para o slide é apenas visualmente reorganizá-los para você

190
00:14:47,980 --> 00:14:51,790
de modo que você pode ver como eu estou construindo-o.

191
00:14:51,790 --> 00:14:59,040
O que o código eo código de distribuição vai fazer seria juntar a uma T

192
00:14:59,040 --> 00:15:01,410
com o nó 0 e 5.

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

194
00:15:05,060 --> 00:15:08,660
O 2 a 2 e agora são os mais baixos, de modo então aqueles soma a 4.

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

196
00:15:12,560 --> 00:15:16,410
Em seguida, depois de que temos a 3 e 3 que necessitam de ser adicionados,

197
00:15:16,410 --> 00:15:21,650
assim outra vez eu estou apenas ligá-lo de modo que você pode ver visualmente, de modo que ele não fique muito confuso.

198
00:15:21,650 --> 00:15:25,740
Então nós temos um 6, e então o nosso passo final é agora que temos apenas 2 nós

199
00:15:25,740 --> 00:15:30,440
somamos aqueles para tornar a base da nossa árvore, que é 10.

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

201
00:15:34,100 --> 00:15:40,750
seu valor, o seu número de freqüência, era quantas vezes eles apareceram na seqüência,

202
00:15:40,750 --> 00:15:46,350
e então temos 5 personagens em nossa string, de modo que faz sentido.

203
00:15:48,060 --> 00:15:52,320
Se olhar para como nós, na verdade, codificá-lo,

204
00:15:52,320 --> 00:15:56,580
como esperado, o i eo s, que aparecem com mais freqüência

205
00:15:56,580 --> 00:16:01,350
são representados pelo número mínimo de bits.

206
00:16:03,660 --> 00:16:05,660
>> Tenha cuidado aqui.

207
00:16:05,660 --> 00:16:09,780
Em árvores Huffman o caso realmente importa.

208
00:16:09,780 --> 00:16:13,670
Um S maiúsculo é diferente de um s minúsculo.

209
00:16:13,670 --> 00:16:21,260
Se tivéssemos "Este é CS50" com letras maiúsculas, o s minúsculo só aparecem duas vezes,

210
00:16:21,260 --> 00:16:27,120
Seria um nó com 2 como o seu valor e, em seguida, S maiúsculo seria apenas uma vez.

211
00:16:27,120 --> 00:16:33,440
Então sua árvore mudaria as estruturas, porque você realmente tem uma folha extra aqui.

212
00:16:33,440 --> 00:16:36,900
Mas a soma ainda seria 10.

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

214
00:16:39,570 --> 00:16:44,060
a adição de todas as contagens.

215
00:16:46,010 --> 00:16:50,990
>> Agora que nós cobrimos árvores Huffman, podemos mergulhar em Huff'n Puff, o pset.

216
00:16:50,990 --> 00:16:52,900
Nós vamos começar com uma seção de perguntas,

217
00:16:52,900 --> 00:16:57,990
e isso vai levá-lo acostumado com árvores binárias e como operar em torno de que:

218
00:16:57,990 --> 00:17:03,230
nós desenho, criando a sua própria estrutura typedef para um nó,

219
00:17:03,230 --> 00:17:07,230
e ver como você pode inserir em uma árvore binária, um que está classificado,

220
00:17:07,230 --> 00:17:09,050
atravessando, e coisas assim.

221
00:17:09,050 --> 00:17:14,560
Esse conhecimento é definitivamente vai ajudar você quando você mergulha na porção Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Na edição padrão do pset, sua tarefa é implementar Puff,

224
00:17:26,329 --> 00:17:30,240
e na versão pirata sua tarefa é implementar Huff.

225
00:17:30,240 --> 00:17:38,490
O Huff faz é que leva o texto e então o traduz para os 0s e 1s,

226
00:17:38,490 --> 00:17:41,990
assim o processo que fizemos acima, onde contamos as freqüências

227
00:17:41,990 --> 00:17:50,970
e em seguida, fez a árvore e, em seguida, disse: "Como posso obter T?"

228
00:17:50,970 --> 00:17:54,840
T é representado por 100, coisas assim,

229
00:17:54,840 --> 00:17:58,860
Huff e depois levaria o texto e, em seguida, saída que binário.

230
00:17:58,860 --> 00:18:04,920
Mas também porque sabemos que nós queremos permitir que o nosso destinatário da mensagem

231
00:18:04,920 --> 00:18:11,790
para recriar a mesma árvore que, também inclui informações sobre as contagens de freqüência.

232
00:18:11,790 --> 00:18:17,980
Então, com Puff nos é dado um arquivo binário de 0s e 1s

233
00:18:17,980 --> 00:18:21,740
e atendendo também à informação sobre as frequências.

234
00:18:21,740 --> 00:18:26,740
Traduzimos todos os 0s e 1s de volta para a mensagem original que foi,

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

236
00:18:29,350 --> 00:18:36,450
Se você está fazendo a edição padrão, você não precisa implementar Huff,

237
00:18:36,450 --> 00:18:39,290
, então você pode simplesmente usar a implementação equipe de Huff.

238
00:18:39,290 --> 00:18:42,080
Há instruções na especificação de como fazer isso.

239
00:18:42,080 --> 00:18:48,780
Você pode executar a implementação equipe de Huff em cima de um arquivo de texto certa

240
00:18:48,780 --> 00:18:53,270
e depois usar essa saída como a sua entrada para Puff.

241
00:18:53,270 --> 00:18:59,330
>> Como eu mencionei antes, nós temos um monte de código de distribuição para este.

242
00:18:59,330 --> 00:19:01,810
Eu vou começar a passar por isso.

243
00:19:01,810 --> 00:19:04,400
Eu vou passar 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 fornece os protótipos das funções,

246
00:19:11,650 --> 00:19:15,520
não é totalmente precisa entender exatamente -

247
00:19:15,520 --> 00:19:20,280
Se você não entende o que está acontecendo nos arquivos. C, então não se preocupe muito,

248
00:19:20,280 --> 00:19:23,600
mas definitivamente tentar dar uma olhada porque pode dar algumas dicas

249
00:19:23,600 --> 00:19:29,220
e é útil para se acostumar com leitura de código de outras pessoas.

250
00:19:38,940 --> 00:19:48,270
>> Olhando huffile.h, nos comentários que declara uma camada de abstração para Huffman codificados arquivos.

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

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

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

254
00:20:08,250 --> 00:20:11,930
Então aqui nós temos um número mágico identificar um arquivo Huffman-codificado.

255
00:20:11,930 --> 00:20:15,890
Dentro de um código de Huffman eles vão ter um número de certa magia

256
00:20:15,890 --> 00:20:18,560
associados com o cabeçalho.

257
00:20:18,560 --> 00:20:21,110
Isso pode parecer apenas um número mágico aleatório,

258
00:20:21,110 --> 00:20:27,160
mas se você realmente traduzi-lo em ASCII, então ele realmente explicita Huff.

259
00:20:27,160 --> 00:20:34,290
Aqui temos uma estrutura para um arquivo Huffman-codificado.

260
00:20:34,290 --> 00:20:39,670
Há todas essas características associadas a um arquivo Huff.

261
00:20:39,670 --> 00:20:47,080
Então aqui temos o cabeçalho de um arquivo de Huff, por isso nós dizemos que Huffeader

262
00:20:47,080 --> 00:20:50,810
em vez de adicionar o h extra porque parece o mesmo de qualquer maneira.

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

264
00:20:52,720 --> 00:20:57,790
Nós temos um número mágico associado a ele.

265
00:20:57,790 --> 00:21:09,040
Se for um arquivo de Huff real, que vai ser o número acima, esta magia.

266
00:21:09,040 --> 00:21:14,720
E então ele vai ter uma matriz.

267
00:21:14,720 --> 00:21:18,750
Assim, para cada símbolo, dos quais existem 256,

268
00:21:18,750 --> 00:21:24,760
ele vai listar o que a frequência desses símbolos estão dentro do arquivo de Huff.

269
00:21:24,760 --> 00:21:28,090
E então, finalmente, temos uma soma de verificação para as freqüências,

270
00:21:28,090 --> 00:21:32,160
qual deve ser a soma dessas frequências.

271
00:21:32,160 --> 00:21:36,520
Então é isso que um Huffeader é.

272
00:21:36,520 --> 00:21:44,600
Então, temos algumas funções que retornam o próximo bit no arquivo Huff

273
00:21:44,600 --> 00:21:52,580
bem como escreve um pouco para o arquivo de Huff, e então esta função aqui, hfclose,

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

275
00:21:54,650 --> 00:21:57,290
Antes, estávamos lidando com reta apenas fclose,

276
00:21:57,290 --> 00:22:01,190
mas quando você tem um arquivo de Huff, em vez de se fclosing

277
00:22:01,190 --> 00:22:06,080
o que na verdade você está indo fazer é hfclose e hfopen-lo.

278
00:22:06,080 --> 00:22:13,220
Essas são funções específicas para os arquivos de Huff que nós vamos tratar.

279
00:22:13,220 --> 00:22:19,230
Então aqui nós lemos no cabeçalho e em seguida, escrever o cabeçalho.

280
00:22:19,230 --> 00:22:25,700
>> Só lendo o. Arquivo h podemos tipo de obter uma noção do que um arquivo pode ser Huff,

281
00:22:25,700 --> 00:22:32,480
quais as características que tem, sem realmente ir para o huffile.c,

282
00:22:32,480 --> 00:22:36,750
que, se mergulhar, vai ser um pouco mais complexa.

283
00:22:36,750 --> 00:22:41,270
Ele tem todo o arquivo I / O lidando aqui com ponteiros.

284
00:22:41,270 --> 00:22:48,010
Aqui vemos que quando chamamos hfread, por exemplo, que ainda está lidando com fread.

285
00:22:48,010 --> 00:22:53,050
Nós não vai se livrar dessas funções totalmente, mas estamos enviando as medidas a tomar conta de

286
00:22:53,050 --> 00:22:59,760
dentro do arquivo Huff em vez de fazer tudo nós mesmos.

287
00:22:59,760 --> 00:23:02,300
Você pode se sentir livre para fazer a varredura através deste se você está curioso

288
00:23:02,300 --> 00:23:08,410
e ir descascar a camada de volta um pouco.

289
00:23:20,650 --> 00:23:24,060
>> O próximo arquivo que vamos olhar é tree.h.

290
00:23:24,060 --> 00:23:30,210
Antes do passo a passo desliza dissemos que esperar um nó Huffman

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

292
00:23:32,960 --> 00:23:38,360
Esperamos que tem um símbolo, uma frequência, e depois duas estrelas nó.

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

294
00:23:41,870 --> 00:23:46,880
exceto em vez de nó vamos chamá-los de árvores.

295
00:23:48,790 --> 00:23:56,760
Nós temos uma função que quando você chamar fazer árvore que retorna um ponteiro de árvore.

296
00:23:56,760 --> 00:24:03,450
Fazer a Speller, quando você estava fazendo um novo nó

297
00:24:03,450 --> 00:24:11,410
você disse nó palavra * novo = malloc (sizeof) e coisas assim.

298
00:24:11,410 --> 00:24:17,510
Basicamente, mktree vai ser lidar com isso para você.

299
00:24:17,510 --> 00:24:20,990
Da mesma forma, quando você quiser remover uma árvore,

300
00:24:20,990 --> 00:24:24,810
de modo que é essencialmente libertar a árvore quando terminar com ele,

301
00:24:24,810 --> 00:24:33,790
em vez de chamar explicitamente livre em que, na verdade você está indo só para usar a função rmtree

302
00:24:33,790 --> 00:24:40,360
onde você passar o ponteiro para a árvore e, em seguida, tree.c vai cuidar disso para você.

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

304
00:24:42,490 --> 00:24:47,240
Esperamos que as mesmas funções, exceto para ver a execução também.

305
00:24:47,240 --> 00:24:57,720
Como esperávamos, quando você chama-lo mktree mallocs do tamanho de uma árvore em um ponteiro,

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

307
00:25:03,190 --> 00:25:08,280
e retorna o ponteiro para a árvore que você acabou de malloc'd para você.

308
00:25:08,280 --> 00:25:13,340
Aqui quando você chamar remover árvore primeiro garante que você não está liberando dupla.

309
00:25:13,340 --> 00:25:18,320
Ele garante que você realmente tem uma árvore que você deseja remover.

310
00:25:18,320 --> 00:25:23,330
Aqui porque uma árvore também inclui os seus filhos,

311
00:25:23,330 --> 00:25:29,560
o que isto significa é que chama recursivamente remover árvore no nó esquerdo da árvore

312
00:25:29,560 --> 00:25:31,650
bem como o nó direito.

313
00:25:31,650 --> 00:25:37,790
Antes que liberta o pai, ele precisa libertar os filhos também.

314
00:25:37,790 --> 00:25:42,770
Pai também é intercambiável com raiz.

315
00:25:42,770 --> 00:25:46,500
O primeiro pai nunca, assim como o grande-grande-grande-grande-avô

316
00:25:46,500 --> 00:25:52,130
ou árvore avó, primeiro temos que libertar-se os primeiros níveis.

317
00:25:52,130 --> 00:25:58,490
Então, atravessar para o fundo, sem aqueles, e em seguida, voltar-se, livre daqueles, etc

318
00:26:00,400 --> 00:26:02,210
Então, isso é árvore.

319
00:26:02,210 --> 00:26:04,240
>> Agora vamos olhar para floresta.

320
00:26:04,240 --> 00:26:09,860
Floresta é onde você coloca todas suas árvores de Huffman.

321
00:26:09,860 --> 00:26:12,910
Ele está dizendo que nós vamos ter uma coisa chamada trama

322
00:26:12,910 --> 00:26:22,320
que contém um apontador para uma árvore, assim como um indicador para uma trama chamada seguinte.

323
00:26:22,320 --> 00:26:28,480
Que estrutura faz esse tipo de olhar como?

324
00:26:29,870 --> 00:26:32,490
É o tipo de diz por lá.

325
00:26:34,640 --> 00:26:36,700
Bem aqui.

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

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

328
00:26:44,590 --> 00:26:53,020
A floresta é definida como uma lista ligada de parcelas,

329
00:26:53,020 --> 00:26:58,100
e assim a estrutura da floresta é que estamos indo só para ter um ponteiro para o nosso primeiro lote

330
00:26:58,100 --> 00:27:02,740
e que a trama tem uma árvore dentro dele, ou melhor aponta para uma árvore

331
00:27:02,740 --> 00:27:06,190
e, em seguida, aponta para o lote seguinte, assim por diante e assim por diante.

332
00:27:06,190 --> 00:27:11,100
Para fazer uma floresta que chamamos mkforest.

333
00:27:11,100 --> 00:27:14,930
Então, temos algumas funções muito úteis aqui.

334
00:27:14,930 --> 00:27:23,240
Temos escolher onde você passa em uma floresta e, em seguida, o valor de retorno é um * Árvore,

335
00:27:23,240 --> 00:27:25,210
um ponteiro para uma árvore.

336
00:27:25,210 --> 00:27:29,370
O que vai fazer é escolher ele vai para a floresta que você está apontando para

337
00:27:29,370 --> 00:27:35,240
em seguida, remover uma árvore com a menor freqüência do que a floresta

338
00:27:35,240 --> 00:27:38,330
e depois dar-lhe o ponteiro para essa árvore.

339
00:27:38,330 --> 00:27:43,030
Uma vez que você chama de escolher, a árvore não vai existir na floresta mais,

340
00:27:43,030 --> 00:27:48,550
mas o valor de retorno é o ponteiro para a árvore.

341
00:27:48,550 --> 00:27:50,730
Então você tem planta.

342
00:27:50,730 --> 00:27:57,420
Desde que você passar em um ponteiro para uma árvore que tem uma frequência não-0,

343
00:27:57,420 --> 00:28:04,040
que planta vai fazer é que vai demorar a floresta, tomar a árvore, e planta que árvore dentro da floresta.

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

345
00:28:06,370 --> 00:28:11,480
Similar para remover árvore, que, basicamente, libertou todos os nossos árvores para nós,

346
00:28:11,480 --> 00:28:16,600
remover floresta vai tudo livre contida na floresta.

347
00:28:16,600 --> 00:28:24,890
>> Se olharmos para forest.c, vamos esperar para ver pelo menos um comando rmtree lá,

348
00:28:24,890 --> 00:28:30,090
porque a memória livre na floresta se uma floresta tem árvores em que,

349
00:28:30,090 --> 00:28:32,930
depois, eventualmente, você vai ter que remover as árvores também.

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

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

352
00:28:42,890 --> 00:28:51,740
Nós inicializar a primeira parcela na floresta como NULL porque ele está vazio, para começar,

353
00:28:51,740 --> 00:29:05,940
então vemos picareta, que retorna a árvore com o menor peso, a menor freqüência,

354
00:29:05,940 --> 00:29:13,560
e então se livrar desse nó especial que aponta para que a árvore eo próximo,

355
00:29:13,560 --> 00:29:16,760
por isso é preciso que fora da lista vinculada da floresta.

356
00:29:16,760 --> 00:29:24,510
E então aqui temos planta, que insere uma árvore para a lista ligada.

357
00:29:24,510 --> 00:29:29,960
O que mata não é bem mantém classificados para nós.

358
00:29:29,960 --> 00:29:37,910
E, em seguida, finalmente, temos rmforest e, como esperado, temos chamado rmtree lá.

359
00:29:46,650 --> 00:29:55,440
>> Olhando para o código de distribuição, até agora, huffile.c foi provavelmente, de longe, o mais difícil de entender,

360
00:29:55,440 --> 00:29:59,990
enquanto que os outros arquivos em si eram bem simples de seguir.

361
00:29:59,990 --> 00:30:03,090
Com o nosso conhecimento de ponteiros e listas ligadas e tal,

362
00:30:03,090 --> 00:30:04,860
fomos capazes de acompanhar muito bem.

363
00:30:04,860 --> 00:30:10,500
Mas tudo o que precisamos para realmente ter certeza de que compreendemos plenamente. São os arquivos h

364
00:30:10,500 --> 00:30:15,840
porque você precisa estar chamando essas funções, lidar com esses valores de retorno,

365
00:30:15,840 --> 00:30:20,590
para se certificar que você entendeu o que a ação vai ser realizada

366
00:30:20,590 --> 00:30:24,290
sempre que você chamar uma dessas funções.

367
00:30:24,290 --> 00:30:33,020
Mas, na verdade, o entendimento dentro do que não é absolutamente necessário, porque temos aqueles. Arquivos h.

368
00:30:35,170 --> 00:30:39,490
Temos mais dois arquivos deixados em nosso código de distribuição.

369
00:30:39,490 --> 00:30:41,640
>> Vamos olhar para despejo.

370
00:30:41,640 --> 00:30:47,230
Despejo por seu comentário aqui leva um arquivo Huffman-comprimido

371
00:30:47,230 --> 00:30:55,580
e, em seguida, traduz e depósitos de todo o seu conteúdo para fora.

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

373
00:31:04,260 --> 00:31:10,770
Esta é uma espécie de espelhamento para arquivo de entrada * = fopen,

374
00:31:10,770 --> 00:31:13,500
e então você passa a informação.

375
00:31:13,500 --> 00:31:18,240
É quase idêntico, exceto em vez de um * arquivo que você está passando em um Huffile;

376
00:31:18,240 --> 00:31:22,030
em vez de fopen você está passando em hfopen.

377
00:31:22,030 --> 00:31:29,280
Aqui lemos no cabeçalho do primeiro, que é uma espécie de similar a como se lê no cabeçalho

378
00:31:29,280 --> 00:31:33,580
para um arquivo bitmap.

379
00:31:33,580 --> 00:31:38,000
O que estamos fazendo aqui é verificar para ver se as informações de cabeçalho

380
00:31:38,000 --> 00:31:44,330
contém o número mágico direito que indica que é um arquivo de Huff real,

381
00:31:44,330 --> 00:31:53,610
em seguida, todas essas verificações para certificar-se de que o arquivo que é aberto um arquivo real xingou ou não.

382
00:31:53,610 --> 00:32:05,330
O que isto significa é que gera as freqüências de todos os símbolos que podemos ver

383
00:32:05,330 --> 00:32:09,790
dentro de um terminal para uma tabela 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
Ele tem um pouco e lê pouco a pouco para o pouco variável e imprime-o.

386
00:32:28,220 --> 00:32:35,430
Então, se eu fosse chamar despejo em hth.bin, que é o resultado de um arquivo huffing

387
00:32:35,430 --> 00:32:39,490
utilizando a solução pessoal, gostaria de obter isso.

388
00:32:39,490 --> 00:32:46,000
É a saída de todos esses personagens e depois colocar a freqüência em que eles aparecem.

389
00:32:46,000 --> 00:32:51,180
Se olharmos, a maioria deles são 0s exceto para isso: H, que aparece duas vezes,

390
00:32:51,180 --> 00:32:54,820
T e, em seguida, uma vez que aparece.

391
00:32:54,820 --> 00:33:07,860
E aqui temos a verdadeira mensagem em 0s e 1s.

392
00:33:07,860 --> 00:33:15,450
Se olharmos para hth.txt, que é provavelmente a mensagem original que foi bufou,

393
00:33:15,450 --> 00:33:22,490
esperamos ver alguns Hs e Ts lá.

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

395
00:33:32,510 --> 00:33:37,440
Aqui estamos em hth.txt. De fato, tem HTH.

396
00:33:37,440 --> 00:33:41,270
Incluído em, embora não possamos vê-lo, é um caractere de nova linha.

397
00:33:41,270 --> 00:33:53,190
O hth.bin arquivo Huff também é a codificação de caracteres de nova linha também.

398
00:33:55,680 --> 00:34:01,330
Aqui porque sabemos que a ordem é HTH e depois de nova linha,

399
00:34:01,330 --> 00:34:07,340
podemos ver que, provavelmente, o H é representado por apenas um único 1

400
00:34:07,340 --> 00:34:17,120
e, em seguida, o T é provavelmente 01 e, em seguida, o seguinte é um H, bem

401
00:34:17,120 --> 00:34:21,139
e então temos uma nova linha indicada por dois 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> E então, finalmente, arquivos, porque estamos lidando com múltiplas. C e. H,

404
00:34:31,600 --> 00:34:36,350
nós vamos ter um argumento muito complexo para o compilador,

405
00:34:36,350 --> 00:34:40,460
e aqui temos um Makefile que faz despejo para você.

406
00:34:40,460 --> 00:34:47,070
Mas, na verdade, você tem que ir sobre como fazer seu próprio arquivo puff.c.

407
00:34:47,070 --> 00:34:54,330
O Makefile na verdade, não se trata de fazer puff.c para você.

408
00:34:54,330 --> 00:34:59,310
Estamos deixando isso para você editar o Makefile.

409
00:34:59,310 --> 00:35:05,930
Quando você digita um comando como fazer tudo, por exemplo, ele vai fazer todos eles para você.

410
00:35:05,930 --> 00:35:10,760
Sinta-se livre para olhar para os exemplos de Makefile das pset passado

411
00:35:10,760 --> 00:35:17,400
bem como sair de um presente para ver como você pode ser capaz de fazer 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 isso para o nosso código de distribuição.

414
00:35:22,730 --> 00:35:28,380
>> Uma vez que temos obtido através disso, então aqui é só mais um lembrete

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

416
00:35:30,980 --> 00:35:35,400
Nós não vamos estar chamando-os de nós mais, nós vamos estar chamando-os de árvores

417
00:35:35,400 --> 00:35:39,260
onde vamos estar representando seu símbolo com um char,

418
00:35:39,260 --> 00:35:43,340
a sua frequência, o número de ocorrências, com um número inteiro.

419
00:35:43,340 --> 00:35:47,370
Nós estamos usando isso porque é mais preciso do que um carro alegórico.

420
00:35:47,370 --> 00:35:52,980
E então nós temos um outro ponteiro para o filho esquerdo, bem como o direito da criança.

421
00:35:52,980 --> 00:35:59,630
Uma floresta, como vimos, é apenas uma lista encadeada de árvores.

422
00:35:59,630 --> 00:36:04,670
Por fim, quando estamos construindo o nosso arquivo Huff,

423
00:36:04,670 --> 00:36:07,580
queremos que a nossa floresta para conter apenas uma árvore 1 -

424
00:36:07,580 --> 00:36:12,420
Uma árvore, uma raiz com vários filhos.

425
00:36:12,420 --> 00:36:20,840
No início de quando estávamos fazendo nossas árvores de Huffman,

426
00:36:20,840 --> 00:36:25,360
começamos por colocar todos os nós em nossa tela

427
00:36:25,360 --> 00:36:27,790
e dizendo que nós vamos ter esses nós,

428
00:36:27,790 --> 00:36:32,920
eventualmente, eles vão ser as folhas, e este é o seu símbolo, esta é a sua freqüência.

429
00:36:32,920 --> 00:36:42,070
Em nossa floresta se só temos 3 letras, que é uma floresta de três árvores.

430
00:36:42,070 --> 00:36:45,150
E então, como vamos, quando adicionamos o primeiro pai,

431
00:36:45,150 --> 00:36:48,080
fizemos uma floresta de duas árvores.

432
00:36:48,080 --> 00:36:54,930
Nós removemos 2 das crianças da nossa floresta e, em seguida, substituí-lo com um nó pai

433
00:36:54,930 --> 00:36:58,820
que tinha esses dois nós como filhos.

434
00:36:58,820 --> 00:37:05,600
E então, finalmente, o nosso último passo com fazer o nosso exemplo, com o As, Bs e Cs

435
00:37:05,600 --> 00:37:08,030
seria tornar o progenitor final,

436
00:37:08,030 --> 00:37:13,190
e assim, então, que iria trazer a nossa contagem total de árvores na floresta para 1.

437
00:37:13,190 --> 00:37:18,140
Será que todo mundo ver como você começa com várias árvores em sua floresta

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

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

440
00:37:28,110 --> 00:37:37,110
O que precisamos fazer é garantir que, como sempre, eles nos dão o direito tipo de entrada

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

442
00:37:39,090 --> 00:37:43,130
Neste caso, eles vão estar dando-nos após seu argumento de linha de comando primeiro

443
00:37:43,130 --> 00:37:53,440
2 mais: o arquivo que queremos descomprimir e a saída do arquivo descompactado.

444
00:37:53,440 --> 00:38:00,410
Mas uma vez que nós temos certeza que eles passam-nos a quantidade certa de valores,

445
00:38:00,410 --> 00:38:05,820
queremos garantir que a entrada é um arquivo Huff ou não.

446
00:38:05,820 --> 00:38:10,420
E então, uma vez que garante que é um arquivo de Huff, então nós queremos construir a nossa árvore,

447
00:38:10,420 --> 00:38:20,940
construir a árvore de tal forma que ele corresponda a árvore que a pessoa que enviou a mensagem construída.

448
00:38:20,940 --> 00:38:25,840
Em seguida, depois de construir a árvore, então podemos lidar com o, 0s e 1s que eles passaram em

449
00:38:25,840 --> 00:38:29,590
seguir aqueles ao longo da nossa árvore porque é idêntico,

450
00:38:29,590 --> 00:38:33,510
e em seguida, escrever essa mensagem, interpretar os bits de volta para chars.

451
00:38:33,510 --> 00:38:35,880
E então, no final, porque estamos lidando com ponteiros aqui,

452
00:38:35,880 --> 00:38:38,110
nós queremos ter certeza de que não temos quaisquer vazamentos de memória

453
00:38:38,110 --> 00:38:41,330
e que tudo livre.

454
00:38:42,820 --> 00:38:46,430
>> Garantir o uso adequado é velho chapéu para nós agora.

455
00:38:46,430 --> 00:38:51,980
Nós levamos em uma entrada, que vai ser o nome do arquivo a soprar,

456
00:38:51,980 --> 00:38:56,010
e, então, especificar uma saída,

457
00:38:56,010 --> 00:39:01,580
de modo 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
Isso é uso. E agora queremos garantir que a entrada é xingou ou não.

459
00:39:08,820 --> 00:39:16,420
Pensando bem, estava lá nada no código de distribuição que pode nos ajudar a

460
00:39:16,420 --> 00:39:21,570
com a compreensão se um arquivo é xingou ou não?

461
00:39:21,570 --> 00:39:26,910
Houve informações sobre o huffile.c Huffeader.

462
00:39:26,910 --> 00:39:33,430
Nós sabemos que cada arquivo tem um Huff Huffeader associada com um número mágico

463
00:39:33,430 --> 00:39:37,240
, bem como uma matriz de as frequências para cada símbolo

464
00:39:37,240 --> 00:39:39,570
, bem como uma soma de verificação.

465
00:39:39,570 --> 00:39:43,180
Nós sabemos disso, mas nós também levou uma olhada em dump.c,

466
00:39:43,180 --> 00:39:49,120
no qual se lê em um arquivo Huff.

467
00:39:49,120 --> 00:39:53,990
E assim, para fazer isso, tinha que verificar se ele realmente foi xingou ou não.

468
00:39:53,990 --> 00:40:03,380
Então, talvez pudéssemos usar dump.c como uma estrutura para o nosso puff.c.

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

470
00:40:12,680 --> 00:40:14,860
e interpretamos que para Whodunit e Redimensionar,

471
00:40:14,860 --> 00:40:20,390
Da mesma forma, o que você poderia fazer é executar o comando como cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
e usar parte do código lá.

473
00:40:23,600 --> 00:40:28,210
No entanto, não vai ser tão simples de um processo

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

475
00:40:33,010 --> 00:40:36,160
mas pelo menos ele dá-lhe um lugar para começar

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

477
00:40:40,540 --> 00:40:43,240
bem como algumas outras coisas.

478
00:40:45,930 --> 00:40:50,250
Temos assegurado o uso adequado e garantiu que a entrada é bufou.

479
00:40:50,250 --> 00:40:53,570
Toda vez que fizemos o que fizemos nossa verificação de erro adequada,

480
00:40:53,570 --> 00:41:01,520
para retornar e encerrar a função se alguma falha ocorre, se há um problema.

481
00:41:01,520 --> 00:41:07,170
>> Agora, o que nós queremos fazer é construir a árvore real.

482
00:41:08,840 --> 00:41:12,640
Se olharmos em Floresta, há duas principais funções

483
00:41:12,640 --> 00:41:15,800
que vamos querer tornar-se muito familiarizado.

484
00:41:15,800 --> 00:41:23,870
Há a planta função booleana que planta uma árvore de freqüência não-0 dentro de nossa floresta.

485
00:41:23,870 --> 00:41:29,250
E assim, lá você passar em um ponteiro para uma floresta e um ponteiro para uma árvore.

486
00:41:32,530 --> 00:41:40,340
Pergunta rápida: Quantos florestas que você tem quando você está construindo uma árvore de Huffman?

487
00:41:44,210 --> 00:41:46,650
A nossa floresta é como a nossa tela, certo?

488
00:41:46,650 --> 00:41:50,800
Então, nós estamos indo só para ter uma floresta, mas vamos ter várias árvores.

489
00:41:50,800 --> 00:41:57,590
Então, antes de chamar planta, você está provavelmente vai querer fazer sua floresta.

490
00:41:57,590 --> 00:42:04,430
Há um comando para que, se você olhar para forest.h de como você pode fazer uma floresta.

491
00:42:04,430 --> 00:42:09,270
Você pode plantar uma árvore. Nós sabemos como fazer isso.

492
00:42:09,270 --> 00:42:11,590
E então você também pode escolher uma árvore da floresta,

493
00:42:11,590 --> 00:42:17,540
remoção de uma árvore com o menor peso e dando-lhe o ponteiro para isso.

494
00:42:17,540 --> 00:42:23,090
Pensando quando estávamos fazendo os exemplos de nós mesmos,

495
00:42:23,090 --> 00:42:27,980
quando estávamos desenhando-o para fora, nós simplesmente acabou de adicionar os links.

496
00:42:27,980 --> 00:42:31,680
Mas aqui, em vez de apenas adicionar os links,

497
00:42:31,680 --> 00:42:40,630
pensar mais como você está removendo dois desses nós e, em seguida, substituí-lo por outro.

498
00:42:40,630 --> 00:42:44,200
Para expressar isso em termos de colheita e plantio,

499
00:42:44,200 --> 00:42:48,840
você está escolhendo duas árvores e plantar outra árvore

500
00:42:48,840 --> 00:42:54,060
que tenha essas duas árvores que você escolheu como crianças.

501
00:42:57,950 --> 00:43:05,280
Para construir árvore de Huffman, você pode ler nos símbolos e freqüências em ordem

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

503
00:43:10,790 --> 00:43:14,250
dá-lhe um conjunto de frequências.

504
00:43:14,250 --> 00:43:19,660
Então você pode ir em frente e simplesmente ignorar qualquer coisa com a 0 nele

505
00:43:19,660 --> 00:43:23,760
porque não queremos 256 folhas no final do mesmo.

506
00:43:23,760 --> 00:43:27,960
Nós só queremos o número de folhas que são personagens

507
00:43:27,960 --> 00:43:31,600
que são realmente utilizados no arquivo.

508
00:43:31,600 --> 00:43:37,590
Você pode ler nesses símbolos, e cada um desses símbolos que têm freqüências não-0,

509
00:43:37,590 --> 00:43:40,440
aqueles vão ser árvores.

510
00:43:40,440 --> 00:43:45,990
O que você pode fazer é toda vez que você ler em um símbolo de frequências não-0,

511
00:43:45,990 --> 00:43:50,660
você pode plantar a árvore na floresta.

512
00:43:50,660 --> 00:43:56,620
Depois de plantar as árvores na floresta, você pode juntar essas árvores como irmãos,

513
00:43:56,620 --> 00:44:01,130
Então, voltando ao plantio e escolher onde você escolhe 2 e depois planta 1,

514
00:44:01,130 --> 00:44:05,820
onde que uma planta que você é o pai das duas crianças que você escolheu.

515
00:44:05,820 --> 00:44:11,160
Então o resultado final vai ser uma única árvore na floresta.

516
00:44:16,180 --> 00:44:18,170
É como você construir a sua árvore.

517
00:44:18,170 --> 00:44:21,850
>> Há várias coisas que podem dar errado aqui

518
00:44:21,850 --> 00:44:26,580
porque estamos lidando com fazer novas árvores e lidar com ponteiros e coisas assim.

519
00:44:26,580 --> 00:44:30,450
Antes, quando estávamos lidando com ponteiros,

520
00:44:30,450 --> 00:44:36,580
sempre que malloc'd nós queríamos ter certeza de que não nos devolver um valor de ponteiro NULL.

521
00:44:36,580 --> 00:44:42,770
Então, em vários passos dentro deste processo não vão ser vários casos

522
00:44:42,770 --> 00:44:45,920
onde o programa poderia falhar.

523
00:44:45,920 --> 00:44:51,310
O que você quer fazer é que você quer ter certeza de que você lida com esses erros,

524
00:44:51,310 --> 00:44:54,580
e na especificação diz para segurá-los graciosamente,

525
00:44:54,580 --> 00:45:00,280
assim como imprimir uma mensagem para o usuário dizendo-lhes por isso que o programa tem para sair

526
00:45:00,280 --> 00:45:03,050
e então prontamente sair dela.

527
00:45:03,050 --> 00:45:09,490
Para fazer isso o tratamento de erros, lembre-se que você quer verificar se

528
00:45:09,490 --> 00:45:12,160
cada vez que pode haver uma falha.

529
00:45:12,160 --> 00:45:14,660
Toda vez que você está fazendo um novo ponteiro

530
00:45:14,660 --> 00:45:17,040
você quer ter certeza de que isso é sucesso.

531
00:45:17,040 --> 00:45:20,320
Antes que estamos acostumados a fazer é fazer um novo ponteiro e malloc-lo,

532
00:45:20,320 --> 00:45:22,380
e então nós verificar se esse ponteiro é NULL.

533
00:45:22,380 --> 00:45:25,670
Portanto, não vão ser alguns casos em que você só pode fazer isso,

534
00:45:25,670 --> 00:45:28,610
mas às vezes você realmente está chamando uma função

535
00:45:28,610 --> 00:45:33,100
e dentro dessa função, que é a única que está fazendo a mallocing.

536
00:45:33,100 --> 00:45:39,110
Nesse caso, se olharmos para algumas das funções dentro do código,

537
00:45:39,110 --> 00:45:42,260
alguns deles são funções booleanas.

538
00:45:42,260 --> 00:45:48,480
No caso abstrato, se temos uma função booleana chamada foo,

539
00:45:48,480 --> 00:45:54,580
Basicamente, podemos supor que, além de fazer o que faz foo,

540
00:45:54,580 --> 00:45:57,210
já que é uma função booleana, ele retorna verdadeiro ou falso -

541
00:45:57,210 --> 00:46:01,300
verdadeiro caso de sucesso, false se não.

542
00:46:01,300 --> 00:46:06,270
Então, queremos verificar se 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 vamos querer imprimir algum tipo de mensagem

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

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

546
00:46:18,530 --> 00:46:23,310
Se foo retorna falso, então sabemos que encontramos algum tipo de erro

547
00:46:23,310 --> 00:46:25,110
e nós precisamos parar de nosso programa.

548
00:46:25,110 --> 00:46:35,600
Uma maneira de fazer isso é ter uma condição onde a função em si é a sua condição.

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

550
00:46:39,320 --> 00:46:43,390
Podemos ter como condição if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Basicamente, isso significa que se no final da execução de foo ele retorna true,

552
00:46:50,900 --> 00:46:57,390
então podemos fazer isso porque a função tem que avaliar foo

553
00:46:57,390 --> 00:47:00,500
, a fim de avaliar a condição geral.

554
00:47:00,500 --> 00:47:06,500
Então é assim que você pode fazer alguma coisa, se a função retornará verdadeiro e é bem sucedido.

555
00:47:06,500 --> 00:47:11,800
Mas quando você está a verificação de erros, você só quer sair se a sua função retorna falso.

556
00:47:11,800 --> 00:47:16,090
O que você poderia fazer é apenas adicionar um == false ou apenas adicionar um estrondo na frente dele

557
00:47:16,090 --> 00:47:21,010
e então você tem if (! foo).

558
00:47:21,010 --> 00:47:29,540
Dentro desse corpo de que condição você teria todo o tratamento de erros,

559
00:47:29,540 --> 00:47:36,940
assim como, "Não foi possível criar esta árvore" e, em seguida, retornar 1 ou algo assim.

560
00:47:36,940 --> 00:47:43,340
O que faz, porém, é que mesmo 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ão você não tem que chamar foo novamente. Isso é um equívoco comum.

563
00:47:51,060 --> 00:47:54,730
Porque ele estava em sua condição, ele já está avaliado,

564
00:47:54,730 --> 00:47:59,430
Então você já tem o resultado, se você estiver usando tornar árvore ou algo assim

565
00:47:59,430 --> 00:48:01,840
ou planta ou picareta ou algo assim.

566
00:48:01,840 --> 00:48:07,460
Ela já tem esse valor. Ele já está executado.

567
00:48:07,460 --> 00:48:10,730
Por isso, é útil usar funções booleanas como condição

568
00:48:10,730 --> 00:48:13,890
porque se está ou não efectivamente executar o corpo do loop,

569
00:48:13,890 --> 00:48:18,030
ele executa a função de qualquer maneira.

570
00:48:22,070 --> 00:48:27,330
>> Nosso segundo a última etapa é escrever a mensagem para o arquivo.

571
00:48:27,330 --> 00:48:33,070
Uma vez que vamos construir a árvore de Huffman, em seguida, escrever a mensagem para o arquivo é bastante simples.

572
00:48:33,070 --> 00:48:39,260
É muito simples agora para apenas seguir os 0s e 1s.

573
00:48:39,260 --> 00:48:45,480
E assim por convenção, sabemos que em uma árvore Huffman os 0s indicam que deixaram

574
00:48:45,480 --> 00:48:48,360
e os 1s indicam certo.

575
00:48:48,360 --> 00:48:53,540
Então, se você ler em pouco a pouco, cada vez que você receber um 0

576
00:48:53,540 --> 00:48:59,100
você vai seguir o ramo da esquerda, e depois a cada vez que você ler em um 1

577
00:48:59,100 --> 00:49:02,100
você vai seguir o ramo direito.

578
00:49:02,100 --> 00:49:07,570
E então você vai continuar até que você bata uma folha

579
00:49:07,570 --> 00:49:11,550
porque as folhas vão ser no final dos ramos.

580
00:49:11,550 --> 00:49:16,870
Como podemos dizer se nós batemos uma folha ou não?

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

582
00:49:21,690 --> 00:49:24,040
[Aluno] Se os ponteiros são NULL. Sim >>.

583
00:49:24,040 --> 00:49:32,220
Podemos dizer se nós batemos uma folha se os ponteiros para árvores, tanto a esquerda e direita são NULL.

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

585
00:49:34,110 --> 00:49:40,320
Sabemos que queremos ler pouco a pouco em nosso arquivo Huff.

586
00:49:43,870 --> 00:49:51,220
Como vimos antes, em dump.c, o que eles fizeram é que lêem pouco a pouco para o arquivo Huff

587
00:49:51,220 --> 00:49:54,560
e apenas impressos que esses fragmentos eram.

588
00:49:54,560 --> 00:49:58,430
Nós não vamos estar fazendo isso. Nós estamos indo fazer algo que é um pouco mais complexa.

589
00:49:58,430 --> 00:50:03,620
Mas o que podemos fazer é que podemos tomar aquele pedaço de código que lê para o bit.

590
00:50:03,620 --> 00:50:10,250
Aqui nós temos o bit inteiro representando o bit atual que estamos no.

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

592
00:50:15,520 --> 00:50:21,270
Com base nisso, então você vai querer ter algum tipo de iterador

593
00:50:21,270 --> 00:50:26,760
para atravessar a sua árvore.

594
00:50:26,760 --> 00:50:31,460
E, em seguida, com base em se o bit é 0 ou 1,

595
00:50:31,460 --> 00:50:36,920
você vai querer quer mover esse iterador para a esquerda ou movê-lo para a direita

596
00:50:36,920 --> 00:50:44,080
todo o caminho até que você bata uma folha, assim todo o caminho até esse nó que você está em

597
00:50:44,080 --> 00:50:48,260
não apontam para nós mais nada.

598
00:50:48,260 --> 00:50:54,300
Por que podemos fazer isso com um arquivo Huffman mas não o código Morse?

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

600
00:50:56,610 --> 00:51:04,440
Nós poderíamos ser como, oh wait, nós batemos uma carta ao longo do caminho, talvez por isso esta é a nossa carta,

601
00:51:04,440 --> 00:51:08,150
enquanto que, se continuamos mais um pouco, então nós teria atingido outra carta.

602
00:51:08,150 --> 00:51:13,110
Mas isso não vai acontecer em codificação de Huffman,

603
00:51:13,110 --> 00:51:17,540
para que possamos ter certeza de que a única maneira que nós vamos bater um personagem

604
00:51:17,540 --> 00:51:23,480
é se as crianças esquerdo e direito que nós são NULL.

605
00:51:28,280 --> 00:51:32,350
>> Finalmente, queremos libertar toda a nossa memória.

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

607
00:51:37,420 --> 00:51:41,940
bem como remover todas as árvores em nossa floresta.

608
00:51:41,940 --> 00:51:46,470
Com base na sua implementação, você provavelmente vai querer chamar remover floresta

609
00:51:46,470 --> 00:51:49,780
em vez de realmente passar por todas as árvores de si mesmo.

610
00:51:49,780 --> 00:51:53,430
Mas se você fez todas as árvores temporários, você vai querer liberar isso.

611
00:51:53,430 --> 00:51:59,060
Você sabe o seu código de melhor, para que você saiba onde você está alocando memória.

612
00:51:59,060 --> 00:52:04,330
E por isso, se você entrar, começar por até controlar f'ing para malloc,

613
00:52:04,330 --> 00:52:08,330
vendo sempre que malloc e certificando-se de que você libertar de tudo isso

614
00:52:08,330 --> 00:52:10,190
mas então apenas passando por seu código,

615
00:52:10,190 --> 00:52:14,260
entender onde você pode ter alocado memória.

616
00:52:14,260 --> 00:52:21,340
Normalmente você pode apenas dizer: "No final de um arquivo que eu estou indo só para remover floresta em minha floresta",

617
00:52:21,340 --> 00:52:23,850
Então, basicamente claro que a memória livre, que,

618
00:52:23,850 --> 00:52:28,310
"E então eu também estou indo para fechar o arquivo e então o meu programa vai sair."

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

620
00:52:33,810 --> 00:52:37,880
Não, porque, por vezes, pode ter havido um erro que aconteceu.

621
00:52:37,880 --> 00:52:42,080
Talvez a gente não pode abrir um arquivo ou nós não poderíamos fazer de outra árvore

622
00:52:42,080 --> 00:52:49,340
ou algum tipo de erro aconteceu no processo de alocação de memória e por isso retornou NULL.

623
00:52:49,340 --> 00:52:56,710
Um erro aconteceu e, depois, devolvido e saia.

624
00:52:56,710 --> 00:53:02,040
Então você quer ter certeza de que a qualquer momento possível que seu programa pode sair,

625
00:53:02,040 --> 00:53:06,980
você quer libertar toda a sua memória lá.

626
00:53:06,980 --> 00:53:13,370
Não só vai ser no final da função principal que você saia de seu código.

627
00:53:13,370 --> 00:53:20,780
Você quer olhar para trás a cada instância de que seu código potencialmente pode retornar prematuramente

628
00:53:20,780 --> 00:53:25,070
e memória qualquer livre faz sentido.

629
00:53:25,070 --> 00:53:30,830
Digamos que você tinha chamado fazer floresta e que retornou falso.

630
00:53:30,830 --> 00:53:34,230
Então você provavelmente não vai precisar remover a floresta

631
00:53:34,230 --> 00:53:37,080
porque você não tem uma floresta ainda.

632
00:53:37,080 --> 00:53:42,130
Mas em todos os pontos do código onde você pode retornar prematuramente

633
00:53:42,130 --> 00:53:46,160
você quer ter certeza de que você liberar qualquer memória possível.

634
00:53:46,160 --> 00:53:50,020
>> Então, quando estamos lidando com liberar memória e ter vazamentos potenciais,

635
00:53:50,020 --> 00:53:55,440
queremos não só usar nosso julgamento e nossa lógica

636
00:53:55,440 --> 00:54:01,850
mas também usar Valgrind para determinar se nós libertou toda a nossa memória corretamente ou não.

637
00:54:01,850 --> 00:54:09,460
Você pode executar Valgrind em Puff e então você também tem que passá-lo

638
00:54:09,460 --> 00:54:14,020
o número certo de linha de comando argumentos para Valgrind.

639
00:54:14,020 --> 00:54:18,100
Você pode executar isso, mas a saída é um pouco enigmática.

640
00:54:18,100 --> 00:54:21,630
Nós temos tido um pouco acostumado com Speller, mas ainda precisamos de ajuda um pouco mais,

641
00:54:21,630 --> 00:54:26,450
assim então executá-lo com algumas bandeiras, como o vazamento de mais-check = full,

642
00:54:26,450 --> 00:54:32,040
que provavelmente vai nos dar alguma saída mais útil em Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Em seguida, outra dica útil quando você está depurando é o comando diff.

644
00:54:39,040 --> 00:54:48,520
Você pode acessar a implementação do pessoal de Huff, que executar em um arquivo de texto,

645
00:54:48,520 --> 00:54:55,400
e depois a saída para um arquivo binário, um arquivo binário Huff, para ser específico.

646
00:54:55,400 --> 00:54:59,440
Então, se você executar o seu próprio sopro em que o arquivo binário,

647
00:54:59,440 --> 00:55:03,950
em seguida, idealmente, o seu arquivo de texto outputted vai ser idêntico

648
00:55:03,950 --> 00:55:08,200
ao original que você passou dentro

649
00:55:08,200 --> 00:55:15,150
Aqui eu estou usando hth.txt como exemplo, e isso é o que falou em sua especificação.

650
00:55:15,150 --> 00:55:21,040
Isso é literalmente apenas HTH e então uma nova linha.

651
00:55:21,040 --> 00:55:30,970
Mas, definitivamente, se sentir livre e você está definitivamente incentivados a usar exemplos mais

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

653
00:55:32,620 --> 00:55:38,110
>> Você pode até mesmo levar um tiro na talvez comprimir e depois descomprimir

654
00:55:38,110 --> 00:55:41,600
alguns dos arquivos que você usou na Speller como Guerra e Paz

655
00:55:41,600 --> 00:55:46,710
ou Jane Austen, ou algo assim - o que seria bem legal - ou Austin Powers,

656
00:55:46,710 --> 00:55:51,880
tipo de lidar com arquivos maiores porque nós não teríamos chegado até ele

657
00:55:51,880 --> 00:55:55,590
se usamos a ferramenta seguinte aqui, ls-l.

658
00:55:55,590 --> 00:56:01,150
Estamos acostumados a ls, que lista todos basicamente o conteúdo em nosso diretório atual.

659
00:56:01,150 --> 00:56:07,860
Passando o sinalizador-l realmente mostra o tamanho dos arquivos.

660
00:56:07,860 --> 00:56:12,690
Se você passar por a especificação pset, ele realmente percorre a criação do arquivo binário,

661
00:56:12,690 --> 00:56:16,590
de huffing-lo, e você vê que para arquivos muito pequenos

662
00:56:16,590 --> 00:56:23,910
o custo do espaço de comprimi-lo e traduzir toda essa informação

663
00:56:23,910 --> 00:56:26,980
de todas as freqüências e coisas assim supera o benefício real

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

665
00:56:30,000 --> 00:56:37,450
Mas se você executá-lo em alguns arquivos de texto mais longos, então você pode ver que você começa a ter algum benefício

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

667
00:56:40,930 --> 00:56:46,210
>> E então, finalmente, temos o nosso GDB velho amigo, que, certamente, vai vir a calhar também.

668
00:56:48,360 --> 00:56:55,320
>> Não temos qualquer dúvida em árvores Huff ou o processo talvez de fazer as árvores

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

670
00:57:00,680 --> 00:57:02,570
Okay. Eu vou ficar em torno de um bit.

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

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