1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walkthrough - Problemo Serio 6]

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

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

4
00:00:07,240 --> 00:00:12,180
>> Saluton, ĉiuj, kaj bonvenon al Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
En Huff'n Puff kion ni faras tuj estos kontraktanta kun Huffman kunpremita dosiero

6
00:00:17,440 --> 00:00:20,740
kaj tiam fumante ĝin supren, por decompressing ĝin,

7
00:00:20,740 --> 00:00:25,810
tiel ke ni povos traduki el la _0s_ kaj _1s_ ke la uzanto sendas al ni

8
00:00:25,810 --> 00:00:30,660
kaj igi ĝin denove en la originala teksto.

9
00:00:30,660 --> 00:00:34,360
Pset 6 tuj estos bela malvarmeta ĉar vi tuj vidos kelkajn el la iloj

10
00:00:34,360 --> 00:00:41,730
ke vi uzis en pset 4 kaj pset 5 kaj tipon de kombini ilin en 1 belan neta koncepto

11
00:00:41,730 --> 00:00:43,830
kiam vi venos por pensi pri ĝi.

12
00:00:43,830 --> 00:00:50,110
>> Ankaŭ, eble, pset 4 kaj 5 estis la plej defia psets ke ni devis proponi.

13
00:00:50,110 --> 00:00:53,950
Do de nun, ni havas ĉi ankoraŭ 1 pset en C,

14
00:00:53,950 --> 00:00:56,480
kaj tuj poste ni al retejo programado.

15
00:00:56,480 --> 00:01:02,310
Do gratulas vin por atingi super la plej malmolaj ĝibo en CS50.

16
00:01:03,630 --> 00:01:09,760
>> Movante on por Huff'n Puff, nia iloj por ĉi pset tuj estos Huffman arboj,

17
00:01:09,760 --> 00:01:14,700
tiel kompreni ne nur kiel duumaj arboj laboron sed ankaŭ specife Huffman arboj,

18
00:01:14,700 --> 00:01:16,240
kiom ili estas konstruita.

19
00:01:16,240 --> 00:01:20,210
Kaj tiam ni havos multe de dissendo kodo en ĉi pset,

20
00:01:20,210 --> 00:01:22,480
kaj ni venis vidi kiu vere iuj de la kodo

21
00:01:22,480 --> 00:01:24,670
ni eble ne povos plene kompreni ankoraux,

22
00:01:24,670 --> 00:01:30,080
kaj tiel tiuj estos la. c dosierojn, sed tiam la koneksa. h dosieroj

23
00:01:30,080 --> 00:01:34,300
donos al ni sufiĉe komprenon ke ni bezonas tiel ke ni scias, kiel tiuj funkcioj funkcii

24
00:01:34,300 --> 00:01:38,100
aŭ almenaŭ kion ili devus fari - iliaj enigoj kaj eligoj -

25
00:01:38,100 --> 00:01:40,760
eĉ se ni ne scias kio okazas en la nigra skatolo

26
00:01:40,760 --> 00:01:44,090
aŭ ne komprenas kio okazas en la nigra skatolo ene.

27
00:01:44,090 --> 00:01:49,400
Kaj poste fine, kiel kutime, ni pritraktas novajn datumstrukturoj,

28
00:01:49,400 --> 00:01:51,840
specifaj tipoj de nodoj kiuj indikas iujn aferojn,

29
00:01:51,840 --> 00:01:56,080
kaj tiel tie havi plumo kaj papero ne nur por la dezajno procezo

30
00:01:56,080 --> 00:01:58,470
kaj kiam vi provas diveni kiel via pset devus funkcii

31
00:01:58,470 --> 00:02:00,520
sed ankaŭ dum depuración.

32
00:02:00,520 --> 00:02:06,140
Vi povas havi GDB apud viaj plumo kaj papero dum vi prenos malsupren kion la valoroj estas,

33
00:02:06,140 --> 00:02:09,320
kie estas via sagoj estas montrante, kaj aferojn tiel.

34
00:02:09,320 --> 00:02:13,720
>> Unue ni rigardu Huffman arboj.

35
00:02:13,720 --> 00:02:19,600
Huffman arboj estas duumaj arboj, signifo ke ĉiu vertico havas nur 2 idoj.

36
00:02:19,600 --> 00:02:24,870
En Huffman arboj la karakterizo estas ke la plej ofta valoroj

37
00:02:24,870 --> 00:02:27,140
estas reprezentitaj de la malplej bitoj.

38
00:02:27,140 --> 00:02:32,690
Ni vidis en prelego ekzemploj de Morsa kodo, kiu ia solidigita iuj literoj.

39
00:02:32,690 --> 00:02:38,030
Se vi provas traduki la A aŭ E, ekzemple,

40
00:02:38,030 --> 00:02:43,940
vi tradukante ke ofte, do anstataŭ devi uzi la plena aro de bitoj

41
00:02:43,940 --> 00:02:48,640
asignitaj por tiu kutima datumtipo, vi kunpremi ĝin al malpli,

42
00:02:48,640 --> 00:02:53,730
kaj tiam tiuj literoj, kiuj estas reprezentitaj malpli ofte estas reprezentitaj per plu bitoj

43
00:02:53,730 --> 00:02:59,840
ĉar vi povas pagi, ke kiam vi pesas el la oftecojn ke tiuj literoj aperas.

44
00:02:59,840 --> 00:03:03,020
Ni havas la sama ideo tie en Huffman arboj

45
00:03:03,020 --> 00:03:12,360
kie ni estas farante ĉenon, speco de vojo por atingi la certaj karakteroj.

46
00:03:12,360 --> 00:03:14,470
Kaj tiam la karakteroj kiuj havas la plej frekvenca

47
00:03:14,470 --> 00:03:17,940
tuj estos reprezentita per la malplej bitoj.

48
00:03:17,940 --> 00:03:22,020
>> La vojo, kiun vi konstruas Huffman arbo

49
00:03:22,020 --> 00:03:27,430
Estas metante ĉiujn karakterojn kiuj aperas en la teksto

50
00:03:27,430 --> 00:03:30,630
kaj kalkuli siajn ofteco, kiom ofte aperas.

51
00:03:30,630 --> 00:03:33,880
Tio povus bone esti grafo de kiom fojoj tiuj literoj aperas

52
00:03:33,880 --> 00:03:40,270
aŭ eble procenton de el ĉiuj karakteroj kiom da ĉiu aperas.

53
00:03:40,270 --> 00:03:44,270
Kaj tiel tio, kion vi faras estas iam vi havas ĉiuj de tiu mapita eksteren,

54
00:03:44,270 --> 00:03:49,060
tiam vi serĉas la plej malalta 2 frekvencoj kaj poste kunigi ilin kiel gefratoj

55
00:03:49,060 --> 00:03:55,660
kie tiam la patro nodo havas oftecon kiu estas la sumo de liaj 2 infanoj.

56
00:03:55,660 --> 00:04:00,870
Kaj poste vi per konvencio diri ke la maldekstra nodo,

57
00:04:00,870 --> 00:04:03,770
vi sekvas ke sekvante la 0 branĉo,

58
00:04:03,770 --> 00:04:08,140
kaj tiam la plej dekstra nodo estas la 1 branĉo.

59
00:04:08,140 --> 00:04:16,040
Kiel ni vidis en Morsa kodo, la gotcha estis ke se vi havis nur pepi kaj la pepi

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

61
00:04:18,120 --> 00:04:22,430
Ĝi povus aŭ esti 1 litero aŭ ĝi povis esti vico de 2 literoj.

62
00:04:22,430 --> 00:04:27,790
Kaj tiel kion Huffman arboj faras estas pro sia naturo de la karakteroj

63
00:04:27,790 --> 00:04:34,140
aŭ nia fina reala gravuloj esti la lasta nodoj en la branĉo -

64
00:04:34,140 --> 00:04:39,300
ni priparolas tiujn kiel folioj - virto de tiu tie ne povas esti ajna ambigueco

65
00:04:39,300 --> 00:04:45,160
en terminoj de kiuj letero vi provas kodi kun la serio de bitoj

66
00:04:45,160 --> 00:04:50,670
ĉar nenie kune la bitoj kiuj reprezentas 1 letero

67
00:04:50,670 --> 00:04:55,960
vi renkontos alian tuta letero, kaj ne estos ajna konfuzo tie.

68
00:04:55,960 --> 00:04:58,430
Sed ni iros en ekzemploj ke vi infanoj povas fakte vidi ke

69
00:04:58,430 --> 00:05:02,120
anstataŭ ni nur diras al vi, ke tio estas vera.

70
00:05:02,120 --> 00:05:06,390
>> Ni rigardu simpla ekzemplo de Huffman arbo.

71
00:05:06,390 --> 00:05:09,380
Mi havas ĉenon tie estas 12 signojn longa.

72
00:05:09,380 --> 00:05:14,010
Mi havas 4 Kiel, 6 Bs, kaj 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Mia unua paŝo estus rakonti.

74
00:05:17,270 --> 00:05:20,760
Kiom da fojoj tio A aperi? Ĝi aperas 4 fojojn en la kordo.

75
00:05:20,760 --> 00:05:25,060
B aperas 6 fojojn, kaj C aperas 2 fojojn.

76
00:05:25,060 --> 00:05:28,970
Nature, mi intencis diri Mi uzas B plej ofte,

77
00:05:28,970 --> 00:05:35,970
do mi volas reprezenti B kun la malplej kvanto de bitoj, la malplej kvanto de _0s_ kaj _1s_.

78
00:05:35,970 --> 00:05:42,600
Kaj tiam mi ankaŭ tuj atendus C al postulas la plej kvanto de _0s_ kaj _1s_ tiel.

79
00:05:42,600 --> 00:05:48,550
Unue kion mi faris tie mi metis ilin en suprenira ordo en terminoj de ofteco.

80
00:05:48,550 --> 00:05:52,710
Ni vidas, ke la C kaj la A, tiuj estas niaj 2 plej malalta oftecoj.

81
00:05:52,710 --> 00:06:00,290
Ni kreos patro nodo, kaj ke patro nodo ne havas literon asociita kun ĝi,

82
00:06:00,290 --> 00:06:05,070
sed ĝi havas oftecon, kiu estas la sumo.

83
00:06:05,070 --> 00:06:08,780
La sumo iĝas 2 + 4, kiu estas 6.

84
00:06:08,780 --> 00:06:10,800
Tiam ni sekvu la maldekstra branĉo.

85
00:06:10,800 --> 00:06:14,970
Se ni estus en tiu 6 nodo, tiam ni devus sekvi 0 al preni al C

86
00:06:14,970 --> 00:06:17,450
kaj tiam 1 ĝis alveni al A.

87
00:06:17,450 --> 00:06:20,300
Do nun ni havas 2 nodoj.

88
00:06:20,300 --> 00:06:23,920
Ni havas la valoron 6 kaj poste ni ankaŭ havas alian nodon kun la valoro 6.

89
00:06:23,920 --> 00:06:28,550
Kaj tial tiuj 2 estas ne nur la 2 plej malalta sed ankaŭ nur la 2, kiuj restis,

90
00:06:28,550 --> 00:06:33,820
do ni aliĝi tiuj de alia patro, kun la sumo estante 12.

91
00:06:33,820 --> 00:06:36,300
Do jen ni havas niajn Huffman arbo

92
00:06:36,300 --> 00:06:40,020
kie akiri al B, kiu estus nur la bito 1

93
00:06:40,020 --> 00:06:45,430
kaj poste por akiri al A ni havus 01 kaj tiam C havanta 00.

94
00:06:45,430 --> 00:06:51,300
Do jen ni vidas ke esence ni reprezentas tiuj signoj kun ĉu 1 aŭ 2 bitoj

95
00:06:51,300 --> 00:06:55,160
kie la B, kiel antaŭdiris, havas la malplej.

96
00:06:55,160 --> 00:07:01,730
Kaj poste ni atendis C havi la plej, sed ĉar ĝi estas tiel malgranda Huffman arbo,

97
00:07:01,730 --> 00:07:06,020
tiam la A estas ankaŭ reprezentita de 2 bitoj kiel kontraŭ ie en la mezo.

98
00:07:07,820 --> 00:07:11,070
>> Nur iri super alia simpla ekzemplo de la kodigo arbo,

99
00:07:11,070 --> 00:07:19,570
diras, ke vi havas la ĉeno "Saluton."

100
00:07:19,570 --> 00:07:25,360
Kion vi faras, estas unue vi dirus kiom da fojoj tio H aperas en tio?

101
00:07:25,360 --> 00:07:34,200
H aperas unufoje kaj poste e aperas unufoje kaj poste ni havas l'aperi dufoje

102
00:07:34,200 --> 00:07:36,580
kaj o aperante unufoje.

103
00:07:36,580 --> 00:07:44,310
Kaj tiel poste ni atendas ke letero por esti prezentita per la malplej kvanto de bitoj?

104
00:07:44,310 --> 00:07:47,450
[Studento] l. >> L. Yeah. l estas prava.

105
00:07:47,450 --> 00:07:50,730
Ni atendas l esti prezentita per la malplej kvanto de bitoj

106
00:07:50,730 --> 00:07:55,890
ĉar l uzas plej en la ĉeno "Saluton."

107
00:07:55,890 --> 00:08:04,280
Kion mi faros nun estas nudigos tiuj nodoj.

108
00:08:04,280 --> 00:08:15,580
Mi havas 1, kiu estas H, kaj poste alia 1, kiu estas e, kaj tiam 1, kiu estas o -

109
00:08:15,580 --> 00:08:23,410
nun mi metis ilin en ordo - kaj tiam 2, kiu estas l.

110
00:08:23,410 --> 00:08:32,799
Tiam mi diras la vojo, kiun mi konstruas Huffman arbo estas trovi la 2 nodoj kun la malplej frekvencoj

111
00:08:32,799 --> 00:08:38,010
kaj Mi faros ilin gefratoj kreante patro nodo.

112
00:08:38,010 --> 00:08:41,850
Ĉi tie ni havas 3 nodoj kun la plej malalta ofteco. Ili estas ĉiuj 1.

113
00:08:41,850 --> 00:08:50,620
Do jen ni elekti kiu ni iras ligi unua.

114
00:08:50,620 --> 00:08:54,850
Diru min elekti la H kaj la TTT.

115
00:08:54,850 --> 00:09:01,150
La sumo de 1 + 1 estas 2, sed ĉi nodo ne havas literon asociita kun ĝi.

116
00:09:01,150 --> 00:09:04,440
Ĝi simple tenas la valoro.

117
00:09:04,440 --> 00:09:10,950
Nun ni rigardu la sekvanta 2 plej malalta oftecoj.

118
00:09:10,950 --> 00:09:15,590
Tio estas 2 kaj 1. Tio povus esti iu el tiuj 2, sed mi tuj elekti ĉi tiun.

119
00:09:15,590 --> 00:09:18,800
La sumo estas 3.

120
00:09:18,800 --> 00:09:26,410
Kaj poste fine, mi nur havas 2 maldekstra, do tiam tiu igas 5.

121
00:09:26,410 --> 00:09:32,010
Tiam tie, kiel atendita, se mi plenigu la kodigo por tiu,

122
00:09:32,010 --> 00:09:37,480
1s estas ĉiam la dekstra branĉo kaj _0s_ estas la maldekstra.

123
00:09:37,480 --> 00:09:45,880
Tiam ni havas l'reprezentita de nur 1 bito kaj tiam la o de 2

124
00:09:45,880 --> 00:09:52,360
kaj tiam la TTT per 2 kaj poste la H falas malsupren al 3 bitoj.

125
00:09:52,360 --> 00:09:59,750
Do vi povas transdoni ĉi mesaĝo "Saluton" anstataŭ efektive uzante la karakteroj

126
00:09:59,750 --> 00:10:02,760
por nur _0s_ kaj _1s_.

127
00:10:02,760 --> 00:10:07,910
Tamen, memoru ke en kelkaj kazoj ni havis ligojn kun nia ofteco.

128
00:10:07,910 --> 00:10:11,900
Ni povis esti ĉu aliĝis al la H kaj la o unue eble.

129
00:10:11,900 --> 00:10:15,730
Aŭ tiam poste kiam ni havis la l reprezentita de 2

130
00:10:15,730 --> 00:10:19,410
tiel kiel la aliĝis reprezentita per 2, ni povus esti ligitaj ĉu unu.

131
00:10:19,410 --> 00:10:23,630
>> Kaj tiel, kiam vi sendu la _0s_ kaj _1s_, ke reale ne garantias

132
00:10:23,630 --> 00:10:27,090
ke la ricevanto povas plene legis vian mesaĝon dekstra ekstere la batilo

133
00:10:27,090 --> 00:10:30,490
ĉar ili eble ne scias kion decidon vi faris.

134
00:10:30,490 --> 00:10:34,920
Do kiam ni pritraktas Huffman kunpremo,

135
00:10:34,920 --> 00:10:40,090
iel ni devas diri la ricevanto de nia mesaĝo kiom ni decidis -

136
00:10:40,090 --> 00:10:43,470
Ili bezonas scii ia ekstra informo

137
00:10:43,470 --> 00:10:46,580
krom la kunpremita mesaĝo.

138
00:10:46,580 --> 00:10:51,490
Ili bezonas kompreni, kion la arbo vere aspektas kiel,

139
00:10:51,490 --> 00:10:55,450
kiel ni fakte faris tiujn decidojn.

140
00:10:55,450 --> 00:10:59,100
>> Jen ni estis nur fari ekzemplojn bazita sur la reala grafo,

141
00:10:59,100 --> 00:11:01,550
sed kelkfoje oni povas ankaŭ havi Huffman arbo

142
00:11:01,550 --> 00:11:05,760
bazita sur la frekvenco en kiu literoj aperas, kaj estas la ĝusta sama procezo.

143
00:11:05,760 --> 00:11:09,090
Jen mi esprimas ĝin en terminoj de procentoj aŭ frakcio,

144
00:11:09,090 --> 00:11:11,290
kaj tiel tie la ĝusta sama afero.

145
00:11:11,290 --> 00:11:15,300
Mi trovas la 2 plej malalta, resumi ilin, la sekvanta 2 plej malalta, resumi ilin,

146
00:11:15,300 --> 00:11:19,390
ĝis mi havas plenan arbon.

147
00:11:19,390 --> 00:11:23,610
Eĉ kvankam ni povus fari ĝin ĉu vojo, kiam ni pritraktas procentoj,

148
00:11:23,610 --> 00:11:27,760
kiu signifu ni dividante aĵoj kaj kontraktanta kun glitpunktaj nombroj aŭ pli ĝuste flosas

149
00:11:27,760 --> 00:11:30,900
se ni pensas pri datumstrukturoj en kapo.

150
00:11:30,900 --> 00:11:32,540
Kion ni scias pri flosas?

151
00:11:32,540 --> 00:11:35,180
Kio estas komuna problemo kiam ni pritraktas flosas?

152
00:11:35,180 --> 00:11:38,600
[Studento] malpreciza aritmetiko. >> Jes. Imprecision.

153
00:11:38,600 --> 00:11:43,760
Pro glitpunktaj imprecision, por ĉi pset por ke ni certigu

154
00:11:43,760 --> 00:11:49,450
ke ni ne perdas ajnan valoroj, tiam ni efektive tuj estos kontraktanta kun la grafo.

155
00:11:49,450 --> 00:11:54,880
Do se vi estus pensi de Huffman nodo, se vi retrorigardas al la strukturo tie,

156
00:11:54,880 --> 00:12:01,740
se vi rigardas la verdoj havas ofteco asociita kun ĝi

157
00:12:01,740 --> 00:12:08,760
tiel kiel notas al nodo al lia maldekstra tiel kiel nodo al lia rajto.

158
00:12:08,760 --> 00:12:13,970
Kaj tiam la ruĝaj tie ankaŭ havas karakteron asociita kun ili.

159
00:12:13,970 --> 00:12:18,900
Ni ne intencas fari apartan bonaj por la gepatroj kaj poste la fina verticoj,

160
00:12:18,900 --> 00:12:23,680
kiuj ni raportas kiel folioj, sed prefere tiujn simple devos NULL valoroj.

161
00:12:23,680 --> 00:12:31,050
Po nodo ni havas karakteron, la simbolo kiu ke nodo reprezentas,

162
00:12:31,050 --> 00:12:40,490
tiam ofteco tiel kiel puntero al lia maldekstra infano kaj ankaŭ lia dekstra infano.

163
00:12:40,490 --> 00:12:45,680
La folioj, kiuj estas je la tre fundo, ankaŭ devus nodo punteros

164
00:12:45,680 --> 00:12:49,550
al lia maldekstra kaj la dekstra, sed pro tio ke tiuj valoroj ne indikante reala nodoj,

165
00:12:49,550 --> 00:12:53,970
kio estus ilia valoro estos? >> [Studento] NULL. >> NULL. Ekzakte.

166
00:12:53,970 --> 00:12:58,430
Jen ekzemplo de kiel vi eble reprezentas la ofteco en flosas,

167
00:12:58,430 --> 00:13:02,130
sed ni tuj estos kontraktanta kun ĝi kun entjeroj,

168
00:13:02,130 --> 00:13:06,780
tiel ĉiuj mi faris estas ŝanĝi la datumtipo tie.

169
00:13:06,780 --> 00:13:09,700
>> Ni iru al iom pli kompleksa ekzemplo.

170
00:13:09,700 --> 00:13:13,360
Sed nun, kiam ni faris la simplaj, estas nur la sama procezo.

171
00:13:13,360 --> 00:13:20,290
Vi trovos la 2 plej malalta frekvencoj, resumi la oftecojn

172
00:13:20,290 --> 00:13:22,450
kaj tio estas la nova frekvenco de via patro nodo,

173
00:13:22,450 --> 00:13:29,310
kiuj tiam notas al lia maldekstra kun la 0 branĉo kaj la dekstra kun la 1 branĉo.

174
00:13:29,310 --> 00:13:34,200
Se ni havas la ĉeno "Tio estas cs50," tiam ni kalkulu kiom da fojoj ĝi T menciis,

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

176
00:13:38,420 --> 00:13:42,010
Tiam kion mi faris tie estas kun la ruĝa nodoj Mi nur plantis,

177
00:13:42,010 --> 00:13:48,530
Mi diris ke mi tuj devos tiujn karakterojn eventuale je la fundo de mia arbo.

178
00:13:48,530 --> 00:13:51,740
Tiuj tuj estos la tuta de la folioj.

179
00:13:51,740 --> 00:13:58,200
Tiam kion mi faris estas mi ordo ili ofteco en suprenira ordo,

180
00:13:58,200 --> 00:14:02,950
kaj ĉi tiu estas vere la vojon, ke la pset kodo faras ĝin

181
00:14:02,950 --> 00:14:07,550
ĉu specoj ĝin ofteco kaj tiam alfabete.

182
00:14:07,550 --> 00:14:13,870
Do ĝi havas la numerojn unua kaj tiam alfabete de la frekvenco.

183
00:14:13,870 --> 00:14:18,520
Tiam kion mi farus estas mi trovus la 2 plej malalta. Tio estas 0 kaj 5.

184
00:14:18,520 --> 00:14:22,390
Mi resumi ilin, kaj tio estas 2. Tiam mi daŭrigus, trovi la sekvanta 2 plej malalta.

185
00:14:22,390 --> 00:14:26,100
Tiuj estas la du 1s, kaj tiam tiuj fariĝis 2 kiel bone.

186
00:14:26,100 --> 00:14:31,570
Nun mi scias ke mia sekva paŝo tuj estos kunigi la plej malalta nombro,

187
00:14:31,570 --> 00:14:41,380
kiu estas la T, la 1, kaj poste elekti unu el la nodoj kiu havas 2 kiel la frekvenco.

188
00:14:41,380 --> 00:14:44,560
Do jen ni havas 3 eblojn.

189
00:14:44,560 --> 00:14:47,980
Kion mi faros por la glito nur vide reordigi ilin por vi

190
00:14:47,980 --> 00:14:51,790
por ke vi povas vidi kiel mi konstrui ĝin.

191
00:14:51,790 --> 00:14:59,040
Kion la kodon kaj vian dissendo kodo tuj faros estus kunigi la T unu

192
00:14:59,040 --> 00:15:01,410
kun la 0 kaj 5 nodo.

193
00:15:01,410 --> 00:15:05,060
Tial ke sumoj al 3, kaj poste ni daŭrigos la procezon.

194
00:15:05,060 --> 00:15:08,660
La 2 kaj la 2 nun estas la plej malalta, do tiam tiuj adicias 4.

195
00:15:08,660 --> 00:15:12,560
Cxiu sekvas ĝis nun? Okay.

196
00:15:12,560 --> 00:15:16,410
Tiam, post ke ni havas la 3 kaj la 3 kiu bezonas esti aldonita supren,

197
00:15:16,410 --> 00:15:21,650
do denove mi nur ŝanĝi ĝin tiel ke vi povas vidi vide por ke ĝi ne ricevas tro senorda.

198
00:15:21,650 --> 00:15:25,740
Tiam ni havas 6, kaj tiam nia fina paŝo estas nun ke ni nur havas 2 nodoj

199
00:15:25,740 --> 00:15:30,440
ni resumi tiujn fari la radiko de nia arbo, kiu estas 10.

200
00:15:30,440 --> 00:15:34,100
Kaj la nombro 10 havas sencon ĉar ĉiu vertico reprezentis,

201
00:15:34,100 --> 00:15:40,750
lia valoro, lia ofteco numeron, estis kiom fojoj ili aperis en la ĉeno,

202
00:15:40,750 --> 00:15:46,350
kaj poste ni havas 5 signojn en nia kordoj, tiel ke havas sencon.

203
00:15:48,060 --> 00:15:52,320
Se ni rigardas supren, kiamaniere ni vere kodi ĝi,

204
00:15:52,320 --> 00:15:56,580
kiel atendita, la i kaj la s, kiu prezentas la plej ofte

205
00:15:56,580 --> 00:16:01,350
estas reprezentitaj de la malplej kvanto de bitoj.

206
00:16:03,660 --> 00:16:05,660
>> Gardu tie.

207
00:16:05,660 --> 00:16:09,780
En Huffman arboj la kazo vere gravas.

208
00:16:09,780 --> 00:16:13,670
An majuskla S estas malsama ol minuskla s.

209
00:16:13,670 --> 00:16:21,260
Se ni havis "Tio estas CS50" kun majuskloj, do la minuskla s nur aperus duoble,

210
00:16:21,260 --> 00:16:27,120
Estus nodo kun 2 kiel ĝia valoro, kaj tiam majuskla S nur estus unu fojon.

211
00:16:27,120 --> 00:16:33,440
Do tiam via arbo ŝanĝus strukturoj ĉar vi efektive havas ekstra folio ĉi tie.

212
00:16:33,440 --> 00:16:36,900
Sed la sumo estus ankoraŭ 10.

213
00:16:36,900 --> 00:16:39,570
Tio estas kion ni reale tuj estos nomante la checksum,

214
00:16:39,570 --> 00:16:44,060
la aldono de ĉiuj el la grafoj.

215
00:16:46,010 --> 00:16:50,990
>> Nun ke ni kovris Huffman arboj, ni povas plonĝi en Huff'n Puff, la pset.

216
00:16:50,990 --> 00:16:52,900
Ni tuj komenci kun sekcio de demandoj,

217
00:16:52,900 --> 00:16:57,990
kaj ĉi tiu tuj ekiru alkutimiĝis kun binara arboj kaj kiel operacii ĉirkaŭ ke:

218
00:16:57,990 --> 00:17:03,230
desegni nodojn, kreante vian propran typedef struct por nodo,

219
00:17:03,230 --> 00:17:07,230
kaj vidi kiel vi eble enmeti en duuma arbo, tiu ke tio ordo,

220
00:17:07,230 --> 00:17:09,050
lauxiris ĝin, kaj tion tiel.

221
00:17:09,050 --> 00:17:14,560
Ke scio estas definitive tuj helpi vin, kiam vi pikita en la Huff'n Puff parto

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

223
00:17:19,150 --> 00:17:26,329
En la normo eldono de la pset, via tasko estas realigi Puff,

224
00:17:26,329 --> 00:17:30,240
kaj en la hacker versio Via tasko estas realigi Huff.

225
00:17:30,240 --> 00:17:38,490
Kio Huff faras estas prenas teksto kaj tiam tradukas gxin en la _0s_ kaj _1s_,

226
00:17:38,490 --> 00:17:41,990
tiel la procezo, kiun ni faris supre, kie ni kalkulis la frekvencojn

227
00:17:41,990 --> 00:17:50,970
kaj poste faris la arbon kaj poste diris: "Kiel mi estas rekompenciĝita T?"

228
00:17:50,970 --> 00:17:54,840
T estas reprezentita de 100, aĵoj kiel tiu,

229
00:17:54,840 --> 00:17:58,860
kaj tiam Huff prenus la tekston kaj poste eligo ke binaraj.

230
00:17:58,860 --> 00:18:04,920
Sed ankaŭ ĉar ni scias ke ni volas permesi nian ricevanto de la mesaĝo

231
00:18:04,920 --> 00:18:11,790
amuzi la ĝusta sama arbo, ĝi inkludas ankaŭ informojn pri la ofteco grafoj.

232
00:18:11,790 --> 00:18:17,980
Tiam kun Puff ni estas donita duargumenta arkivon de _0s_ kaj _1s_

233
00:18:17,980 --> 00:18:21,740
kaj donis ankaŭ la informon pri la frekvencoj.

234
00:18:21,740 --> 00:18:26,740
Ni traduki ĉiujn tiuj _0s_ kaj _1s_ dorso enen la originala mesaĝo kiu estis,

235
00:18:26,740 --> 00:18:29,350
do ni decompressing tio.

236
00:18:29,350 --> 00:18:36,450
Se vi faras la normon eldono, vi ne bezonas apliki Huff,

237
00:18:36,450 --> 00:18:39,290
tiel tiam vi povas simple uzi la bastonon efektivigo de Huff.

238
00:18:39,290 --> 00:18:42,080
Esas instrukciojn en la specifo pri kiel fari tion.

239
00:18:42,080 --> 00:18:48,780
Vi povas lanĉi la bastonon efektivigo de Huff sur iu teksta dosiero

240
00:18:48,780 --> 00:18:53,270
kaj poste uzas tiun produktadon laŭ via enigo al Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kiel mi menciis antaŭe, ni havas multe da dissendo kodo por tiu ĉi.

242
00:18:59,330 --> 00:19:01,810
Mi tuj komencos tuj tra ĝi.

243
00:19:01,810 --> 00:19:04,400
Mi pasigos la plejparto de la tempo sur la. H dosieroj

244
00:19:04,400 --> 00:19:07,660
ĉar en la. c dosierojn, ĉar ni havas la. h

245
00:19:07,660 --> 00:19:11,650
kaj tio donas al ni la prototipoj de la funkcioj,

246
00:19:11,650 --> 00:19:15,520
ni ne tute bezonas kompreni ĝuste -

247
00:19:15,520 --> 00:19:20,280
Se vi ne komprenas kio okazas en la. C dosieroj, tiam ne tro maltrankviliĝu,

248
00:19:20,280 --> 00:19:23,600
sed definitive provu rigardi ĉar ĝi povus doni iujn aludoj

249
00:19:23,600 --> 00:19:29,220
kaj estas utila por alkutimiĝi al legado fremdajn kodo.

250
00:19:38,940 --> 00:19:48,270
>> Rigardante huffile.h, en la komentoj deklaras mantelo de abstraktado por Huffman-kodita dosierojn.

251
00:19:48,270 --> 00:20:01,660
Se ni iras malsupren, oni vidas ke estas maksimumo de 256 simboloj kiuj ni povus bezoni kodojn por.

252
00:20:01,660 --> 00:20:05,480
Tio inkluzivas ĉiujn literojn de la alfabeto - majuskle kaj minuskle -

253
00:20:05,480 --> 00:20:08,250
kaj tiam simboloj kaj numeroj, ktp

254
00:20:08,250 --> 00:20:11,930
Tiam tie ni havas magian nombron identiganta Huffman-kodita dosiero.

255
00:20:11,930 --> 00:20:15,890
Ene de Huffman kodo ili tuj havi iun magia nombro

256
00:20:15,890 --> 00:20:18,560
asociita kun la kaploko.

257
00:20:18,560 --> 00:20:21,110
Tio povas aspekti simple hazarda magia nombro,

258
00:20:21,110 --> 00:20:27,160
sed se vi efektive traduki al ASCII, do ĝi reale hechizos el Huff.

259
00:20:27,160 --> 00:20:34,290
Jen ni havas struct por Huffman-kodita dosiero.

260
00:20:34,290 --> 00:20:39,670
Jen ĉiuj el tiuj karakterizaĵoj asociita kun Huff dosiero.

261
00:20:39,670 --> 00:20:47,080
Tiam cxi tie ni havas la kaplinio por Huff dosieron, do ni nomas ĝin Huffeader

262
00:20:47,080 --> 00:20:50,810
anstataŭ aldonante la ekstran h ĉar ĝi sonas la sama ĉiuokaze.

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

264
00:20:52,720 --> 00:20:57,790
Ni havas magian nombron asociita kun ĝi.

265
00:20:57,790 --> 00:21:09,040
Se temas pri efektiva Huff dosiero, ĝi tuj estos la nombro super, ĉi magio unu.

266
00:21:09,040 --> 00:21:14,720
Kaj tiam ĝi havos tabelo.

267
00:21:14,720 --> 00:21:18,750
Do por ĉiu simbolo, de kiuj estas 256,

268
00:21:18,750 --> 00:21:24,760
ĝi tuj printi kion la ofteco de tiuj simboloj estas ene de la Huff dosiero.

269
00:21:24,760 --> 00:21:28,090
Kaj poste fine, ni havas checksum por la frekvencoj,

270
00:21:28,090 --> 00:21:32,160
kiuj devus esti la sumo de tiuj frekvencoj.

271
00:21:32,160 --> 00:21:36,520
Do, tio estas kion oni Huffeader estas.

272
00:21:36,520 --> 00:21:44,600
Tiam ni havas iujn funkciojn kiuj revenos la venonta bito en la Huff dosieron

273
00:21:44,600 --> 00:21:52,580
tiel kiel skribas iom al la Huff dosiero, kaj tiam ĉi tiu funkcio ĉi tie, hfclose,

274
00:21:52,580 --> 00:21:54,650
ke efektive fermas la Huff dosiero.

275
00:21:54,650 --> 00:21:57,290
Antaŭe, ni pritraktas rekte nur fclose,

276
00:21:57,290 --> 00:22:01,190
sed kiam vi havas Huff dosiero, anstataŭ fclosing ĝin

277
00:22:01,190 --> 00:22:06,080
kion vi vere volas fari estas hfclose kaj hfopen ĝin.

278
00:22:06,080 --> 00:22:13,220
Tiuj estas specifaj funkcioj al la Huff dosierojn kiuj ni tuj estos pritraktas.

279
00:22:13,220 --> 00:22:19,230
Tiam tie ni legas en la kaplinio kaj poste skribi la kaploko.

280
00:22:19,230 --> 00:22:25,700
>> Nur legante la. H dosieron ni povas ia akiri senton de kia Huff dosiero povus esti,

281
00:22:25,700 --> 00:22:32,480
kio karakterizaj havas, sen reale iras en la huffile.c,

282
00:22:32,480 --> 00:22:36,750
kiu, se ni plonĝi en, tuj estos iom pli kompleksa.

283
00:22:36,750 --> 00:22:41,270
Ĝi havas ĉiujn de la dosiero en / el tie pritraktas punteros.

284
00:22:41,270 --> 00:22:48,010
Jen ni vidas ke kiam ni nomas hfread, ekzemple, ĝi estas ankoraŭ pritraktas fread.

285
00:22:48,010 --> 00:22:53,050
Ni ne liveri de tiuj funkcioj tute, sed ni sendas tiujn esti zorgo

286
00:22:53,050 --> 00:22:59,760
ene la Huff dosiero anstataŭ fari ĉiuj ĝin.

287
00:22:59,760 --> 00:23:02,300
Vi povas bonvolu skani tra ĉi se vi estas scivola

288
00:23:02,300 --> 00:23:08,410
kaj iru, kaj senŝeligi la mantelo reen iomete.

289
00:23:20,650 --> 00:23:24,060
>> La venonta dosiero por ke ni tuj rigardi estas tree.h.

290
00:23:24,060 --> 00:23:30,210
Antaŭe en la Walkthrough glitas ni diris nin atendas Huffman nodo

291
00:23:30,210 --> 00:23:32,960
kaj ni faris typedef struct nodo.

292
00:23:32,960 --> 00:23:38,360
Ni atendas havi simbolon, ofteco, kaj poste 2 nodo steloj.

293
00:23:38,360 --> 00:23:41,870
En ĉi tiu kazo kion ni faras estas ĉi estas esence la sama

294
00:23:41,870 --> 00:23:46,880
krom anstataŭ nodo ni iras por voki ilin arboj.

295
00:23:48,790 --> 00:23:56,760
Ni havas funkcion, ke kiam vi nomas fari arbo denove vi arbo puntero.

296
00:23:56,760 --> 00:24:03,450
Back al Speller, kiam vi estis farante novan nodon

297
00:24:03,450 --> 00:24:11,410
vi diris nodo * nova vorto = malloc (sizeof) kaj aĵoj tiel.

298
00:24:11,410 --> 00:24:17,510
Esence, mktree tuj estos pritraktas ke por vi.

299
00:24:17,510 --> 00:24:20,990
Simile, kiam oni volas forigi arbo,

300
00:24:20,990 --> 00:24:24,810
tiel ke tio esence liberigante la arbo, kiam vi faris per ĝi,

301
00:24:24,810 --> 00:24:33,790
anstataŭ eksplicite nomi liberaj sur tiu, vi vere nur tuj uzos la funkcio rmtree

302
00:24:33,790 --> 00:24:40,360
kie pasas en la puntero al tiu arbo kaj tiam tree.c prizorgos, ke por vi.

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

304
00:24:42,490 --> 00:24:47,240
Ni atendas la samajn funkciojn krom vidi la efektivigo tiel.

305
00:24:47,240 --> 00:24:57,720
Kiel ni atendis, kiam vi nomas mktree ĝin mallocs la grandeco de arbo en pointer,

306
00:24:57,720 --> 00:25:03,190
inicializa ĉiuj valoroj al la NULL valoron, do _0s_ aŭ NULLs,

307
00:25:03,190 --> 00:25:08,280
kaj poste redonas la puntero al tiu arbo, kiun vi ĵus malloc'd al vi.

308
00:25:08,280 --> 00:25:13,340
Jen kiam vi nomas forigi arbo ĝin unue certigas ke vi ne duobla liberigi.

309
00:25:13,340 --> 00:25:18,320
Ĝi certigas ke vi efektive havas arbo, kiun vi volas forigi.

310
00:25:18,320 --> 00:25:23,330
Ĉi tie, ĉar arbo inkludas ankaŭ liaj filoj,

311
00:25:23,330 --> 00:25:29,560
kion ĉi tio estas rekursie nomas forigi arbo sur la maldekstra vertico de la arbo

312
00:25:29,560 --> 00:25:31,650
tiel kiel la dekstra nodo.

313
00:25:31,650 --> 00:25:37,790
Antaŭ ol ĝi liberigas la patro, kiun ĝi bezonas por liberigi la infanojn tiel.

314
00:25:37,790 --> 00:25:42,770
Patro ankaŭ estas interŝanĝeblaj kun radiko.

315
00:25:42,770 --> 00:25:46,500
La unua patro, tiel kiel la granda-granda-granda-praavo

316
00:25:46,500 --> 00:25:52,130
aŭ avino arbo, unue ni devas liberigi laŭ la niveloj unua.

317
00:25:52,130 --> 00:25:58,490
Do trairi al la fundo, la libera tiuj, kaj tiam revenu supren, libera tiuj, ktp

318
00:26:00,400 --> 00:26:02,210
Do jen arbo.

319
00:26:02,210 --> 00:26:04,240
>> Nun ni rigardu arbaro.

320
00:26:04,240 --> 00:26:09,860
Arbaro estas kie vi metas ĉiujn viajn Huffman arboj.

321
00:26:09,860 --> 00:26:12,910
Oni diras, ke ni tuj havos iun nomita komploto

322
00:26:12,910 --> 00:26:22,320
kiu enhavas puntero al arbo tiel kiel puntero al komploto nomas proksima.

323
00:26:22,320 --> 00:26:28,480
Kio strukturo faras tian rigardon kiel?

324
00:26:29,870 --> 00:26:32,490
Ĉio diras ĝin tie.

325
00:26:34,640 --> 00:26:36,700
Ĝuste super tie.

326
00:26:37,340 --> 00:26:39,170
Al ligitaj listo.

327
00:26:39,170 --> 00:26:44,590
Ni vidas, ke kiam ni havas intrigo estas kiel ligitaj listo de intrigoj.

328
00:26:44,590 --> 00:26:53,020
Al arbaro estas difinita kiel ligitaj listo de bedoj,

329
00:26:53,020 --> 00:26:58,100
kaj tiel la strukturo de arbaro estas ni nur havos puntero al nia unua intrigo

330
00:26:58,100 --> 00:27:02,740
kaj ke intrigo havas arbo en ĝi aŭ pli ĝuste notas al arbo

331
00:27:02,740 --> 00:27:06,190
kaj poste notas al la sekvanta intrigo, tiel plu kaj tiel plu.

332
00:27:06,190 --> 00:27:11,100
Por fari arbaron ni nomas mkforest.

333
00:27:11,100 --> 00:27:14,930
Tiam ni havas vere utilaj funkcioj tie.

334
00:27:14,930 --> 00:27:23,240
Ni havas repreni kie pasas en arbaro kaj tiam la reveno valoro estas Arbo *,

335
00:27:23,240 --> 00:27:25,210
puntero al arbo.

336
00:27:25,210 --> 00:27:29,370
Kio fosilo faros estas ĝi iros en la arbaron, ke vi indikante

337
00:27:29,370 --> 00:27:35,240
tiam forpreni arbo kun la plej malalta ofteco de tiu arbaro

338
00:27:35,240 --> 00:27:38,330
kaj poste doni al vi la puntero al tiu arbo.

339
00:27:38,330 --> 00:27:43,030
Iam vi nomas repreni, la arbo ne ekzistas en la arbaro plu,

340
00:27:43,030 --> 00:27:48,550
sed la reveno valoro estas la puntero al tiu arbo.

341
00:27:48,550 --> 00:27:50,730
Tiam vi havas planton.

342
00:27:50,730 --> 00:27:57,420
Kondiĉe ke vi pasas en puntero al arbo kiu havas ne-0 ofteco,

343
00:27:57,420 --> 00:28:04,040
kio planto faros estas ĝi prenos la arbaro, prenu la arbo, kaj planto kiu arbo interne de la arbaro.

344
00:28:04,040 --> 00:28:06,370
Jen ni havas rmforest.

345
00:28:06,370 --> 00:28:11,480
Similaj forigi arbo, kiu esence liberigis ĉiuj niaj arboj por ni,

346
00:28:11,480 --> 00:28:16,600
forigi arbaro volo liberaj ĉio enhavis en tiu arbaro.

347
00:28:16,600 --> 00:28:24,890
>> Se ni rigardas forest.c, ni atendis vidi almenaŭ 1 rmtree komandon en tie,

348
00:28:24,890 --> 00:28:30,090
ĉar al libera memoro en la arbaro, se arbaro havas arbojn en ĝi,

349
00:28:30,090 --> 00:28:32,930
tiam eventuale vi tuj devos forigi tiujn arbojn tro.

350
00:28:32,930 --> 00:28:41,020
Se ni rigardas forest.c, ni havas niajn mkforest, kiu estas kiel ni atendis.

351
00:28:41,020 --> 00:28:42,890
Ni malloc aĵoj.

352
00:28:42,890 --> 00:28:51,740
Ni pravalorizi la unua argumento en la arbaro kiel NULL ĉar ĝi estas malplena por komenci,

353
00:28:51,740 --> 00:29:05,940
tiam ni vidos fosilo, kiu revenas al la arbo kun la plej malalta pezo, la plej malalta ofteco,

354
00:29:05,940 --> 00:29:13,560
kaj poste liveras de tiu aparta nodo ke poentojn al tiu arbo kaj la sekva,

355
00:29:13,560 --> 00:29:16,760
tial ĝi prenas tiun el la ligitaj listo de la arbaro.

356
00:29:16,760 --> 00:29:24,510
Kaj tiam tie ni havas planton, kiu enmetas arbo en la ligitaj listo.

357
00:29:24,510 --> 00:29:29,960
Kio arbaro ne estas bele subtenas ĝin ordo por ni.

358
00:29:29,960 --> 00:29:37,910
Kaj poste fine, ni havas rmforest kaj, kiel atendis, ni havas rmtree pregxis tie.

359
00:29:46,650 --> 00:29:55,440
>> Rigardante la dissendo kodo ĝis nun, huffile.c estis probable per malproksime la plej malfacila por kompreni,

360
00:29:55,440 --> 00:29:59,990
dum la aliaj dosieroj mem estis sufiĉe simpla sekvi.

361
00:29:59,990 --> 00:30:03,090
Kun nia kono de punteros kaj kunligita lertaj kaj tia,

362
00:30:03,090 --> 00:30:04,860
ni povis sekvi sufiĉe bone.

363
00:30:04,860 --> 00:30:10,500
Sed ĉiuj ni bezonas vere certigi ke ni plene komprenas estas la. H dosieroj

364
00:30:10,500 --> 00:30:15,840
ĉar vi bezonas esti nomante tiuj funkcioj, traktante kun tiuj reveno valoroj,

365
00:30:15,840 --> 00:30:20,590
tiel certigi ke vi plene komprenis kion ago tuj por ludado

366
00:30:20,590 --> 00:30:24,290
kiam ajn vi nomas unu el tiuj funkcioj.

367
00:30:24,290 --> 00:30:33,020
Sed reale kompreni ene de ĝi ne estas sufiĉe necesa ĉar ni havas tiujn. H dosierojn.

368
00:30:35,170 --> 00:30:39,490
Ni havas 2 pli dosierojn lasis en nia dissendo-kodo.

369
00:30:39,490 --> 00:30:41,640
>> Ni rigardu dump.

370
00:30:41,640 --> 00:30:47,230
Enjxetos por lia komento tie prenas Huffman-kunpremita dosiero

371
00:30:47,230 --> 00:30:55,580
kaj tiam tradukas kaj renversas ĉiuj ties enhavo eksteren.

372
00:31:01,010 --> 00:31:04,260
Jen ni vidas ke ĝi estas nomante hfopen.

373
00:31:04,260 --> 00:31:10,770
Tio estas speco de spegulon al dosieron * enigo = fopen,

374
00:31:10,770 --> 00:31:13,500
kaj tiam vi pasos en la informo.

375
00:31:13,500 --> 00:31:18,240
Estas preskaŭ identa escepte anstataŭ dosieron * vi pasante en Huffile;

376
00:31:18,240 --> 00:31:22,030
anstataŭ fopen vi pasante en hfopen.

377
00:31:22,030 --> 00:31:29,280
Ĉi tie ni legas en la kaplinio unua, kiu estas speco de simila al kiel ni legas en la kaplinio

378
00:31:29,280 --> 00:31:33,580
por bitmap dosiero.

379
00:31:33,580 --> 00:31:38,000
Kion ni faras ĉi tie estas kontrolanta vidi ĉu la kaplinion informoj

380
00:31:38,000 --> 00:31:44,330
enhavas la dekstra magia nombro kiu indikas ke temas pri efektiva Huff dosiero,

381
00:31:44,330 --> 00:31:53,610
tiam ĉiuj el ĉi tiuj kontroloj por certigi ke la dosiero kiun ni malfermitaj estas reala huffed dosiero aŭ ne.

382
00:31:53,610 --> 00:32:05,330
Kion ĉi tio estas eligas la oftecojn de ĉiuj el la simboloj kiuj povas vidi

383
00:32:05,330 --> 00:32:09,790
ene de terminalo en grafika tablo.

384
00:32:09,790 --> 00:32:15,240
Ĉi tiu parto tuj estos utila.

385
00:32:15,240 --> 00:32:24,680
Ĝi havas iom kaj legas iom post iom en la variablo iom kaj poste presas ĝin.

386
00:32:28,220 --> 00:32:35,430
Do se mi estus nomi dump sur hth.bin, kiu estas la rezulto de huffing dosieron

387
00:32:35,430 --> 00:32:39,490
uzante la bastonon solvo, mi akirus ĉi.

388
00:32:39,490 --> 00:32:46,000
Ĝi estas elirigi ĉiuj tiuj signoj kaj poste meti la ofteco je kiu ili aperas.

389
00:32:46,000 --> 00:32:51,180
Se ni rigardas, la plejparto de ili estas _0s_ krom por tio: H, kiu aperas dufoje,

390
00:32:51,180 --> 00:32:54,820
kaj tiam T, kiu aperas unufoje.

391
00:32:54,820 --> 00:33:07,860
Kaj tiam tie ni havas la reala mesaĝo en _0s_ kaj _1s_.

392
00:33:07,860 --> 00:33:15,450
Se ni rigardas hth.txt, kiu estas supozeble la originala mesaĝo kiu huffed,

393
00:33:15,450 --> 00:33:22,490
ni atendas vidi iujn Hs kaj Ts tie.

394
00:33:22,490 --> 00:33:28,720
Specife, ni atendas por vidi nur 1 T kaj 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Jen ni estas en hth.txt. Ĝi ja havas HTH.

396
00:33:37,440 --> 00:33:41,270
Inkluzivita en tie, kvankam ni ne povas vidi gxin, estas linion karaktero.

397
00:33:41,270 --> 00:33:53,190
La Huff dosieron hth.bin ankaŭ kodi la linion karakteron tiel.

398
00:33:55,680 --> 00:34:01,330
Ĉi tie, ĉar ni scias ke la ordo estas HTH kaj poste linion,

399
00:34:01,330 --> 00:34:07,340
ni povas vidi ke probable la H estas reprezentita de nur sola 1

400
00:34:07,340 --> 00:34:17,120
kaj tiam la T estas probable 01 kaj tiam la sekvanta H estas 1, tiel

401
00:34:17,120 --> 00:34:21,139
kaj poste ni havas linion indikita de du _0s_.

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

403
00:34:26,530 --> 00:34:31,600
>> Kaj poste fine, ĉar ni pritraktas multnombraj. C kaj. H dosieroj,

404
00:34:31,600 --> 00:34:36,350
ni havos belan kompleksa argumento al la tradukilo,

405
00:34:36,350 --> 00:34:40,460
kaj tiel tie ni havas Makefile kiu faras dump por vi.

406
00:34:40,460 --> 00:34:47,070
Sed reale, vi devas iri farante vian propran puff.c dosiero.

407
00:34:47,070 --> 00:34:54,330
La Makefile reale ne traktas farante puff.c por vi.

408
00:34:54,330 --> 00:34:59,310
Ni lasante ke ĝis vi redakti la Makefile.

409
00:34:59,310 --> 00:35:05,930
Kiam vi eniros en komando kiel fari ĉiuj, ekzemple, ĝi faros cxion por vi.

410
00:35:05,930 --> 00:35:10,760
Bonvolu rigardi la ekzemplojn de Makefile el la pasinteco pset

411
00:35:10,760 --> 00:35:17,400
tiel kiel pafante de ĉi tiu por vidi kiel vi eble povos fari vian Puff dosieron

412
00:35:17,400 --> 00:35:20,260
per redaktado ĉi Makefile.

413
00:35:20,260 --> 00:35:22,730
Tio pri ĝi por nia dissendo-kodo.

414
00:35:22,730 --> 00:35:28,380
>> Iam ni alvenas tra tiu, tiam tie estas nur alia memorigo

415
00:35:28,380 --> 00:35:30,980
pri kiel ni tuj estos pritraktanta la Huffman nodoj.

416
00:35:30,980 --> 00:35:35,400
Ni ne tuj estos nomante ilin nodoj plu; ni tuj estos nomante ilin arboj

417
00:35:35,400 --> 00:35:39,260
kie ni tuj estos reprezenti liajn simbolo kun char,

418
00:35:39,260 --> 00:35:43,340
ilia ofteco, la nombro de okazajxoj, kun entjero.

419
00:35:43,340 --> 00:35:47,370
Ni uzas tion ĉar ĝi estas pli preciza ol kaleŝego.

420
00:35:47,370 --> 00:35:52,980
Kaj tiam ni havas alian sagon al la maldekstra infano kaj ankaŭ la dekstra infano.

421
00:35:52,980 --> 00:35:59,630
Al arbaro, kiel ni vidis, estas nur ligillisto de arboj.

422
00:35:59,630 --> 00:36:04,670
Fine, kiam ni konstruas nian Huff dosiero,

423
00:36:04,670 --> 00:36:07,580
ni volas nian arbaro enhavi nur 1 arbo -

424
00:36:07,580 --> 00:36:12,420
1 arbo, 1 radikon kun multnombraj infanoj.

425
00:36:12,420 --> 00:36:20,840
Antaŭe kiam ni nur faras nian Huffman arboj,

426
00:36:20,840 --> 00:36:25,360
ni komencis metante ĉiujn nodojn sur nia ekrano

427
00:36:25,360 --> 00:36:27,790
kaj dirante ni havos tiujn nodojn,

428
00:36:27,790 --> 00:36:32,920
eventuale ili tuj estos la folioj, kaj ĉi tiu estas lia simbolo, jen ilia ofteco.

429
00:36:32,920 --> 00:36:42,070
En nia arbaro, se ni nur havas 3 literoj, kiuj estas arbaraj de 3 arboj.

430
00:36:42,070 --> 00:36:45,150
Kaj poste kiam ni iru plu, kiam ni aldonas la unua patro,

431
00:36:45,150 --> 00:36:48,080
ni faris arbaro de 2 arboj.

432
00:36:48,080 --> 00:36:54,930
Ni forigis 2 el tiuj infanoj de nia arbaro kaj tiam anstataŭis ĝin per patro nodo

433
00:36:54,930 --> 00:36:58,820
kiu havis la 2 nodoj kiel infanoj.

434
00:36:58,820 --> 00:37:05,600
Kaj poste fine, nia lasta paŝo kun fari nian ekzemplon kun la mezuro, Bs, kaj C

435
00:37:05,600 --> 00:37:08,030
estus fari la fino patro,

436
00:37:08,030 --> 00:37:13,190
kaj tiel tiam kiu alportus nia tuta grafo de arboj en la arbaro al 1.

437
00:37:13,190 --> 00:37:18,140
Ĉu ĉiuj vidas, kiel vi starti evi multnombraj arboj en via arbaro

438
00:37:18,140 --> 00:37:22,520
kaj fini kun 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Kion ni bezonas fari por Puff?

440
00:37:28,110 --> 00:37:37,110
Kion ni bezonas fari estas certiĝi ke, kiel ĉiam, ili donas al ni la rajton tipo de enigo

441
00:37:37,110 --> 00:37:39,090
por ke ni povas efektive uzi la programon.

442
00:37:39,090 --> 00:37:43,130
En ĉi tiu kazo tuj esti donante nin post ilia unua komando-linia argumento

443
00:37:43,130 --> 00:37:53,440
2 pli: la dosiero kiu ni volas malkompaktigi kaj la eliro de la decompressed dosiero.

444
00:37:53,440 --> 00:38:00,410
Sed iam ni certigu ke ili pasas ni en la dekstra kvanton de valoroj,

445
00:38:00,410 --> 00:38:05,820
ni volas certigi ke la enigo estas Huff dosiero aŭ ne.

446
00:38:05,820 --> 00:38:10,420
Kaj poste iam ni garantias ke ĝi estas Huff dosiero, tiam ni volas konstrui nian arbon,

447
00:38:10,420 --> 00:38:20,940
konstrui la arbo tia, ke ĝi kongruas la arbo, ke la persono kiu sendis la mesaĝon konstruitaj.

448
00:38:20,940 --> 00:38:25,840
Tiam, post ni konstruas la arbo, tiam ni povas trakti la _0s_ kaj _1s_ ke ili pasis en,

449
00:38:25,840 --> 00:38:29,590
sekvi tiujn kune nian arbon ĉar ĝi estas identa,

450
00:38:29,590 --> 00:38:33,510
kaj poste skribu tiun mesaĝon ekstere, interpreti la bitoj denove en signoj.

451
00:38:33,510 --> 00:38:35,880
Kaj poste fine ĉar ni pritraktas punteros tie,

452
00:38:35,880 --> 00:38:38,110
ni volas certigi ke ni ne havas ajnan memoro fugoj

453
00:38:38,110 --> 00:38:41,330
kaj ke ni liberan ĉion.

454
00:38:42,820 --> 00:38:46,430
>> Certigante taŭga uzo estas malnova ĉapelo por ni nun.

455
00:38:46,430 --> 00:38:51,980
Ni prenu en enigo, kiu tuj estos la nomo de la dosiero al Puff,

456
00:38:51,980 --> 00:38:56,010
kaj poste ni specifi eligo,

457
00:38:56,010 --> 00:39:01,580
tial la nomo de la dosiero por la plenblovis eligo, kiu estos la teksta dosiero.

458
00:39:03,680 --> 00:39:08,820
Tio estas uzado. Kaj nun ni volas certigi ke la enmeto huffed aŭ ne.

459
00:39:08,820 --> 00:39:16,420
Pensante dorso, estis io en la dissendo kodo kiu povus helpi nin

460
00:39:16,420 --> 00:39:21,570
kun kompreni ĉu dosiero estas huffed aŭ ne?

461
00:39:21,570 --> 00:39:26,910
Estis informo en huffile.c pri la Huffeader.

462
00:39:26,910 --> 00:39:33,430
Ni scias ke ĉiu Huff dosiero havas Huffeader asociita kun ĝi kun magia nombro

463
00:39:33,430 --> 00:39:37,240
tiel kiel tabelo de la frekvencoj por ĉiu simbolo

464
00:39:37,240 --> 00:39:39,570
tiel kiel kontrolsumon.

465
00:39:39,570 --> 00:39:43,180
Ni scias tion, sed ni ankaŭ prenis travidi en dump.c,

466
00:39:43,180 --> 00:39:49,120
en kiu legis en Huff dosiero.

467
00:39:49,120 --> 00:39:53,990
Kaj tiel fari tion, ĝi devis kontroli ĉu ĝi vere estis huffed aŭ ne.

468
00:39:53,990 --> 00:40:03,380
Do eble ni povus uzi dump.c kiel strukturon por nia puff.c.

469
00:40:03,380 --> 00:40:12,680
Reen al pset 4 kiam ni havis la dosiero copy.c ke kopiita en RGB triopoj

470
00:40:12,680 --> 00:40:14,860
kaj ni interpretis ke por Whodunit kaj Regrandigi,

471
00:40:14,860 --> 00:40:20,390
simile, kion vi povus fari estas simple kuras la komandon kiel cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
kaj uzi iun el la kodo tie.

473
00:40:23,600 --> 00:40:28,210
Tamen, ĝi ne tuj estos tiel rekta de procezo

474
00:40:28,210 --> 00:40:33,010
por traduki vian dump.c en puff.c,

475
00:40:33,010 --> 00:40:36,160
sed almenaŭ donas vin ie komenci

476
00:40:36,160 --> 00:40:40,540
pri kiel certigi ke la enigo estas reale huffed aŭ ne

477
00:40:40,540 --> 00:40:43,240
tiel kiel kelkaj aliaj aĵoj.

478
00:40:45,930 --> 00:40:50,250
Ni certigis ĝusta uzo kaj certigis ke la enmeto huffed.

479
00:40:50,250 --> 00:40:53,570
Ĉiufoje ke ni faris kion ni faris nia propra eraro kontrolanta,

480
00:40:53,570 --> 00:41:01,520
tiel reveni kaj lasi la funkcio se iu fiasko okazas, se estas problemo.

481
00:41:01,520 --> 00:41:07,170
>> Nun kion ni volas fari estas konstrui la reala arbo.

482
00:41:08,840 --> 00:41:12,640
Se ni rigardas en Arbaro, estas 2 ĉefaj funkcioj

483
00:41:12,640 --> 00:41:15,800
ke ni tuj volas fariĝi tre konanta.

484
00:41:15,800 --> 00:41:23,870
Jen la Bulea funkcio planto kiu plantoj ne-0 ofteco arbo interne nia arbaro.

485
00:41:23,870 --> 00:41:29,250
Kaj do vi pasas en puntero al arbaro kaj puntero al arbo.

486
00:41:32,530 --> 00:41:40,340
Rapida demando: Kiom da arbaroj vi havas kiam vi konstruas Huffman arbo?

487
00:41:44,210 --> 00:41:46,650
Nia arbaro estas kiel niaj tolo, ĉu ne?

488
00:41:46,650 --> 00:41:50,800
Do ni nur havos 1 arbaro, sed ni tuj havos multnombraj arboj.

489
00:41:50,800 --> 00:41:57,590
Do antaŭ ol vi nomas planto, vi supozeble tuj volas fari vian arbaron.

490
00:41:57,590 --> 00:42:04,430
Tie estas komando por ke, se vi rigardas en forest.h pri kiel vi povas fari arbaro.

491
00:42:04,430 --> 00:42:09,270
Vi povas planti arbon. Ni scias kiel fari tion.

492
00:42:09,270 --> 00:42:11,590
Kaj tiam vi ankaŭ povas elekti arbon el la arbaro,

493
00:42:11,590 --> 00:42:17,540
forigo arbo kun la plej malalta pezo kaj donas al vi la puntero al tio.

494
00:42:17,540 --> 00:42:23,090
Pensante reen al kiam ni faris la ekzemploj ni mem,

495
00:42:23,090 --> 00:42:27,980
kiam ni desegni gxin, ni simple nur aldonis la ligilon.

496
00:42:27,980 --> 00:42:31,680
Sed tie anstataŭ nur aldonante la ligiloj,

497
00:42:31,680 --> 00:42:40,630
pensi pri tio pli kiel vi forigo 2 el tiuj nodoj kaj tiam anstataŭante ĝin per alia.

498
00:42:40,630 --> 00:42:44,200
Por esprimi, ke en terminoj de pluki kaj planti,

499
00:42:44,200 --> 00:42:48,840
vi pluki 2 arboj kaj tiam plantante alia arbo

500
00:42:48,840 --> 00:42:54,060
kiu havas tiujn 2 arboj kiujn vi elektis kiel infanoj.

501
00:42:57,950 --> 00:43:05,280
Konstrui Huffman la arbo, vi povas legi en la simboloj kaj frekvencoj por

502
00:43:05,280 --> 00:43:10,790
ĉar la Huffeader donas ke al vi,

503
00:43:10,790 --> 00:43:14,250
donas tabelo de la frekvencoj.

504
00:43:14,250 --> 00:43:19,660
Do vi povas antaŭeniri kaj simple ignoras nenion kun la 0 en ĝi

505
00:43:19,660 --> 00:43:23,760
ĉar ni ne volas 256 folioj ĉe la fino de ĝi.

506
00:43:23,760 --> 00:43:27,960
Ni nur volas ke la nombro de folioj, kiuj estas gravuloj

507
00:43:27,960 --> 00:43:31,600
kiuj efektive uzata en la dosiero.

508
00:43:31,600 --> 00:43:37,590
Vi povas legi en tiuj simboloj, kaj ĉiu el tiuj simboloj, kiuj havas ne-0 frekvencoj,

509
00:43:37,590 --> 00:43:40,440
tiuj tuj estos arboj.

510
00:43:40,440 --> 00:43:45,990
Kion vi povas fari estas ĉiufoje kiam vi legis en ne-0 ofteco simbolo,

511
00:43:45,990 --> 00:43:50,660
vi povas planti tiu arbo en la arbaro.

512
00:43:50,660 --> 00:43:56,620
Kiam vi plantos la arbojn en la arbaro, vi povas aliĝi tiuj arboj kiel gefratoj,

513
00:43:56,620 --> 00:44:01,130
do tuj revenis al planti kaj pluki kie vi prenas 2 kaj tiam planto 1,

514
00:44:01,130 --> 00:44:05,820
kie tiu 1 kiu vi planto estas la patro de la 2 infanoj, kiun vi prenis.

515
00:44:05,820 --> 00:44:11,160
Do tiam via fina rezulto estas tuj estos sola arbo en via arbaro.

516
00:44:16,180 --> 00:44:18,170
Tiel estas kiel vi konstruos viajn arbo.

517
00:44:18,170 --> 00:44:21,850
>> Estas pluraj aferoj kiuj povus erari ĉi tie

518
00:44:21,850 --> 00:44:26,580
ĉar ni pritraktas fari novajn arbojn kaj pritraktas punteros kaj aĵoj tiel.

519
00:44:26,580 --> 00:44:30,450
Antaŭ kiam ni pritraktas punteros,

520
00:44:30,450 --> 00:44:36,580
ĉiufoje kiam ni malloc'd ni volis certigi ke ĝi ne revenos al ni NULL puntero valoro.

521
00:44:36,580 --> 00:44:42,770
Do en pluraj paŝoj ene de ĉi tiu procezo ne tuj estos pluraj kazoj

522
00:44:42,770 --> 00:44:45,920
kie estas via programo povus maltrafi.

523
00:44:45,920 --> 00:44:51,310
Kion vi volas fari estas vi volas certigi ke vi manipuli tiujn erarojn,

524
00:44:51,310 --> 00:44:54,580
kaj en la spec diras manipuli ilin gracie,

525
00:44:54,580 --> 00:45:00,280
tiel kiel presi mesaĝon al la uzanto diris al ili kial la programo devas quit

526
00:45:00,280 --> 00:45:03,050
kaj poste rapide forlasis ĝin.

527
00:45:03,050 --> 00:45:09,490
Por fari tion eraro uzado, memoru, ke vi volas kontroli ĝin

528
00:45:09,490 --> 00:45:12,160
ĉiun solan fojon ke povus esti fiasko.

529
00:45:12,160 --> 00:45:14,660
Ĉiu sola fojo ke vi faras nova puntero

530
00:45:14,660 --> 00:45:17,040
vi volas certigi ke tio sukcesis.

531
00:45:17,040 --> 00:45:20,320
Antaŭ kio ni uzas por fari estas fari novan puntero kaj malloc ĝin,

532
00:45:20,320 --> 00:45:22,380
kaj tiam ni devus kontroli ĉu tiu puntero estas NULL.

533
00:45:22,380 --> 00:45:25,670
Do tuj estos iuj kazoj, kie vi povas simple fari tion,

534
00:45:25,670 --> 00:45:28,610
sed kelkfoje vi fakte nomi funkcio

535
00:45:28,610 --> 00:45:33,100
kaj ene de tiu funkcio, tio estas la ke tio faras la mallocing.

536
00:45:33,100 --> 00:45:39,110
En tiu kazo, se ni retrorigardas al kelkaj el la funkcioj ene de la kodo,

537
00:45:39,110 --> 00:45:42,260
kelkaj el ili estas Bulea funkcioj.

538
00:45:42,260 --> 00:45:48,480
En la abstrakta kazo se ni havas Bulea funkcio nomita foo,

539
00:45:48,480 --> 00:45:54,580
esence, ni povas supozi ke, krom fari kion ajn foo faras,

540
00:45:54,580 --> 00:45:57,210
ĉar ĝi estas Bulea funkcio, ĝi revenas vera aŭ malvera -

541
00:45:57,210 --> 00:46:01,300
vera se sukcesa, malvera se ne.

542
00:46:01,300 --> 00:46:06,270
Do ni volas kontroli ĉu la reveno valoro de foo estas vera aŭ malvera.

543
00:46:06,270 --> 00:46:10,400
Se ĝi estas falsa, tio signifas ke ni tuj volas presi ian mesaĝon

544
00:46:10,400 --> 00:46:14,390
kaj tiam lasis la programo.

545
00:46:14,390 --> 00:46:18,530
Kion ni volas fari estas kontroli la reveno valoro de foo.

546
00:46:18,530 --> 00:46:23,310
Se foo revenas malvera, tiam ni scios, ke ni renkontis ian eraron

547
00:46:23,310 --> 00:46:25,110
kaj ni bezonas quit nia programo.

548
00:46:25,110 --> 00:46:35,600
Maniero por fari ĉi estas havi kondiĉo kie la reala funkcio mem estas via stato.

549
00:46:35,600 --> 00:46:39,320
Diru foo prenas en x.

550
00:46:39,320 --> 00:46:43,390
Ni povas havi kiel kondiĉon se (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Esence, tio signifas, se fine de ekzekuti foo ĝi revenas vera,

552
00:46:50,900 --> 00:46:57,390
tiam ni povas fari ĉi tion ĉar la funkcio devas taksi foo

553
00:46:57,390 --> 00:47:00,500
por taksi la tuta kondiĉo.

554
00:47:00,500 --> 00:47:06,500
Tial jen kiel vi povas fari ion se la funkcio redonas vera kaj estas sukcesa.

555
00:47:06,500 --> 00:47:11,800
Sed kiam vi estas eraro kontrolanta, vi nur volas lasi se via funkcio redonas falsaj.

556
00:47:11,800 --> 00:47:16,090
Kion vi povus fari estas simple aldoni == malvera aŭ nur aldoni bang antaŭ ĝin

557
00:47:16,090 --> 00:47:21,010
kaj tiam vi havos if (! foo).

558
00:47:21,010 --> 00:47:29,540
Ene de tiu korpo de tiu kondiĉo vi havus ĉiujn eraro uzado,

559
00:47:29,540 --> 00:47:36,940
tiel kiel, "Ne povis krei tiun arbon" kaj tiam revenu 1 aŭ io kiel tio.

560
00:47:36,940 --> 00:47:43,340
Kion tio faras, tamen, estas ke kvankam foo revenis falsaj -

561
00:47:43,340 --> 00:47:46,980
Diru foo revenas vera.

562
00:47:46,980 --> 00:47:51,060
Tiam vi ne devas nomi foo denove. Tio estas komuna eraro.

563
00:47:51,060 --> 00:47:54,730
Ĉar estis en via kondiĉo, ĝi estas jam taksis,

564
00:47:54,730 --> 00:47:59,430
tiel vi jam havas la rezulton, se vi uzas fari arbo aŭ iu simila

565
00:47:59,430 --> 00:48:01,840
aŭ planto aŭ fosilo aŭ iu.

566
00:48:01,840 --> 00:48:07,460
Ĝi jam havas tiun valoron. Ĝi estas jam ekzekutita.

567
00:48:07,460 --> 00:48:10,730
Do ĝi estas utila por uzi Bulea funkcioj kiel la kondiĉo

568
00:48:10,730 --> 00:48:13,890
ĉar ĉu vi vere ekzekuti la korpon de la ciklo,

569
00:48:13,890 --> 00:48:18,030
ekzekutas la funkcio ĉiuokaze.

570
00:48:22,070 --> 00:48:27,330
>> Nia dua lasta paŝo estas skribi la mesaĝon al la dosiero.

571
00:48:27,330 --> 00:48:33,070
Iam ni konstruu la Huffman arbo, tiam skribi la mesaĝon al la dosiero estas bela simpla.

572
00:48:33,070 --> 00:48:39,260
Estas bela simpla nun nur sekvi la _0s_ kaj _1s_.

573
00:48:39,260 --> 00:48:45,480
Kaj tiel per konvencio ni scias ke en Huffman arbo la _0s_ indikas forlasis

574
00:48:45,480 --> 00:48:48,360
kaj la 1s indiki pravas.

575
00:48:48,360 --> 00:48:53,540
Se do vi legis en iom post iom, ĉiufoje ke vi ricevas 0

576
00:48:53,540 --> 00:48:59,100
vi sekvu la maldekstra branĉo, kaj tiam ĉiu tempo vi legis en 1

577
00:48:59,100 --> 00:49:02,100
vi tuj sekvu la dekstra branĉo.

578
00:49:02,100 --> 00:49:07,570
Kaj tiam vi tuj pluiri ĝis ili batis folio

579
00:49:07,570 --> 00:49:11,550
ĉar la folioj tuj estos fine de la branĉoj.

580
00:49:11,550 --> 00:49:16,870
Kiel ni povas distingi, ĉu ni batis folio aŭ ne?

581
00:49:19,800 --> 00:49:21,690
Ni diris ĝin antaŭe.

582
00:49:21,690 --> 00:49:24,040
[Studento] Se la punteros estas NULL. >> Jes.

583
00:49:24,040 --> 00:49:32,220
Ni povas diri se ni batis folio se la punteros al ambaŭ la maldekstra kaj dekstra arboj estas NULL.

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

585
00:49:34,110 --> 00:49:40,320
Ni scias, ke ni volas legi en iom post iom en niajn Huff dosiero.

586
00:49:43,870 --> 00:49:51,220
Kiel ni vidis antaŭe en dump.c, kion ili faris estas ili legis en iom post iom en la Huff dosieron

587
00:49:51,220 --> 00:49:54,560
kaj nur presas el kio tiuj bitoj estis.

588
00:49:54,560 --> 00:49:58,430
Ni ne tuj estos fari tion. Ni tuj faros iun kiu estas iom pli kompleksa.

589
00:49:58,430 --> 00:50:03,620
Sed kion ni povas fari estas ni povas preni ke iom da kodo kiu legas en la bito.

590
00:50:03,620 --> 00:50:10,250
Jen ni havas la entjera iom reprezentantaj la nuna iom, ke ni estas en.

591
00:50:10,250 --> 00:50:15,520
Tiu prizorgas ripetanta ĉiuj bitoj en la dosieron ĝis vi batis la fino de la dosiero.

592
00:50:15,520 --> 00:50:21,270
Bazita sur tiu, tiam vi tuj volas havi ian iterator

593
00:50:21,270 --> 00:50:26,760
tra viaj arbo.

594
00:50:26,760 --> 00:50:31,460
Kaj poste bazita sur ĉu la bito estas 0 aŭ 1,

595
00:50:31,460 --> 00:50:36,920
vi tuj volas ĉu movi ke iterator al la maldekstra aŭ movi ĝin al la dekstra

596
00:50:36,920 --> 00:50:44,080
tuta vojo ĝis vi batis folio, do la tuta vojo ĝis tiu nodo, ke vi estas en

597
00:50:44,080 --> 00:50:48,260
ne indikas plu nodoj.

598
00:50:48,260 --> 00:50:54,300
Kial ni povas fari tio kun Huffman dosiero sed ne Morsa kodo?

599
00:50:54,300 --> 00:50:56,610
Ĉar en Morsa kodo ekzistas iom da ambigueco.

600
00:50:56,610 --> 00:51:04,440
Ni povis esti kiel, oh atendas, ni batis leteron kune la vojon, do eble tio estas nia letero,

601
00:51:04,440 --> 00:51:08,150
dum se ni daŭre nur iom pli longe, tiam ni estus batis alia litero.

602
00:51:08,150 --> 00:51:13,110
Sed tio ne estas okazos en Huffman kodigo,

603
00:51:13,110 --> 00:51:17,540
do ni povas ripozi certigis, ke la sola maniero por ke ni tuj batis gravulo

604
00:51:17,540 --> 00:51:23,480
estas se tiu nodo la maldekstra kaj dekstra infanoj estas NULL.

605
00:51:28,280 --> 00:51:32,350
>> Fine, ni volas liberigi nian tutan memoron.

606
00:51:32,350 --> 00:51:37,420
Ni volas ambaŭ fermi la Huff dosiero ni estis kontraktanta kun

607
00:51:37,420 --> 00:51:41,940
tiel kiel forigi ĉiujn arbojn en nia arbaro.

608
00:51:41,940 --> 00:51:46,470
Bazita sur via efektivigo, vi probable tuj volas nomi forigi arbaro

609
00:51:46,470 --> 00:51:49,780
anstataŭ reale iras tra ĉiu el la arboj mem.

610
00:51:49,780 --> 00:51:53,430
Sed se vi faris neniun temporal arboj, vi volas liberigi tion.

611
00:51:53,430 --> 00:51:59,060
Vi konas vian kodo bona, do vi scias, kie vi atribuante memoro.

612
00:51:59,060 --> 00:52:04,330
Kaj do se vi eniros, starti per eĉ Kontrolo F'ing por malloc,

613
00:52:04,330 --> 00:52:08,330
vidante kiam vi malloc kaj certigante ke vi liberigi ĉiujn, ke

614
00:52:08,330 --> 00:52:10,190
sed tiam nur irante tra via kodo,

615
00:52:10,190 --> 00:52:14,260
kompreni, kie vi povus esti atribuitaj memoro.

616
00:52:14,260 --> 00:52:21,340
Kutime vi povus simple diri: "Je la fino de dosiero Mi nur tuj eltiros arbaro sur mia arbaro",

617
00:52:21,340 --> 00:52:23,850
do esence certe ke memoro, libera, ke,

618
00:52:23,850 --> 00:52:28,310
"Kaj tiam mi ankaŭ tuj fermi la dosieron kaj tiam mia programo tuj forlasis."

619
00:52:28,310 --> 00:52:33,810
Sed estas ke la sola tempo kiun via programo fermas?

620
00:52:33,810 --> 00:52:37,880
Ne, ĉar kelkfoje povus esti eraro, ke okazis.

621
00:52:37,880 --> 00:52:42,080
Eble ni ne povis malfermi dosieron aŭ ni ne povis fari alian arbon

622
00:52:42,080 --> 00:52:49,340
aŭ ia eraro okazis en la memoro atribuo procezo kaj tiel revenis NULL.

623
00:52:49,340 --> 00:52:56,710
Eraro okazis kaj tiam ni revenis kaj quit.

624
00:52:56,710 --> 00:53:02,040
Do tiam vi volas certigi ke iu ajn ebla tempo ke via programo povas quit,

625
00:53:02,040 --> 00:53:06,980
vi volas liberigi ĉiujn via memoro tie.

626
00:53:06,980 --> 00:53:13,370
Ĝi estas ne nur tuj estos en la fino de la ĉefa funkcio kiu vi quit vian kodon.

627
00:53:13,370 --> 00:53:20,780
Vi volas retrorigardas al ĉiu okazo, ke via kodo potenciale povus reveni antaŭtempe

628
00:53:20,780 --> 00:53:25,070
kaj poste liberaj ajn memoro havas sencon.

629
00:53:25,070 --> 00:53:30,830
Say vi vokis fari arbaro kaj kiu revenis falsaj.

630
00:53:30,830 --> 00:53:34,230
Tiam vi verŝajne ne bezonos forigi vian arbaro

631
00:53:34,230 --> 00:53:37,080
ĉar vi ne havas arbaro ankoraŭ.

632
00:53:37,080 --> 00:53:42,130
Sed ĉe ĉiu punkto en la kodo, kie vi povus reveni antaŭtempe

633
00:53:42,130 --> 00:53:46,160
vi volas certigi ke vi liberigi ajna ebla memoro.

634
00:53:46,160 --> 00:53:50,020
>> Do kiam ni pritraktas liberigi memoron kaj havante potencial fugoj,

635
00:53:50,020 --> 00:53:55,440
ni volas ne nur uzi nian juĝon kaj nia logiko

636
00:53:55,440 --> 00:54:01,850
sed ankaŭ uzi Valgrind por determini ĉu ni liberigxis ĉiuj niaj memoro adekvate aŭ ne.

637
00:54:01,850 --> 00:54:09,460
Vi povas aŭ kuri Valgrind sur Puff kaj tiam vi devas ankaŭ pasi ĝin

638
00:54:09,460 --> 00:54:14,020
dekstre numero de komand-linio argumentoj por Valgrind.

639
00:54:14,020 --> 00:54:18,100
Vi povas ruli tion, sed la eligo estas iom enigmaj.

640
00:54:18,100 --> 00:54:21,630
Ni alvenas iom uzata por ĝin per Speller, sed ni ankoraŭ bezonas iom pli da helpo,

641
00:54:21,630 --> 00:54:26,450
do tiam kurante ĝin kun kelkaj pli flagoj kiel la fugo-check = plena,

642
00:54:26,450 --> 00:54:32,040
ke verŝajne al ni iun pli helpema eligo sur Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Tiam alia utila tip kiam vi elpurigante estas la malsamoj komando.

644
00:54:39,040 --> 00:54:48,520
Vi povas aliri la bastonon de efektivigo de Huff, kuri, ke sur teksto-dosiero,

645
00:54:48,520 --> 00:54:55,400
kaj tiam Eligo ĝin al duuma dosiero, duuma Huff dosiero, por esti specifa.

646
00:54:55,400 --> 00:54:59,440
Tiam se vi kuros vian propran nubeto en tiu duuma dosiero,

647
00:54:59,440 --> 00:55:03,950
tiam ideale, via outputted teksta dosiero tuj estos identa

648
00:55:03,950 --> 00:55:08,200
al la originalo, kiun vi pasis in

649
00:55:08,200 --> 00:55:15,150
Jen Mi uzas hth.txt kiel la ekzemplo, kaj tio estas la raportis en via spec.

650
00:55:15,150 --> 00:55:21,040
Tio laŭvorte nur HTH kaj poste novan linion.

651
00:55:21,040 --> 00:55:30,970
Sed definitive sentas senpagaj kaj vi certe kuraĝigis uzi plu ekzemploj

652
00:55:30,970 --> 00:55:32,620
por via teksta dosiero.

653
00:55:32,620 --> 00:55:38,110
>> Vi povas eĉ preni ŝancon eble kunpremante kaj poste decompressing

654
00:55:38,110 --> 00:55:41,600
kelkaj el la dosieroj kiujn vi uzis en Speller kiel Milito kaj Paco

655
00:55:41,600 --> 00:55:46,710
aŭ Jane Austen aŭ io simila - kiu estus speco de cool - aŭ Austin Powers,

656
00:55:46,710 --> 00:55:51,880
speco de kontraktanta kun pli grandaj dosieroj ĉar ni ne malsupreniru, por ĝin

657
00:55:51,880 --> 00:55:55,590
se ni uzas la sekvanta ilo tie, ls-l.

658
00:55:55,590 --> 00:56:01,150
Ni uzis por LS, kiu esence listas ĉiuj enhavoj en nia aktuala dosierujo.

659
00:56:01,150 --> 00:56:07,860
Pasante en la flago-l reale montras la grandecon de tiuj dosieroj.

660
00:56:07,860 --> 00:56:12,690
Se vi iras tra la pset spec, ĝi reale marŝas vin tra kreante la duuma dosiero,

661
00:56:12,690 --> 00:56:16,590
de huffing ĝin, kaj vi vidos ke por tre malgrandaj dosieroj

662
00:56:16,590 --> 00:56:23,910
la spaco kosto de kunpremante ĝin kaj traduki ĉiujn tiun informon

663
00:56:23,910 --> 00:56:26,980
de ĉiuj frekvencoj kaj aliaj similaj ke kompensas la reala profito

664
00:56:26,980 --> 00:56:30,000
de kunpremante la dosieron en la unua loko.

665
00:56:30,000 --> 00:56:37,450
Sed se vi kuros ĝin sur iun plu tekstaj dosieroj, tiam vi eble vidas, ke vi komencu akiri profiton

666
00:56:37,450 --> 00:56:40,930
en kunpremante tiujn dosierojn.

667
00:56:40,930 --> 00:56:46,210
>> Kaj poste fine, ni havas niajn malnovajn pal GDB, kiu definitive tuj venos en oportuna ankaŭ.

668
00:56:48,360 --> 00:56:55,320
>> Ĉu ni havas demandojn sur Huff arboj aŭ la procezo eble de farante la arboj

669
00:56:55,320 --> 00:56:58,590
aŭ ajna alia demandojn sur Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okay. Mi restos ĉirkaŭrigardis por iom.

671
00:57:02,570 --> 00:57:06,570
>> Dankon, al ĉiuj. Tio estis Walkthrough 6. Kaj bona sorto.

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