1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Tutorial - Butlletí de problemes 6]

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

3
00:00:04,810 --> 00:00:07,240
[Aquesta és CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hola a tots i benvinguts a Tutorial 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
En Puff Huff'n el que estem fent estarà tractant amb un arxiu comprimit Huffman

6
00:00:17,440 --> 00:00:20,740
i després bufar una còpia de seguretat, de manera que la descompressió,

7
00:00:20,740 --> 00:00:25,810
pel que podem traduir de el 0 i 1 que l'usuari ens envia

8
00:00:25,810 --> 00:00:30,660
i convertir de nou en el text original.

9
00:00:30,660 --> 00:00:34,360
Pset 6 va a ser molt bo perquè vas a veure algunes de les eines

10
00:00:34,360 --> 00:00:41,730
que va utilitzar en el conjunt de processadors 4 i 5 i el conjunt de processadors tipus de combinació en un concepte bastant net

11
00:00:41,730 --> 00:00:43,830
quan s'arriba a pensar-hi.

12
00:00:43,830 --> 00:00:50,110
>> També, sens dubte, pset 4 i 5 van ser els conjunts de processadors més difícils que hem hagut d'oferir.

13
00:00:50,110 --> 00:00:53,950
Així que a partir d'ara, tenim aquest conjunt de processadors 1 més en C,

14
00:00:53,950 --> 00:00:56,480
i després d'això estem en la programació web.

15
00:00:56,480 --> 00:01:02,310
Així que us felicito per aconseguir sobre la gepa més dura en CS50.

16
00:01:03,630 --> 00:01:09,760
>> Passant per Puff Huff'n, la nostra caixa d'eines per a aquest conjunt de processadors seran arbres de Huffman,

17
00:01:09,760 --> 00:01:14,700
de manera que entendre no només com funcionen els arbres binaris, sinó també específicament arbres Huffman,

18
00:01:14,700 --> 00:01:16,240
com estan construïts.

19
00:01:16,240 --> 00:01:20,210
I llavors tindrem una gran quantitat de codi distribució en aquest conjunt de processadors,

20
00:01:20,210 --> 00:01:22,480
i arribarem a veure que en realitat part del codi

21
00:01:22,480 --> 00:01:24,670
no podria ser capaç d'entendre completament encara,

22
00:01:24,670 --> 00:01:30,080
de manera que aquests seran els arxius. C, però llavors els seus arxius adjunts. h

23
00:01:30,080 --> 00:01:34,300
ens donarà prou coneixement que necessitem perquè puguem saber com aquestes funcions es

24
00:01:34,300 --> 00:01:38,100
o almenys el que han de fer - les entrades i sortides -

25
00:01:38,100 --> 00:01:40,760
encara que no sabem el que està passant en el quadre negre

26
00:01:40,760 --> 00:01:44,090
o no entén el que està passant en el quadre negre en el seu interior.

27
00:01:44,090 --> 00:01:49,400
I, finalment, com sempre, es tracta de noves estructures de dades,

28
00:01:49,400 --> 00:01:51,840
determinats tipus de nodes que apunten a certes coses,

29
00:01:51,840 --> 00:01:56,080
i aquí té una ploma i un paper, no només per al procés de disseny

30
00:01:56,080 --> 00:01:58,470
i quan vostè està tractant d'esbrinar com el conjunt de processadors han de treballar

31
00:01:58,470 --> 00:02:00,520
però també durant la depuració.

32
00:02:00,520 --> 00:02:06,140
Vostè pot tenir GDB amb el seu llapis i paper mentre es pren de manera que els valors són,

33
00:02:06,140 --> 00:02:09,320
on les fletxes estan apuntant, i coses per l'estil.

34
00:02:09,320 --> 00:02:13,720
>> Primer donem una ullada als arbres de Huffman.

35
00:02:13,720 --> 00:02:19,600
Arbres Huffman són arbres binaris, el que significa que cada node només té 2 fills.

36
00:02:19,600 --> 00:02:24,870
En arbres Huffman la característica és que els valors més freqüents

37
00:02:24,870 --> 00:02:27,140
estan representats pels menys bits.

38
00:02:27,140 --> 00:02:32,690
Hem vist en els exemples de conferències de codi Morse, quin tipus de consolidat algunes lletres.

39
00:02:32,690 --> 00:02:38,030
Si vostè està tractant de traduir una A o una E, per exemple,

40
00:02:38,030 --> 00:02:43,940
estàs traduint sovint, així que en lloc d'haver d'utilitzar tot el conjunt de bits

41
00:02:43,940 --> 00:02:48,640
previstes per aquest tipus de dades és habitual, es comprimeix a menys,

42
00:02:48,640 --> 00:02:53,730
i després aquestes cartes que estan representats amb menys freqüència es representen amb més bits d'

43
00:02:53,730 --> 00:02:59,840
ja que pot donar-se el luxe de que quan vostè pesa les freqüències que aquestes cartes apareixen.

44
00:02:59,840 --> 00:03:03,020
Tenim la mateixa idea aquí en els arbres de Huffman

45
00:03:03,020 --> 00:03:12,360
on estem fent una cadena, una mena de camí per arribar als determinats caràcters.

46
00:03:12,360 --> 00:03:14,470
I després els personatges que tenen més freqüència

47
00:03:14,470 --> 00:03:17,940
seran representats amb el menor nombre de bits.

48
00:03:17,940 --> 00:03:22,020
>> La manera com es construeix un arbre de Huffman

49
00:03:22,020 --> 00:03:27,430
és mitjançant la col · locació de tots els caràcters que apareixen en el text

50
00:03:27,430 --> 00:03:30,630
i el càlcul de la seva freqüència, la freqüència amb què apareixen.

51
00:03:30,630 --> 00:03:33,880
Això podria ser un recompte de les vegades que les lletres apareixen

52
00:03:33,880 --> 00:03:40,270
o potser un percentatge d'entre tots els personatges de la quantitat de cada un d'ells apareix.

53
00:03:40,270 --> 00:03:44,270
I així, el que fas és un cop que tens tot això fos assignada,

54
00:03:44,270 --> 00:03:49,060
llavors busqui les 2 freqüències més baixes i després unir-los com a germans

55
00:03:49,060 --> 00:03:55,660
on llavors el node pare té una freqüència que és la suma dels seus 2 nens.

56
00:03:55,660 --> 00:04:00,870
I llavors, per convenció, dir que el node esquerre,

57
00:04:00,870 --> 00:04:03,770
vostè segueix que, seguint la ramificació 0,

58
00:04:03,770 --> 00:04:08,140
i després el node més a la dreta és la branca 1.

59
00:04:08,140 --> 00:04:16,040
Com hem vist al codi Morse, el Gotcha una era que si tenies un bip bip i el

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

61
00:04:18,120 --> 00:04:22,430
És ben podria ser 1 carta o podria ser una seqüència de lletres 2.

62
00:04:22,430 --> 00:04:27,790
I què arbres Huffman fa és perquè per la naturalesa dels personatges

63
00:04:27,790 --> 00:04:34,140
o la final els personatges reals que són els nodes anteriors en el ram -

64
00:04:34,140 --> 00:04:39,300
ens referim a aquelles com fulles - en virtut que no hi pot haver cap ambigüitat

65
00:04:39,300 --> 00:04:45,160
en termes de la carta que vostè està tractant de codificar amb la sèrie de bits

66
00:04:45,160 --> 00:04:50,670
perquè enlloc al llarg dels bits que representen una carta

67
00:04:50,670 --> 00:04:55,960
es troba una altra carta sencera, i no hi haurà cap confusió allà.

68
00:04:55,960 --> 00:04:58,430
Però entrarem en exemples que vostès poden veure realment que

69
00:04:58,430 --> 00:05:02,120
en lloc de nosaltres simplement li diu que això és cert.

70
00:05:02,120 --> 00:05:06,390
>> Vegem un exemple simple d'un arbre de Huffman.

71
00:05:06,390 --> 00:05:09,380
Tinc una cadena que aquí és de 12 caràcters.

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

73
00:05:14,010 --> 00:05:17,270
El meu primer pas seria comptar.

74
00:05:17,270 --> 00:05:20,760
Quantes vegades Una aparèixer? Sembla 4 vegades a la cadena.

75
00:05:20,760 --> 00:05:25,060
B apareix 6 vegades, i C apareix 2 vegades.

76
00:05:25,060 --> 00:05:28,970
Naturalment, jo vaig a dir que estic fent servir B amb més freqüència,

77
00:05:28,970 --> 00:05:35,970
així que vull representar B amb el menor nombre de bits, el menor nombre de 0s i 1s.

78
00:05:35,970 --> 00:05:42,600
I llavors jo també esperaré C i requereixen major quantitat de 0s i 1s també.

79
00:05:42,600 --> 00:05:48,550
En primer lloc el que vaig fer aquí els vaig posar en ordre ascendent en termes de freqüència.

80
00:05:48,550 --> 00:05:52,710
Veiem que la C i l'A, aquestes són les nostres dues freqüències més baixes.

81
00:05:52,710 --> 00:06:00,290
Creem un node pare, i que el node pare no té una carta associada a ell,

82
00:06:00,290 --> 00:06:05,070
però té una freqüència, que és la suma.

83
00:06:05,070 --> 00:06:08,780
La suma esdevé 2 + 4, que és 6.

84
00:06:08,780 --> 00:06:10,800
Després seguim la branca esquerra.

85
00:06:10,800 --> 00:06:14,970
Si estiguéssim en aquest node 6, llavors seguiríem 0 a arribar a C

86
00:06:14,970 --> 00:06:17,450
i després 1 per arribar a A.

87
00:06:17,450 --> 00:06:20,300
Així que ara tenim dos nodes.

88
00:06:20,300 --> 00:06:23,920
Tenim el valor 6 i després també tenim un altre node amb el valor 6.

89
00:06:23,920 --> 00:06:28,550
I així, els dos no són només el més baix 2, però també només el 2 que queden,

90
00:06:28,550 --> 00:06:33,820
Per això amb els d'altres pares, amb la suma és 12.

91
00:06:33,820 --> 00:06:36,300
Així que aquí tenim el nostre arbre de Huffman

92
00:06:36,300 --> 00:06:40,020
on per arribar a B, que no seria més que el bit 1

93
00:06:40,020 --> 00:06:45,430
i després d'arribar a un tindríem 01 i després C, amb 00.

94
00:06:45,430 --> 00:06:51,300
Així que aquí veiem que bàsicament estem representant aquests caràcters amb 1 o 2 bits

95
00:06:51,300 --> 00:06:55,160
on el B, com es va predir, té la menor.

96
00:06:55,160 --> 00:07:01,730
I llavors el que esperàvem C als que més tenen, però ja que és un petit arbre de Huffman,

97
00:07:01,730 --> 00:07:06,020
A continuació, el també està representat per 2 bits en lloc de en algun lloc en el medi.

98
00:07:07,820 --> 00:07:11,070
>> Només per repassar altre exemple simple de l'arbre de Huffman,

99
00:07:11,070 --> 00:07:19,570
diu que té la cadena "Hola".

100
00:07:19,570 --> 00:07:25,360
El que fa és primer que diria quantes vegades H apareguin en el present?

101
00:07:25,360 --> 00:07:34,200
H apareix una vegada i després i apareix una vegada i després tenim l apareix dues vegades

102
00:07:34,200 --> 00:07:36,580
i o una vegada que apareix.

103
00:07:36,580 --> 00:07:44,310
I llavors esperem que la carta de ser representat pel menor nombre de bits?

104
00:07:44,310 --> 00:07:47,450
[Estudiant] l. >> L. Si. l és correcte.

105
00:07:47,450 --> 00:07:50,730
Esperem l a estar representat pel menor nombre de bits

106
00:07:50,730 --> 00:07:55,890
perquè l s'utilitza més en la cadena "Hola".

107
00:07:55,890 --> 00:08:04,280
Què faré ara és treure aquests nodes.

108
00:08:04,280 --> 00:08:15,580
Tinc 1, que és H, i després un altre 1, que és i, i després un 1, que és O -

109
00:08:15,580 --> 00:08:23,410
ara mateix m'estic posant en ordre - i després 2, que és l.

110
00:08:23,410 --> 00:08:32,799
Llavors em diuen que el camí que vaig a construir un arbre de Huffman és trobar els 2 nodes que tenen menys freqüències

111
00:08:32,799 --> 00:08:38,010
i fer-los germans mitjançant la creació d'un node pare.

112
00:08:38,010 --> 00:08:41,850
Aquí tenim 3 nodes amb la freqüència més baixa. Són tots 1.

113
00:08:41,850 --> 00:08:50,620
Així que aquí hem de triar un que anem a vincular primer.

114
00:08:50,620 --> 00:08:54,850
Diguem de triar l'H i el correu.

115
00:08:54,850 --> 00:09:01,150
La suma de 1 + 1 és 2, però aquest node no té una lletra associada amb ella.

116
00:09:01,150 --> 00:09:04,440
Només té el valor.

117
00:09:04,440 --> 00:09:10,950
Ara ens centrarem en els propers 2 freqüències més baixes.

118
00:09:10,950 --> 00:09:15,590
Això és 2 i 1. Això podria ser qualsevol dels 2, però jo vaig a triar aquest.

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

120
00:09:18,800 --> 00:09:26,410
I, finalment, només tinc 2 a l'esquerra, de manera que es converteix després 5.

121
00:09:26,410 --> 00:09:32,010
Llavors aquí, com era d'esperar, si compliment la codificació perquè,

122
00:09:32,010 --> 00:09:37,480
1s sempre la branca dreta i 0s són el de l'esquerra.

123
00:09:37,480 --> 00:09:45,880
Llavors tenim l representada per només 1 bit i després o el 2 per

124
00:09:45,880 --> 00:09:52,360
i llavors el correu per 2 i després el H cau a 3 bits.

125
00:09:52,360 --> 00:09:59,750
Així que vostè pot transmetre aquest missatge "Hola" en lloc d'utilitzar realment els personatges

126
00:09:59,750 --> 00:10:02,760
amb només 0s i 1s.

127
00:10:02,760 --> 00:10:07,910
No obstant això, recordeu que en diversos casos hem tingut llaços amb la nostra freqüència.

128
00:10:07,910 --> 00:10:11,900
Podríem haver ni es va unir a la H i O potser el primer.

129
00:10:11,900 --> 00:10:15,730
O llavors més endavant, quan vam tenir la l representat per 2

130
00:10:15,730 --> 00:10:19,410
així com el unit 01:00 representat per 2, podríem haver vinculat qualsevol d'ells.

131
00:10:19,410 --> 00:10:23,630
>> I així, quan s'envia el 0 i 1, que en realitat no garanteix

132
00:10:23,630 --> 00:10:27,090
que el destinatari pot llegir completament el missatge tot d'

133
00:10:27,090 --> 00:10:30,490
perquè no es pot saber quina decisió que ha realitzat.

134
00:10:30,490 --> 00:10:34,920
Així que quan ens enfrontem amb la compressió Huffman,

135
00:10:34,920 --> 00:10:40,090
d'alguna manera hem de dir-li al receptor del nostre missatge com decidim -

136
00:10:40,090 --> 00:10:43,470
Necessita saber algun tipus d'informació addicional

137
00:10:43,470 --> 00:10:46,580
A més del missatge comprimit.

138
00:10:46,580 --> 00:10:51,490
Ells necessiten entendre el que l'arbre es veu realment com,

139
00:10:51,490 --> 00:10:55,450
la manera com realment va fer aquestes decisions.

140
00:10:55,450 --> 00:10:59,100
>> Aquí estàvem fent exemples basats en el recompte real,

141
00:10:59,100 --> 00:11:01,550
però de vegades també pot tenir un arbre de Huffman

142
00:11:01,550 --> 00:11:05,760
basat en la freqüència amb què apareixen les lletres, i és exactament el mateix procés.

143
00:11:05,760 --> 00:11:09,090
Aquí m'estic expressant en termes de percentatges o fracció,

144
00:11:09,090 --> 00:11:11,290
i aquí exactament el mateix.

145
00:11:11,290 --> 00:11:15,300
Em sembla el més baix 2, els suma, la més baixa 2 següent, sumar-los,

146
00:11:15,300 --> 00:11:19,390
fins que tingui un arbre.

147
00:11:19,390 --> 00:11:23,610
Tot i que podria fer-ho de qualsevol manera, quan estem tractant amb percentatges,

148
00:11:23,610 --> 00:11:27,760
això vol dir que estem dividint les coses i tractar amb decimals o més aviat flota

149
00:11:27,760 --> 00:11:30,900
si estem pensant en estructures de dades d'un cap.

150
00:11:30,900 --> 00:11:32,540
Què sabem sobre els flotadors?

151
00:11:32,540 --> 00:11:35,180
Què és un problema comú quan ens enfrontem amb flotadors?

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

153
00:11:38,600 --> 00:11:43,760
A causa de la imprecisió de coma flotant, per aquest conjunt de processadors de manera que ens assegurem

154
00:11:43,760 --> 00:11:49,450
que no es perd cap valor, llavors estem realment estarà tractant amb el comte.

155
00:11:49,450 --> 00:11:54,880
Així que si vostè anés a pensar en un node Huffman, si mirem cap enrere a l'estructura d'aquí,

156
00:11:54,880 --> 00:12:01,740
si ens fixem en els verds té una freqüència associada a ella

157
00:12:01,740 --> 00:12:08,760
així com que apunta a un node a la seva esquerra, així com un node a la seva dreta.

158
00:12:08,760 --> 00:12:13,970
I a continuació, els vermells no tenen també un caràcter associat amb ells.

159
00:12:13,970 --> 00:12:18,900
No farem altres diferents per als pares i després els nodes finals,

160
00:12:18,900 --> 00:12:23,680
la qual ens referim com fulles, sinó més aviat els que acaben tindran valors NULL.

161
00:12:23,680 --> 00:12:31,050
Per cada node que tindrem un caràcter, el símbol que representa aquest node,

162
00:12:31,050 --> 00:12:40,490
a continuació, una freqüència, així com un punter al seu fill esquerre, així com el seu fill dret.

163
00:12:40,490 --> 00:12:45,680
Les fulles, que es troben a la part inferior, també tindria punters a nodes

164
00:12:45,680 --> 00:12:49,550
a la seva esquerra ia la seva dreta, però ja que aquests valors no estan apuntant als nodes reals,

165
00:12:49,550 --> 00:12:53,970
qual cosa el seu valor sigui? >> [Estudiant] NULL. >> NULL. Exactament.

166
00:12:53,970 --> 00:12:58,430
Heus aquí un exemple de com es pot representar la freqüència en carrosses,

167
00:12:58,430 --> 00:13:02,130
però anem a tractar amb ell amb nombres enters,

168
00:13:02,130 --> 00:13:06,780
així que tot el que he fet és canviar el tipus de dades allà.

169
00:13:06,780 --> 00:13:09,700
>> Anirem a una mica més d'un exemple complex.

170
00:13:09,700 --> 00:13:13,360
Però ara que hem fet els més simples, és només el mateix procés.

171
00:13:13,360 --> 00:13:20,290
Trobareu les 2 freqüències més baixes, sumi les freqüències

172
00:13:20,290 --> 00:13:22,450
i aquesta és la nova freqüència del seu node pare,

173
00:13:22,450 --> 00:13:29,310
que al seu torn apunta a la seva esquerra amb la ramificació 0 i el dret a la sucursal 1.

174
00:13:29,310 --> 00:13:34,200
Si tenim la cadena "This is CS50", llavors compti les vegades que s'esmenta T,

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

176
00:13:38,420 --> 00:13:42,010
Llavors el que vaig fer aquí és amb els nodes vermells Acabo de plantats,

177
00:13:42,010 --> 00:13:48,530
He dit que vaig a tenir aquests personatges finalment al fons del meu arbre.

178
00:13:48,530 --> 00:13:51,740
Els que seran tots els fulls.

179
00:13:51,740 --> 00:13:58,200
Llavors el que vaig fer és que ells ordenats per freqüència en ordre ascendent,

180
00:13:58,200 --> 00:14:02,950
i això és en realitat la forma en què el codi de conjunt de processadors que fa

181
00:14:02,950 --> 00:14:07,550
Val la classe de freqüència i després per ordre alfabètic.

182
00:14:07,550 --> 00:14:13,870
Per tant, té els números primer i després alfabèticament per la freqüència.

183
00:14:13,870 --> 00:14:18,520
Llavors el que jo faria és que anava a trobar la més baixa 2. Això és 0 i 5.

184
00:14:18,520 --> 00:14:22,390
Jo els suma, i això és 2. A continuació, m'agradaria seguir, trobar el proper 2 baix.

185
00:14:22,390 --> 00:14:26,100
Aquests són els dos 1s, i després convertir-se en els 2 també.

186
00:14:26,100 --> 00:14:31,570
Ara sé que el meu pròxim pas va a unir-se a la xifra més baixa,

187
00:14:31,570 --> 00:14:41,380
que és la T, l'1, i després triar un dels nodes que té 2 com la freqüència.

188
00:14:41,380 --> 00:14:44,560
Així que aquí tenim 3 opcions.

189
00:14:44,560 --> 00:14:47,980
El que vaig a fer pel tobogan és només visualment reordenar per a vostè

190
00:14:47,980 --> 00:14:51,790
perquè pugui veure com ho estic construint.

191
00:14:51,790 --> 00:14:59,040
El que el codi i el codi de distribució es farà seria unir-se a la T un

192
00:14:59,040 --> 00:15:01,410
amb el node 0 i 5.

193
00:15:01,410 --> 00:15:05,060
Així que les sumes a 3, i després continuem el procés.

194
00:15:05,060 --> 00:15:08,660
El 2 i el 2 ara són els més baixos, perquè després els suma a 4.

195
00:15:08,660 --> 00:15:12,560
Tothom seguint fins ara? Bé.

196
00:15:12,560 --> 00:15:16,410
Després, després que tenim el 3 i el 3 que han de ser sumats,

197
00:15:16,410 --> 00:15:21,650
així que de nou només ho estic canviant de manera que vostè pot veure visualment perquè no sigui massa complicat.

198
00:15:21,650 --> 00:15:25,740
Llavors tenim un 6, i després el nostre pas final és ara que només tenim dos nodes

199
00:15:25,740 --> 00:15:30,440
sumem aquells als que l'arrel del nostre arbre, que és 10.

200
00:15:30,440 --> 00:15:34,100
I el número 10 té sentit perquè cada node representat,

201
00:15:34,100 --> 00:15:40,750
seu valor, el seu número de freqüència, era quantes vegades va aparèixer a la cadena,

202
00:15:40,750 --> 00:15:46,350
i després tenim 5 caràcters en la nostra cadena, pel que té sentit.

203
00:15:48,060 --> 00:15:52,320
Si mirem a la forma en que realment ho codificar,

204
00:15:52,320 --> 00:15:56,580
com s'esperava, la i i la s, que apareixen amb més freqüència

205
00:15:56,580 --> 00:16:01,350
estan representats pel menor nombre de bits.

206
00:16:03,660 --> 00:16:05,660
>> Aneu amb compte aquí.

207
00:16:05,660 --> 00:16:09,780
En el cas d'arbres Huffman realment importa.

208
00:16:09,780 --> 00:16:13,670
Una S majúscula és diferent a una s minúscula.

209
00:16:13,670 --> 00:16:21,260
Si tinguéssim "Aquest és CS50" amb lletres majúscules, la s minúscula només apareixen dues vegades,

210
00:16:21,260 --> 00:16:27,120
Seria un node amb dos com el seu valor, i després S majúscula només seria un cop.

211
00:16:27,120 --> 00:16:33,440
Així que l'arbre podria canviar les estructures, ja que en realitat tenen un full addicional aquí.

212
00:16:33,440 --> 00:16:36,900
Però la suma encara seria 10.

213
00:16:36,900 --> 00:16:39,570
Això és el que realment estarà trucant a la suma de comprovació,

214
00:16:39,570 --> 00:16:44,060
l'addició de tots els recomptes.

215
00:16:46,010 --> 00:16:50,990
>> Ara que hem cobert els arbres Huffman, podem submergir-nos en Huff'n Puff, el conjunt de processadors.

216
00:16:50,990 --> 00:16:52,900
Anem a començar amb una secció de preguntes,

217
00:16:52,900 --> 00:16:57,990
i això es posarà vostè acostumat amb els arbres binaris i la forma d'operar al voltant del següent:

218
00:16:57,990 --> 00:17:03,230
nodes de dibuix, la creació de la seva pròpia estructura typedef per un node,

219
00:17:03,230 --> 00:17:07,230
i veure com es pot inserir en un arbre binari, que està classificat,

220
00:17:07,230 --> 00:17:09,050
travessant, i coses per l'estil.

221
00:17:09,050 --> 00:17:14,560
Aquest coneixement és, sens dubte ajudarà quan et submergeixis a la part Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
del conjunt de processadors.

223
00:17:19,150 --> 00:17:26,329
En l'edició estàndard del conjunt de processadors, la seva tasca és implementar Puff,

224
00:17:26,329 --> 00:17:30,240
i en la versió pirata de la seva tasca és implementar Huff.

225
00:17:30,240 --> 00:17:38,490
Què Huff fa és que pren el text i després es tradueix en el 0 i 1,

226
00:17:38,490 --> 00:17:41,990
de manera que el procés que hem fet anteriorment, on comptem amb les freqüències

227
00:17:41,990 --> 00:17:50,970
i després va fer l'arbre i després va dir: "Com puc obtenir T?"

228
00:17:50,970 --> 00:17:54,840
T està representat per 100, coses així,

229
00:17:54,840 --> 00:17:58,860
Huff i després prendria el text i després la sortida que binària.

230
00:17:58,860 --> 00:18:04,920
Però també perquè sabem que volem permetre que el nostre destinatari del missatge

231
00:18:04,920 --> 00:18:11,790
per tornar a crear el mateix arbre exacta, sinó que també inclou informació sobre els comptes de la freqüència.

232
00:18:11,790 --> 00:18:17,980
Després, amb Puff se'ns dóna un arxiu binari de 0 i 1

233
00:18:17,980 --> 00:18:21,740
i donada també la informació sobre les freqüències.

234
00:18:21,740 --> 00:18:26,740
Traduïm tots els de tornada 0s i 1s en el missatge original que va ser,

235
00:18:26,740 --> 00:18:29,350
pel que estem descomprimint això.

236
00:18:29,350 --> 00:18:36,450
Si vostè està fent l'edició estàndard, no cal implementar Huff,

237
00:18:36,450 --> 00:18:39,290
així llavors vostè pot utilitzar l'aplicació personal de Huff.

238
00:18:39,290 --> 00:18:42,080
Hi ha instruccions en l'especificació de com fer això.

239
00:18:42,080 --> 00:18:48,780
Podeu executar l'aplicació personal de Huff en un arxiu de text determinat

240
00:18:48,780 --> 00:18:53,270
i aleshores utilitzar aquesta sortida com l'entrada a Puff.

241
00:18:53,270 --> 00:18:59,330
>> Com ja he dit abans, tenim una gran quantitat de codi de distribució d'aquesta.

242
00:18:59,330 --> 00:19:01,810
Vaig a començar a anar a través d'ell.

243
00:19:01,810 --> 00:19:04,400
Vaig a passar la major part del temps al. Arxius h

244
00:19:04,400 --> 00:19:07,660
perquè en l'expedient. c, perquè tenim la h.

245
00:19:07,660 --> 00:19:11,650
i que ens proporciona els prototips de les funcions,

246
00:19:11,650 --> 00:19:15,520
no acabem d'entendre exactament que -

247
00:19:15,520 --> 00:19:20,280
Si no entén el que està passant en l'expedient. C, llavors no et preocupis massa,

248
00:19:20,280 --> 00:19:23,600
però sens dubte prova a fer una ullada, ja que podria donar algunes pistes

249
00:19:23,600 --> 00:19:29,220
i és útil per acostumar-se a la lectura de codi d'altres persones.

250
00:19:38,940 --> 00:19:48,270
>> Quant a huffile.h, en els comentaris es declara una capa d'abstracció envers codi de Huffman arxius.

251
00:19:48,270 --> 00:20:01,660
Si anem cap avall, veiem que hi ha un màxim de 256 símbols que pot ser que necessiti per codis.

252
00:20:01,660 --> 00:20:05,480
Això inclou totes les lletres de l'alfabet en majúscules i minúscules -

253
00:20:05,480 --> 00:20:08,250
i després els símbols i números, etc

254
00:20:08,250 --> 00:20:11,930
Llavors aquí tenim un nombre màgic que identifica un arxiu amb codificació Huffman.

255
00:20:11,930 --> 00:20:15,890
Dins d'un codi Huffman que tindran un nombre de certa màgia

256
00:20:15,890 --> 00:20:18,560
associat amb la capçalera.

257
00:20:18,560 --> 00:20:21,110
Això podria semblar només un nombre màgic a l'atzar,

258
00:20:21,110 --> 00:20:27,160
però si en realitat es tradueixen en ASCII, llavors el que realment explica Huff.

259
00:20:27,160 --> 00:20:34,290
Aquí tenim una estructura d'un arxiu amb codificació Huffman.

260
00:20:34,290 --> 00:20:39,670
No totes aquestes característiques associades amb un arxiu de Huff.

261
00:20:39,670 --> 00:20:47,080
Llavors aquí tenim la capçalera d'un arxiu de Huff, per això en diem Huffeader

262
00:20:47,080 --> 00:20:50,810
en lloc d'afegir la h extra perquè sona igual de totes maneres.

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

264
00:20:52,720 --> 00:20:57,790
Tenim un nombre màgic associat amb ell.

265
00:20:57,790 --> 00:21:09,040
Si es tracta d'un veritable arxiu de Huff, que serà el nombre de dalt, aquest màgic.

266
00:21:09,040 --> 00:21:14,720
I llavors tindrà una matriu.

267
00:21:14,720 --> 00:21:18,750
Així, per a cada símbol, dels quals hi ha 256,

268
00:21:18,750 --> 00:21:24,760
que va a enumerar el que la freqüència d'aquests símbols es troben a l'arxiu de Huff.

269
00:21:24,760 --> 00:21:28,090
I, finalment, tenim una suma de comprovació de les freqüències,

270
00:21:28,090 --> 00:21:32,160
que ha de ser la suma d'aquestes freqüències.

271
00:21:32,160 --> 00:21:36,520
Així que això és el que un Huffeader és.

272
00:21:36,520 --> 00:21:44,600
Llavors tenim algunes funcions que retornen el següent bit a l'arxiu de Huff

273
00:21:44,600 --> 00:21:52,580
així com escriu un bit en el fitxer de Huff, i llavors aquesta funció aquí, hfclose,

274
00:21:52,580 --> 00:21:54,650
que en realitat tanca l'arxiu Huff.

275
00:21:54,650 --> 00:21:57,290
Abans, es tractava de recta just fclose,

276
00:21:57,290 --> 00:22:01,190
però quan es té un arxiu de Huff, en lloc del fclosing

277
00:22:01,190 --> 00:22:06,080
el que realment farà és hfclose i hfopen ella.

278
00:22:06,080 --> 00:22:13,220
Són funcions específiques als arxius Huff que estarem tractant.

279
00:22:13,220 --> 00:22:19,230
Llavors aquí es llegeix a la capçalera i després escriure la capçalera.

280
00:22:19,230 --> 00:22:25,700
>> Amb només llegir l'arxiu. H puguem tipus de tenir una idea de què és un arxiu Huff podria ser,

281
00:22:25,700 --> 00:22:32,480
¿Quines característiques té, sense haver d'anar a la huffile.c,

282
00:22:32,480 --> 00:22:36,750
que, si ens submergim en, serà una mica més complex.

283
00:22:36,750 --> 00:22:41,270
Té tot l'arxiu I / O aquí tractant amb punters.

284
00:22:41,270 --> 00:22:48,010
Aquí veiem que quan anomenem hfread, per exemple, encara es tracta d'fread.

285
00:22:48,010 --> 00:22:53,050
No anem a desfer-nos d'aquestes funcions del tot, però estem enviant als quals es van ocupar de

286
00:22:53,050 --> 00:22:59,760
dins de l'arxiu de Huff en lloc de fer tot nosaltres mateixos.

287
00:22:59,760 --> 00:23:02,300
Vostè pot sentir-se lliure per explorar a través d'això si vostè és curiós

288
00:23:02,300 --> 00:23:08,410
i anar a pelar la capa de nou una mica.

289
00:23:20,650 --> 00:23:24,060
>> El següent arxiu que anem a mirar és tree.h.

290
00:23:24,060 --> 00:23:30,210
Abans del Tutorial llisca vam dir d'esperar un node Huffman

291
00:23:30,210 --> 00:23:32,960
i vam fer un node typedef struct.

292
00:23:32,960 --> 00:23:38,360
Esperem que tingui un símbol, una freqüència, i després 2 estrelles node.

293
00:23:38,360 --> 00:23:41,870
En aquest cas el que estem fent és que aquest és essencialment el mateix

294
00:23:41,870 --> 00:23:46,880
però en lloc de node anem a cridar arbres.

295
00:23:48,790 --> 00:23:56,760
Tenim una funció que quan es crida a fer arbre que li retorna un punter arbre.

296
00:23:56,760 --> 00:24:03,450
Retorn a Speller, quan estaven fent un nou node

297
00:24:03,450 --> 00:24:11,410
vostè ha dit node paraula * nou = malloc (sizeof) i coses per l'estil.

298
00:24:11,410 --> 00:24:17,510
Bàsicament, mktree es tractarà amb això per tu.

299
00:24:17,510 --> 00:24:20,990
De la mateixa manera, quan es vol treure un arbre,

300
00:24:20,990 --> 00:24:24,810
pel que és essencialment alliberant a l'arbre quan hagi acabat amb ell,

301
00:24:24,810 --> 00:24:33,790
en comptes de cridar explícitament lliure en què, en realitat estàs només va a utilitzar la funció de rmtree

302
00:24:33,790 --> 00:24:40,360
on es passa el punter a aquest arbre i després tree.c es farà càrrec d'això per tu.

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

304
00:24:42,490 --> 00:24:47,240
Esperem que les mateixes funcions, excepte per veure la implementació.

305
00:24:47,240 --> 00:24:57,720
No és sorprenent, quan es diu mktree el mallocs la mida d'un arbre en un punter,

306
00:24:57,720 --> 00:25:03,190
inicialitza tots els valors per al valor NULL, de manera que 0 º o nuls,

307
00:25:03,190 --> 00:25:08,280
i torna el punter a aquest arbre que acaba de malloc'd a vostè.

308
00:25:08,280 --> 00:25:13,340
Aquí quan es diu a eliminar arbre per primera vegada s'assegura que vostè no està alliberant doble.

309
00:25:13,340 --> 00:25:18,320
S'assegura que vostè realment té un arbre que voleu eliminar.

310
00:25:18,320 --> 00:25:23,330
Heus aquí perquè un arbre també inclou els seus fills,

311
00:25:23,330 --> 00:25:29,560
el que això fa és que crida de forma recursiva eliminar arbre al node esquerre de l'arbre

312
00:25:29,560 --> 00:25:31,650
així com el node dret.

313
00:25:31,650 --> 00:25:37,790
Abans que s'allibera als pares, ha de alliberar els nens també.

314
00:25:37,790 --> 00:25:42,770
Pares també és intercanviable amb l'arrel.

315
00:25:42,770 --> 00:25:46,500
El pare per primera vegada, així que com el tatara-tatara-tatara-tatara-avi

316
00:25:46,500 --> 00:25:52,130
o arbre àvia, primer hem de alliberar pels primers nivells.

317
00:25:52,130 --> 00:25:58,490
Així que recórrer fins al fons, sense ells, i després tornar a pujar, sense ells, etc

318
00:26:00,400 --> 00:26:02,210
Així que això és arbre.

319
00:26:02,210 --> 00:26:04,240
>> Ara ens centrarem en els boscos.

320
00:26:04,240 --> 00:26:09,860
Bosc és on es col · loquen tots els arbres de Huffman.

321
00:26:09,860 --> 00:26:12,910
És com dir que haurem cosa que es diu una parcel · la

322
00:26:12,910 --> 00:26:22,320
que conté un punter a un arbre, així com un punter a una trama anomenada següent.

323
00:26:22,320 --> 00:26:28,480
Quina estructura té aquest tipus de sembla?

324
00:26:29,870 --> 00:26:32,490
En certa manera es diu per aquí.

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

326
00:26:37,340 --> 00:26:39,170
Una llista enllaçada.

327
00:26:39,170 --> 00:26:44,590
Veiem que quan tenim un argument que és com una llista enllaçada de parcel · les.

328
00:26:44,590 --> 00:26:53,020
Un bosc es defineix com una llista enllaçada de parcel · les,

329
00:26:53,020 --> 00:26:58,100
de manera que l'estructura del bosc és només tindrem un punter a la nostra primera parcel · la

330
00:26:58,100 --> 00:27:02,740
i que la parcel · la té un arbre dins d'ella o, més aviat apunta a un arbre

331
00:27:02,740 --> 00:27:06,190
i després apunta a la trama següent, així successivament i així successivament.

332
00:27:06,190 --> 00:27:11,100
Perquè un bosc que anomenem mkforest.

333
00:27:11,100 --> 00:27:14,930
A continuació tenim algunes funcions molt útils aquí.

334
00:27:14,930 --> 00:27:23,240
Hem de triar on es passa en un bosc i després el valor de retorn és un * Arbre,

335
00:27:23,240 --> 00:27:25,210
un punter a un arbre.

336
00:27:25,210 --> 00:27:29,370
Què selecció farà és que vaig a entrar al bosc que està apuntant a

337
00:27:29,370 --> 00:27:35,240
després retiri un arbre amb la freqüència més baixa d'aquest bosc

338
00:27:35,240 --> 00:27:38,330
i després donar-li el punter a aquest arbre.

339
00:27:38,330 --> 00:27:43,030
Quan vostè truqui a recollir, l'arbre no existirà mai més al bosc,

340
00:27:43,030 --> 00:27:48,550
però el valor de retorn és el punter a aquest arbre.

341
00:27:48,550 --> 00:27:50,730
Llavors vostè té la planta.

342
00:27:50,730 --> 00:27:57,420
Sempre que es passa un punter a un arbre que té una freqüència de no-0,

343
00:27:57,420 --> 00:28:04,040
quina planta farà és que prendrà el bosc, prengui l'arbre, i que dins de la planta de l'arbre de la selva.

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

345
00:28:06,370 --> 00:28:11,480
Similar a eliminar arbre, que bàsicament va alliberar a tots els nostres arbres per a nosaltres,

346
00:28:11,480 --> 00:28:16,600
treure bosc que per a tota realitat lliure contingut en aquest bosc.

347
00:28:16,600 --> 00:28:24,890
>> Si ens fixem en forest.c, esperarem a veure almenys una ordre rmtree allà,

348
00:28:24,890 --> 00:28:30,090
perquè per alliberar memòria al bosc si un bosc té arbres-hi,

349
00:28:30,090 --> 00:28:32,930
després, eventualment hauràs treure aquests arbres també.

350
00:28:32,930 --> 00:28:41,020
Si ens fixem en forest.c, tenim la nostra mkforest, que és el que esperem.

351
00:28:41,020 --> 00:28:42,890
Tenim coses malloc.

352
00:28:42,890 --> 00:28:51,740
Ens inicialitzar la primera parcel · la al bosc com NULL perquè està buit, per començar,

353
00:28:51,740 --> 00:29:05,940
llavors veiem selecció, que retorna l'arbre amb el pes més baix, la freqüència més baixa,

354
00:29:05,940 --> 00:29:13,560
i després es desfà d'aquest node particular que apunta a aquest arbre i el que ve,

355
00:29:13,560 --> 00:29:16,760
per la qual cosa pren que de la llista enllaçada de la selva.

356
00:29:16,760 --> 00:29:24,510
I llavors aquí tenim planta, que insereix un arbre a la llista enllaçada.

357
00:29:24,510 --> 00:29:29,960
El que fa és que els boscos bé manté ordenats per a nosaltres.

358
00:29:29,960 --> 00:29:37,910
I, finalment, tenim rmforest i, com era d'esperar, tenim rmtree anomenat allà.

359
00:29:46,650 --> 00:29:55,440
>> Quant a la distribució de codi fins ara, huffile.c va ser probablement amb molt més difícil d'entendre,

360
00:29:55,440 --> 00:29:59,990
mentre que els altres arxius en si eren força fàcils de seguir.

361
00:29:59,990 --> 00:30:03,090
Amb el nostre coneixement dels punters i llistes enllaçades i tal,

362
00:30:03,090 --> 00:30:04,860
hem estat capaços de seguir bastant bé.

363
00:30:04,860 --> 00:30:10,500
Però tot el que necessitem fer realment segur que estem totalment d'entendre són els arxius. H

364
00:30:10,500 --> 00:30:15,840
perquè cal estar trucant a aquestes funcions, que tracta dels valors de retorn,

365
00:30:15,840 --> 00:30:20,590
així que assegureu-vos que comprèn perfectament l'acció que es realitzarà

366
00:30:20,590 --> 00:30:24,290
cada vegada que es cridi a una d'aquestes funcions.

367
00:30:24,290 --> 00:30:33,020
Però en realitat la comprensió dins de la mateixa no és molt necessari perquè tenim aquests. Arxius h.

368
00:30:35,170 --> 00:30:39,490
Tenim 2 més arxius que queden en el nostre codi de distribució.

369
00:30:39,490 --> 00:30:41,640
>> Fem una ullada a abocador.

370
00:30:41,640 --> 00:30:47,230
Bolcat pel seu comentari aquí pren un arxiu comprimit Huffman-

371
00:30:47,230 --> 00:30:55,580
i després tradueix i abocadors de tot el seu contingut fora.

372
00:31:01,010 --> 00:31:04,260
Aquí veiem que s'està cridant hfopen.

373
00:31:04,260 --> 00:31:10,770
Aquesta és una espècie de mirall per presentar d'entrada * = fopen,

374
00:31:10,770 --> 00:31:13,500
i després se li passa la informació.

375
00:31:13,500 --> 00:31:18,240
És gairebé idèntic excepte que en lloc d'un arxiu * que estiguis passant un Huffile;

376
00:31:18,240 --> 00:31:22,030
en lloc de fopen que està passant a hfopen.

377
00:31:22,030 --> 00:31:29,280
Aquí llegim a la primera capçalera, que és una espècie de manera similar a com es llegeix a la capçalera

378
00:31:29,280 --> 00:31:33,580
per a un arxiu de mapa de bits.

379
00:31:33,580 --> 00:31:38,000
El que estem fent aquí és la comprovació per veure si la informació de l'encapçalament

380
00:31:38,000 --> 00:31:44,330
conté el nombre màgic correcte que indica que és un arxiu real Huff,

381
00:31:44,330 --> 00:31:53,610
llavors totes aquestes comprovacions per assegurar-se que l'arxiu obert que és un arxiu real huffed o no.

382
00:31:53,610 --> 00:32:05,330
El que això fa és que emet les freqüències de tots els símbols que podem veure

383
00:32:05,330 --> 00:32:09,790
dins d'un terminal en una taula gràfica.

384
00:32:09,790 --> 00:32:15,240
Aquesta part serà útil.

385
00:32:15,240 --> 00:32:24,680
Té una mica i llegeix poc a poc en la variable de bits i després imprimeix.

386
00:32:28,220 --> 00:32:35,430
Així que si jo fos a cridar bolcat en hth.bin, que és el resultat d'inhalar un arxiu

387
00:32:35,430 --> 00:32:39,490
utilitzant la solució personal, m'agradaria tenir això.

388
00:32:39,490 --> 00:32:46,000
És la sortida de tots aquests personatges i després posar la freqüència amb què apareixen.

389
00:32:46,000 --> 00:32:51,180
Si ens fixem, la majoria d'ells són 0s excepte per això: H, que apareix dues vegades,

390
00:32:51,180 --> 00:32:54,820
i llavors T, que apareix una vegada.

391
00:32:54,820 --> 00:33:07,860
I aquí tenim el missatge real en 0s i 1s.

392
00:33:07,860 --> 00:33:15,450
Si ens fixem en hth.txt, que presumiblement és el missatge original que es bufo,

393
00:33:15,450 --> 00:33:22,490
esperem veure alguns Hs i Ts en aquest país.

394
00:33:22,490 --> 00:33:28,720
En concret, s'espera veure a 1 T i HS 2.

395
00:33:32,510 --> 00:33:37,440
Aquí estem en hth.txt. En efecte, té HTH.

396
00:33:37,440 --> 00:33:41,270
Inclòs en allà, encara que no ho podem veure, és un caràcter de nova línia.

397
00:33:41,270 --> 00:33:53,190
El hth.bin arxiu Huff també es codifica el caràcter de nova línia també.

398
00:33:55,680 --> 00:34:01,330
Heus aquí perquè sabem que l'ordre és HTH i després salt de línia,

399
00:34:01,330 --> 00:34:07,340
podem veure que probablement l'H està representada per només un únic 1

400
00:34:07,340 --> 00:34:17,120
i després la T és probablement 01 i després el següent és H 1, així

401
00:34:17,120 --> 00:34:21,139
i llavors tenim una nova línia indicada per dos 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> I finalment, perquè estem tractant múltiple. Cy. Arxius h,

404
00:34:31,600 --> 00:34:36,350
tindrem un argument prou complex per al compilador,

405
00:34:36,350 --> 00:34:40,460
i aquí tenim un Makefile que fa bolcat per a vostè.

406
00:34:40,460 --> 00:34:47,070
Però en realitat, hi ha d'anar sobre la fabricació del seu propi arxiu puff.c.

407
00:34:47,070 --> 00:34:54,330
El Makefile en realitat no tracta de fer puff.c per a vostè.

408
00:34:54,330 --> 00:34:59,310
Estem deixant que depèn de vostè per editar el Makefile.

409
00:34:59,310 --> 00:35:05,930
Quan s'introdueix una ordre com fan tots, per exemple, farà tot per vostè.

410
00:35:05,930 --> 00:35:10,760
Siéntase lliure de mirar els exemples de Makefile del conjunt de processadors passat

411
00:35:10,760 --> 00:35:17,400
així com sortir d'aquest per veure com podria ser capaç de fer que l'arxiu Puff

412
00:35:17,400 --> 00:35:20,260
mitjançant l'edició d'aquest Makefile.

413
00:35:20,260 --> 00:35:22,730
Això és tot pel nostre codi de distribució.

414
00:35:22,730 --> 00:35:28,380
>> Quan hagi passat per això, llavors aquí és només un altre recordatori

415
00:35:28,380 --> 00:35:30,980
de la manera com tindrem tracte amb els nodes de Huffman.

416
00:35:30,980 --> 00:35:35,400
No estarem trucant als nodes més, nosaltres estarem trucant arbres

417
00:35:35,400 --> 00:35:39,260
on anem a representar el seu símbol amb un char,

418
00:35:39,260 --> 00:35:43,340
seva freqüència, el nombre d'ocurrències, amb un nombre enter.

419
00:35:43,340 --> 00:35:47,370
Estem usant això perquè és més precís que un flotador.

420
00:35:47,370 --> 00:35:52,980
I després tenim un altre punter al fill esquerre i el fill dret.

421
00:35:52,980 --> 00:35:59,630
Un bosc, com hem vist, és només una llista enllaçada d'arbres.

422
00:35:59,630 --> 00:36:04,670
En última instància, quan estem construint el nostre arxiu Huff,

423
00:36:04,670 --> 00:36:07,580
volem que el nostre bosc per contenir només 1 arbre -

424
00:36:07,580 --> 00:36:12,420
Un arbre, una arrel amb diversos nens.

425
00:36:12,420 --> 00:36:20,840
Anteriorment quan estàvem fent els nostres arbres Huffman,

426
00:36:20,840 --> 00:36:25,360
comencem posant tots els nodes en la nostra pantalla

427
00:36:25,360 --> 00:36:27,790
i dir que tindrem aquests nodes,

428
00:36:27,790 --> 00:36:32,920
eventualment seran les fulles, i aquesta és el seu símbol, es tracta de la seva freqüència.

429
00:36:32,920 --> 00:36:42,070
En el nostre bosc si només tenim tres cartes, que és un bosc de 3 arbres.

430
00:36:42,070 --> 00:36:45,150
I després, a mesura que avancem, quan es va agregar el primer pare,

431
00:36:45,150 --> 00:36:48,080
vam fer un bosc de 2 arbres.

432
00:36:48,080 --> 00:36:54,930
Hem eliminat dos dels fills del nostre bosc i després ho va reemplaçar amb un node pare

433
00:36:54,930 --> 00:36:58,820
que tenia aquests dos nodes com els nens.

434
00:36:58,820 --> 00:37:05,600
I, finalment, el nostre últim pas amb la fabricació del nostre exemple amb l'As, Bs i Cs

435
00:37:05,600 --> 00:37:08,030
seria fer la matriu final,

436
00:37:08,030 --> 00:37:13,190
i és així, que portaria al nostre compte total dels arbres al bosc a 1.

437
00:37:13,190 --> 00:37:18,140
Tothom veu com s'inicia amb diversos arbres al bosc

438
00:37:18,140 --> 00:37:22,520
i acabar amb 1? Bé. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Què és el que hem de fer per Puff?

440
00:37:28,110 --> 00:37:37,110
El que hem de fer és assegurar-se que, com sempre, ens donen el tipus d'entrada

441
00:37:37,110 --> 00:37:39,090
perquè pugui executar el programa.

442
00:37:39,090 --> 00:37:43,130
En aquest cas, estarem donant-nos després del seu primer argument de la línia d'ordres

443
00:37:43,130 --> 00:37:53,440
2 més: l'arxiu que desitja descomprimir i la sortida de l'arxiu descomprimit.

444
00:37:53,440 --> 00:38:00,410
Però quan ens assegurem que ens passi en la quantitat correcta dels valors,

445
00:38:00,410 --> 00:38:05,820
volem assegurar que l'entrada és un fitxer Huff o no.

446
00:38:05,820 --> 00:38:10,420
I un cop et garantim que és un arxiu de Huff, llavors volem construir el nostre arbre,

447
00:38:10,420 --> 00:38:20,940
construir l'arbre de manera que coincideixi amb l'arbre que la persona que va enviar el missatge construït.

448
00:38:20,940 --> 00:38:25,840
A continuació, després de construir l'arbre, llavors podem tractar amb ell, 0s i 1s que van passar a

449
00:38:25,840 --> 00:38:29,590
segueixen al llarg del nostre arbre perquè és idèntic,

450
00:38:29,590 --> 00:38:33,510
i després escriure aquest missatge, interpretar els bits de nou en chars.

451
00:38:33,510 --> 00:38:35,880
I després, al final, ja que es tracta de punters aquí,

452
00:38:35,880 --> 00:38:38,110
volem assegurar-nos que no tenim pèrdues de memòria

453
00:38:38,110 --> 00:38:41,330
i que tot sigui gratis.

454
00:38:42,820 --> 00:38:46,430
>> Vetllar per l'ús adequat és força vell per a nosaltres per ara.

455
00:38:46,430 --> 00:38:51,980
Prenem en una entrada, que serà el nom del fitxer que s'inflen,

456
00:38:51,980 --> 00:38:56,010
i llavors especificar una sortida,

457
00:38:56,010 --> 00:39:01,580
de manera que el nom de l'arxiu per a la sortida d'inflat, que serà l'arxiu de text.

458
00:39:03,680 --> 00:39:08,820
Aquesta és el seu ús. I ara volem assegurar-nos que l'entrada està esbufegar com si no.

459
00:39:08,820 --> 00:39:16,420
Pensant-ho bé, hi havia alguna cosa en el codi de distribució que ens poden ajudar a

460
00:39:16,420 --> 00:39:21,570
amb la comprensió de si un arxiu està esbufegar o no?

461
00:39:21,570 --> 00:39:26,910
No hi havia informació en huffile.c sobre la Huffeader.

462
00:39:26,910 --> 00:39:33,430
Sabem que tots els arxius Huff té un Huffeader associat amb un nombre màgic

463
00:39:33,430 --> 00:39:37,240
així com una matriu de les freqüències per a cada símbol

464
00:39:37,240 --> 00:39:39,570
així com una suma de comprovació.

465
00:39:39,570 --> 00:39:43,180
Ho sabem, però que també ens va portar una ullada a dump.c,

466
00:39:43,180 --> 00:39:49,120
en el qual es llegeix en un arxiu de Huff.

467
00:39:49,120 --> 00:39:53,990
I per fer això, havia de comprovar si realment es va bufar com si no.

468
00:39:53,990 --> 00:40:03,380
Així que potser podríem utilitzar dump.c com una estructura per al nostre puff.c.

469
00:40:03,380 --> 00:40:12,680
Tornar al conjunt de processadors 4 quan vam tenir la copy.c arxiu que va copiar en triples RGB

470
00:40:12,680 --> 00:40:14,860
i es va interpretar que per Whodunit i canvi de mida,

471
00:40:14,860 --> 00:40:20,390
de la mateixa manera, el que es pot fer és executar la comanda com cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
i l'ús d'una part del codi allà.

473
00:40:23,600 --> 00:40:28,210
No obstant això, no serà tan senzill d'un procés

474
00:40:28,210 --> 00:40:33,010
per a la traducció de la seva dump.c en puff.c,

475
00:40:33,010 --> 00:40:36,160
però almenys li dóna un lloc per començar

476
00:40:36,160 --> 00:40:40,540
en la forma de garantir que l'entrada està realment o no esbufegar

477
00:40:40,540 --> 00:40:43,240
així com algunes altres coses.

478
00:40:45,930 --> 00:40:50,250
Ens hem assegurat l'ús adequat i assegurar-se que l'entrada està esbufegar.

479
00:40:50,250 --> 00:40:53,570
Cada vegada que hem fet el que hem fet el nostre revisió d'errors adequat,

480
00:40:53,570 --> 00:41:01,520
el de tornar i deixar la funció si es produeix alguna fallada, si hi ha un problema.

481
00:41:01,520 --> 00:41:07,170
>> Ara el que vull fer és construir l'arbre real.

482
00:41:08,840 --> 00:41:12,640
Si ens fixem en el bosc, hi ha 2 funcions principals

483
00:41:12,640 --> 00:41:15,800
que anem a voler conèixer molt bé.

484
00:41:15,800 --> 00:41:23,870
Aquí hi ha la planta funció booleana que planta un arbre freqüència no-0 a l'interior del nostre bosc.

485
00:41:23,870 --> 00:41:29,250
I així es passa un punter a un bosc i un punter a un arbre.

486
00:41:32,530 --> 00:41:40,340
Una pregunta ràpida: Com molts boscos es té quan vostè està construint un arbre de Huffman?

487
00:41:44,210 --> 00:41:46,650
El nostre bosc és com el nostre llenç, no?

488
00:41:46,650 --> 00:41:50,800
Així que només tindrem un bosc, però tindrem diversos arbres.

489
00:41:50,800 --> 00:41:57,590
Així que abans de trucar a la planta, que està probablement va a voler fer el seu bosc.

490
00:41:57,590 --> 00:42:04,430
Hi ha una ordre perquè si ens fixem en forest.h sobre com vostè pot fer un bosc.

491
00:42:04,430 --> 00:42:09,270
Vostè pot plantar un arbre. Sabem com fer-ho.

492
00:42:09,270 --> 00:42:11,590
I llavors vostè pot també escollir un arbre del bosc,

493
00:42:11,590 --> 00:42:17,540
l'eliminació d'un arbre amb el pes més baix i que li dóna el punter a això.

494
00:42:17,540 --> 00:42:23,090
Pensant de nou a quan estàvem fent els exemples de nosaltres mateixos,

495
00:42:23,090 --> 00:42:27,980
quan l'estàvem traient, simplement acaba d'afegir els enllaços.

496
00:42:27,980 --> 00:42:31,680
Però aquí, en lloc de limitar-se a afegir els enllaços,

497
00:42:31,680 --> 00:42:40,630
Crec que és més com estàs traient 2 dels nodes i després reemplaçar-lo per un altre.

498
00:42:40,630 --> 00:42:44,200
Per expressar que en termes de collita i sembra,

499
00:42:44,200 --> 00:42:48,840
vostè està recollint dos arbres i després plantar un altre arbre

500
00:42:48,840 --> 00:42:54,060
que té aquests dos arbres que vostè va escollir com nens.

501
00:42:57,950 --> 00:43:05,280
Per construir arbre de Huffman, es pot llegir en els símbols i les freqüències per tal de

502
00:43:05,280 --> 00:43:10,790
perquè el Huffeader dóna a tu,

503
00:43:10,790 --> 00:43:14,250
t'ofereix una àmplia gamma de les freqüències.

504
00:43:14,250 --> 00:43:19,660
Així que vostè pot seguir endavant i simplement fer cas omís de qualsevol cosa amb el 0 en el mateix

505
00:43:19,660 --> 00:43:23,760
perquè no volem 256 fulls al final de la mateixa.

506
00:43:23,760 --> 00:43:27,960
Només volem que el nombre de fulls que són personatges

507
00:43:27,960 --> 00:43:31,600
que s'utilitza realment en l'arxiu.

508
00:43:31,600 --> 00:43:37,590
Vostè pot llegir en aquests símbols, i cada un d'aquests símbols que tenen freqüències no-0,

509
00:43:37,590 --> 00:43:40,440
els que seran arbres.

510
00:43:40,440 --> 00:43:45,990
El que pot fer és que cada vegada que es llegeix en un símbol de freqüència no-0,

511
00:43:45,990 --> 00:43:50,660
vostè pot plantar aquest arbre al bosc.

512
00:43:50,660 --> 00:43:56,620
Quan plantar els arbres al bosc, vostè pot unir-se als arbres com germans,

513
00:43:56,620 --> 00:44:01,130
així d'anar de nou a la sembra i la collita en el qual recollir 2 i després la planta 1,

514
00:44:01,130 --> 00:44:05,820
on aquesta planta 1 que vostè és el pare dels dos nens que vostè va escollir.

515
00:44:05,820 --> 00:44:11,160
Així que el resultat final serà un sol arbre al bosc.

516
00:44:16,180 --> 00:44:18,170
Aquesta és la forma de construir el seu arbre.

517
00:44:18,170 --> 00:44:21,850
>> Hi ha diverses coses que podrien sortir malament aquí

518
00:44:21,850 --> 00:44:26,580
perquè estem tractant amb la fabricació de nous arbres i fer front als punters i coses per l'estil.

519
00:44:26,580 --> 00:44:30,450
Abans, quan estàvem tractant amb punters,

520
00:44:30,450 --> 00:44:36,580
sempre que malloc'd volíem assegurar-nos que no ens retornen un valor de punter NULL.

521
00:44:36,580 --> 00:44:42,770
Així que en diversos passos dins d'aquest procés no seran diversos casos

522
00:44:42,770 --> 00:44:45,920
on el programa podria fallar.

523
00:44:45,920 --> 00:44:51,310
El que vull fer és que vostè vol assegurar-se que vostè maneja aquests errors,

524
00:44:51,310 --> 00:44:54,580
i en l'especificació que diu manejar amb gràcia,

525
00:44:54,580 --> 00:45:00,280
així com imprimir un missatge a l'usuari dient per què el programa ha de deixar de fumar

526
00:45:00,280 --> 00:45:03,050
i després ràpidament sortir-ne.

527
00:45:03,050 --> 00:45:09,490
Per això, el control d'errors, recordi que vostè desitgi comprovar

528
00:45:09,490 --> 00:45:12,160
cada vegada que hi ha podria ser un fracàs.

529
00:45:12,160 --> 00:45:14,660
Cada vegada que vostè està fent un nou punter

530
00:45:14,660 --> 00:45:17,040
vostè vol assegurar-se que això és un èxit.

531
00:45:17,040 --> 00:45:20,320
Abans del que solem fer és fer un nou punter i malloc ella,

532
00:45:20,320 --> 00:45:22,380
i llavors podríem comprovar si aquest punter és NULL.

533
00:45:22,380 --> 00:45:25,670
Així que aquí hi haurà alguns casos on només es pot fer això,

534
00:45:25,670 --> 00:45:28,610
però de vegades en realitat està cridant a una funció

535
00:45:28,610 --> 00:45:33,100
i dins d'aquesta funció, que és la que està fent el mallocing.

536
00:45:33,100 --> 00:45:39,110
En aquest cas, si mirem enrere a algunes de les funcions dins del codi,

537
00:45:39,110 --> 00:45:42,260
alguns d'ells són funcions booleanes.

538
00:45:42,260 --> 00:45:48,480
En el cas abstracte si tenim una funció booleana anomenada foo,

539
00:45:48,480 --> 00:45:54,580
Bàsicament, podem suposar que, a més de fer el que fa foo,

540
00:45:54,580 --> 00:45:57,210
ja que és una funció booleana, retorna vertader o fals -

541
00:45:57,210 --> 00:46:01,300
true si és correcte, false en cas contrari.

542
00:46:01,300 --> 00:46:06,270
Així que volem comprovar si el valor de retorn de foo és vertader o fals.

543
00:46:06,270 --> 00:46:10,400
Si és fals, això vol dir que anem a voler imprimir algun tipus de missatge

544
00:46:10,400 --> 00:46:14,390
i surti del programa.

545
00:46:14,390 --> 00:46:18,530
El que volem fer és comprovar el valor retornat de foo.

546
00:46:18,530 --> 00:46:23,310
Si foo retorna false, llavors sabem que ens trobem amb algun tipus d'error

547
00:46:23,310 --> 00:46:25,110
i hem de sortir del nostre programa.

548
00:46:25,110 --> 00:46:35,600
Una manera de fer això és tenir una condició on la funció en si és la seva condició.

549
00:46:35,600 --> 00:46:39,320
Digui foo pren en x.

550
00:46:39,320 --> 00:46:43,390
Podem tenir com a condició if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Bàsicament, això vol dir que si al final de l'execució de foo retorna veritable,

552
00:46:50,900 --> 00:46:57,390
llavors no podem fer això perquè la funció d'avaluar foo

553
00:46:57,390 --> 00:47:00,500
amb la finalitat d'avaluar la condició general.

554
00:47:00,500 --> 00:47:06,500
Així que així és com es pot fer alguna cosa si la funció retorna veritat i la aconsegueix.

555
00:47:06,500 --> 00:47:11,800
Però quan un és la comprovació d'errors, només vol deixar de fumar si la seva funció retorna false.

556
00:47:11,800 --> 00:47:16,090
El que podria fer és afegir un == false o simplement afegir una explosió al davant d'ella

557
00:47:16,090 --> 00:47:21,010
i després tens if (! foo).

558
00:47:21,010 --> 00:47:29,540
Dins d'aquest cos d'aquesta condició que tindria tot el control d'errors,

559
00:47:29,540 --> 00:47:36,940
així com, "No s'ha pogut crear aquest arbre" i després retornar 1 o alguna cosa per l'estil.

560
00:47:36,940 --> 00:47:43,340
El que fa, però, és que encara foo retornat false -

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

562
00:47:46,980 --> 00:47:51,060
Llavors vostè no ha de trucar a foo nou. Això és un error comú.

563
00:47:51,060 --> 00:47:54,730
A causa que va ser en la seva condició, ja està avaluat,

564
00:47:54,730 --> 00:47:59,430
de manera que ja tenen el resultat si vostè està utilitzant make arbre o alguna cosa així

565
00:47:59,430 --> 00:48:01,840
o de la planta o de la selecció o una cosa així.

566
00:48:01,840 --> 00:48:07,460
Ja té aquest valor. Ja està executat.

567
00:48:07,460 --> 00:48:10,730
Així que és útil l'ús de funcions booleanes com la condició

568
00:48:10,730 --> 00:48:13,890
perquè si està o no fa és executar el cos del bucle,

569
00:48:13,890 --> 00:48:18,030
s'executa la funció de totes maneres.

570
00:48:22,070 --> 00:48:27,330
>> El nostre segon a últim pas és escriure el missatge a l'arxiu.

571
00:48:27,330 --> 00:48:33,070
Un cop de construir l'arbre de Huffman, a continuació, escriure el missatge en l'arxiu és bastant senzill.

572
00:48:33,070 --> 00:48:39,260
És bastant senzill ara a seguir només el 0 i 1.

573
00:48:39,260 --> 00:48:45,480
I així, per convenció, se sap que en un arbre de Huffman dels 0 Indiqueu esquerre

574
00:48:45,480 --> 00:48:48,360
i el 1s indicar dreta.

575
00:48:48,360 --> 00:48:53,540
Així que si vostè llegeix en poc a poc, cada vegada que s'obté un 0

576
00:48:53,540 --> 00:48:59,100
podràs seguir la branca esquerra, i després cada vegada que es llegeix en un 1

577
00:48:59,100 --> 00:49:02,100
vostè seguirà la branca dreta.

578
00:49:02,100 --> 00:49:07,570
I llavors vostè va a continuar fins arribar a un full

579
00:49:07,570 --> 00:49:11,550
perquè les fulles estaran a l'extrem de les branques.

580
00:49:11,550 --> 00:49:16,870
Com podem saber si ens hem topat amb un full o no?

581
00:49:19,800 --> 00:49:21,690
Ho hem dit abans.

582
00:49:21,690 --> 00:49:24,040
[Estudiant] Si els punters són NULL. Sí >>.

583
00:49:24,040 --> 00:49:32,220
Podem saber si ens hem topat amb un full si els punters als arbres de l'esquerra i la dreta són NULL.

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

585
00:49:34,110 --> 00:49:40,320
Sabem que volem llegir a poc a poc en el nostre arxiu de Huff.

586
00:49:43,870 --> 00:49:51,220
Com hem vist abans en dump.c, el que van fer és que llegeixen en poc a poc a l'arxiu de Huff

587
00:49:51,220 --> 00:49:54,560
y només imprimeix el que els bits eren.

588
00:49:54,560 --> 00:49:58,430
No estarem fent això. Estarem fent una cosa que és una mica més complex.

589
00:49:58,430 --> 00:50:03,620
Però el que podem fer és que podem prendre aquest tros de codi que llegeix a la broca.

590
00:50:03,620 --> 00:50:10,250
Aquí tenim el bit enter que representa el bit actual que estem.

591
00:50:10,250 --> 00:50:15,520
Aquest s'encarrega de iteració a tots els bits en l'arxiu fins que arribi al final de l'arxiu.

592
00:50:15,520 --> 00:50:21,270
Basat en això, llavors vostè va a voler tenir algun tipus de Iterador

593
00:50:21,270 --> 00:50:26,760
per recórrer l'arbre.

594
00:50:26,760 --> 00:50:31,460
I a continuació, en funció de si el bit és 0 o 1,

595
00:50:31,460 --> 00:50:36,920
vostè va a voler moure qualsevol que Iterador cap a l'esquerra o moure'ls a la dreta

596
00:50:36,920 --> 00:50:44,080
tot el camí fins arribar a un full, de manera que tot el camí fins a aquest node que està en

597
00:50:44,080 --> 00:50:48,260
no apunta a cap nodes més.

598
00:50:48,260 --> 00:50:54,300
Per què hi farem això amb un arxiu de Huffman, però no el codi Morse?

599
00:50:54,300 --> 00:50:56,610
Perquè en codi Morse que hi ha una mica d'ambigüitat.

600
00:50:56,610 --> 00:51:04,440
Podríem ser com, oh espera, ens hem topat amb una carta en el camí, així que potser aquesta és la nostra carta,

601
00:51:04,440 --> 00:51:08,150
mentre que si seguim una mica més, llavors hauria colpejat una altra carta.

602
00:51:08,150 --> 00:51:13,110
Però això no passarà a la codificació Huffman,

603
00:51:13,110 --> 00:51:17,540
per la qual cosa podem estar segurs que l'única manera que anem a colpejar un caràcter

604
00:51:17,540 --> 00:51:23,480
és si els fills esquerre i dret que node són NULL.

605
00:51:28,280 --> 00:51:32,350
>> Finalment, volem alliberar tots de la nostra memòria.

606
00:51:32,350 --> 00:51:37,420
Volem tant a tancar l'arxiu Huff que hem estat tractant amb

607
00:51:37,420 --> 00:51:41,940
així com eliminar tots els arbres del nostre bosc.

608
00:51:41,940 --> 00:51:46,470
Segons la seva aplicació, vostè està probablement va a voler cridar a treure bosc

609
00:51:46,470 --> 00:51:49,780
lloc de realment anar a través de tots els arbres vostè mateix.

610
00:51:49,780 --> 00:51:53,430
Però si vostè va fer els arbres temporals, haurà d'alliberar això.

611
00:51:53,430 --> 00:51:59,060
Vostè sap que el seu millor codi, així que vostè sap on és l'assignació de memòria.

612
00:51:59,060 --> 00:52:04,330
Així que si vas a, comenci fins i tot per al Control f'ing malloc,

613
00:52:04,330 --> 00:52:08,330
veient cada vegada que malloc i assegurar-se que et alliberi de tot això

614
00:52:08,330 --> 00:52:10,190
però llavors només va a través del seu codi,

615
00:52:10,190 --> 00:52:14,260
entendre en què podria haver assignat la memòria.

616
00:52:14,260 --> 00:52:21,340
En general, podeu dir: "Després d'un arxiu que només vaig a treure la meva bosc en bosc"

617
00:52:21,340 --> 00:52:23,850
així que bàsicament esborrar aquest record, sense que,

618
00:52:23,850 --> 00:52:28,310
"I llavors jo també vaig a tancar l'arxiu i llavors el meu programa deixarà de fumar."

619
00:52:28,310 --> 00:52:33,810
Però és que l'única vegada que el seu programa es tanca?

620
00:52:33,810 --> 00:52:37,880
No, perquè de vegades pot haver hagut un error que va ocórrer.

621
00:52:37,880 --> 00:52:42,080
Potser no hem pogut obrir un arxiu o no podíem fer altra arbre

622
00:52:42,080 --> 00:52:49,340
o algun tipus d'error ocorregut en el procés d'assignació de memòria i pel que va tornar NULL.

623
00:52:49,340 --> 00:52:56,710
Un errada i després vam tornar i deixar de fumar.

624
00:52:56,710 --> 00:53:02,040
Així que vostè vol assegurar-se que qualsevol moment és possible que el programa pot deixar de fumar,

625
00:53:02,040 --> 00:53:06,980
desitja alliberar tota la memòria allà.

626
00:53:06,980 --> 00:53:13,370
No només estarà a la final de la funció principal que surt del seu codi.

627
00:53:13,370 --> 00:53:20,780
Vols veure de nou a tots els casos que el codi potencialment podria tornar abans d'hora

628
00:53:20,780 --> 00:53:25,070
i després alliberar la memòria tot el que té sentit.

629
00:53:25,070 --> 00:53:30,830
Digui que l'havia cridat a fer del bosc i que va tornar falsa.

630
00:53:30,830 --> 00:53:34,230
Llavors probablement no haurà de treure el seu bosc

631
00:53:34,230 --> 00:53:37,080
No té un bosc encara.

632
00:53:37,080 --> 00:53:42,130
Però en tots els punts del codi en el qual podria tornar abans d'hora

633
00:53:42,130 --> 00:53:46,160
vostè voldrà assegurar-se que vostè alliberar qualsevol memòria possible.

634
00:53:46,160 --> 00:53:50,020
>> Així que quan ens enfrontem a l'alliberament de memòria i tenir fuites potencials,

635
00:53:50,020 --> 00:53:55,440
Volem no només utilitzarem el nostre judici i la nostra lògica

636
00:53:55,440 --> 00:54:01,850
sinó també utilitzar Valgrind per determinar si s'ha alliberat tota la nostra memòria correctament o no.

637
00:54:01,850 --> 00:54:09,460
Podeu executar Valgrind en Puff i llavors vostè ha de passar també

638
00:54:09,460 --> 00:54:14,020
el nombre correcte d'arguments de línia de comandes per Valgrind.

639
00:54:14,020 --> 00:54:18,100
Pots córrer, però la sortida és una mica críptic.

640
00:54:18,100 --> 00:54:21,630
Ens hem tornat una mica acostumat a això amb el revisor ortogràfic, però encara necessitem l'ajuda d'una mica més,

641
00:54:21,630 --> 00:54:26,450
de manera que també s'executa amb algunes banderes més com la fugida-check = complet,

642
00:54:26,450 --> 00:54:32,040
que probablement ens donarà una sortida més útil sobre Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Després, un altre consell útil quan s'està depurant és la comanda diff.

644
00:54:39,040 --> 00:54:48,520
Pot accedir a l'aplicació al personal de Huff, córrer que en un arxiu de text,

645
00:54:48,520 --> 00:54:55,400
i després la sortida a un fitxer binari, un arxiu binari Huff, que és específica.

646
00:54:55,400 --> 00:54:59,440
Llavors si executa el seu propi alè sobre aquest arxiu binari,

647
00:54:59,440 --> 00:55:03,950
llavors l'ideal, l'arxiu de text de sortida tipus serà idèntic

648
00:55:03,950 --> 00:55:08,200
a l'original que passa pulg

649
00:55:08,200 --> 00:55:15,150
Aquí estic fent servir hth.txt com a exemple, i aquesta és la que es parla en la seva especificació.

650
00:55:15,150 --> 00:55:21,040
Això és, literalment, només HTH i després un salt de línia.

651
00:55:21,040 --> 00:55:30,970
Però definitivament se sent lliure i que són sens dubte anima a utilitzar més exemples

652
00:55:30,970 --> 00:55:32,620
per l'arxiu de text.

653
00:55:32,620 --> 00:55:38,110
>> Vostè pot fins i tot fer una foto a potser la compressió i descompressió de llavors

654
00:55:38,110 --> 00:55:41,600
alguns dels arxius que s'utilitzen en Speller com Guerra i Pau

655
00:55:41,600 --> 00:55:46,710
o Jane Austen o alguna cosa per l'estil - que seria una mena de fresc - o Austin Powers,

656
00:55:46,710 --> 00:55:51,880
tipus de tractar amb arxius més grans, ja que no hauria arribat fins a ell

657
00:55:51,880 --> 00:55:55,590
si fem servir la següent eina aquí, ls-l.

658
00:55:55,590 --> 00:56:01,150
Estem acostumats a ls, que bàsicament mostra tots els continguts al nostre directori actual.

659
00:56:01,150 --> 00:56:07,860
En passar per la bandera-l en realitat mostra la mida dels arxius.

660
00:56:07,860 --> 00:56:12,690
Si vostè va a través de l'especificació del conjunt de processadors, el que realment li guia a través de crear l'arxiu binari,

661
00:56:12,690 --> 00:56:16,590
de bufar, i es veu que per arxius molt petits

662
00:56:16,590 --> 00:56:23,910
el cost de l'espai de comprimir i traduir tota aquesta informació

663
00:56:23,910 --> 00:56:26,980
de totes les freqüències i coses per l'estil que sigui més gran que el benefici real

664
00:56:26,980 --> 00:56:30,000
de comprimir l'arxiu en el primer lloc.

665
00:56:30,000 --> 00:56:37,450
Però si l'executa en alguns arxius de text més llargs, llavors és possible que vegi que vostè comença a aconseguir algun benefici

666
00:56:37,450 --> 00:56:40,930
a la compressió dels arxius.

667
00:56:40,930 --> 00:56:46,210
>> I, finalment, tenim al nostre vell amic GDB, que sens dubte serà molt útil també.

668
00:56:48,360 --> 00:56:55,320
>> Tenim alguna pregunta sobre els arbres Huff o el procés potser de fer que els arbres

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

670
00:57:00,680 --> 00:57:02,570
Bé. Em quedaré voltant per una mica.

671
00:57:02,570 --> 00:57:06,570
>> Gràcies a tots. Això era Tutorial 6. I bona sort.

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