1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Solisyon - Set Pwoblèm 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Inivèsite Harvard]

3
00:00:04,810 --> 00:00:07,240
[Sa a se CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hello, tout moun, epi byenveni nan solisyon 6: Huff'n feyte.

5
00:00:12,180 --> 00:00:17,440
Nan feyte Huff'n ki sa nou ap fè yo pral fè fas ak yon dosye konprese Huffman

6
00:00:17,440 --> 00:00:20,740
ak Lè sa a, aletman li tounen moute, se konsa dekonprese li,

7
00:00:20,740 --> 00:00:25,810
pou nou ka tradui soti nan ki 0s ak 1S voye nan itilizatè a nou

8
00:00:25,810 --> 00:00:30,660
epi konvèti li tounen nan tèks orijinal la.

9
00:00:30,660 --> 00:00:34,360
Pset 6 a pwal trè fre paske w ap ale nan wè kèk nan zouti yo

10
00:00:34,360 --> 00:00:41,730
ke ou te itilize nan pset 4 ak pset 5 ak kalite konbine yo nan 1 konsèp trè pwòp

11
00:00:41,730 --> 00:00:43,830
lè ou vini nan panse sou sa.

12
00:00:43,830 --> 00:00:50,110
>> Epitou, joui, pset 4 ak 5 yo te pi psets yo solid ki nou te gen yo ofri.

13
00:00:50,110 --> 00:00:53,950
Se konsa, soti nan kounye a, nou gen sa a pset 1 plis nan C,

14
00:00:53,950 --> 00:00:56,480
ak Lè sa a, apre ke nou se sou pwogramasyon entènèt.

15
00:00:56,480 --> 00:01:02,310
Se konsa, felisite tèt nou pou jwenn plis pase bòs la pi di nan CS50.

16
00:01:03,630 --> 00:01:09,760
>> Deplase sou pou feyte Huff'n, bwat zouti pou nou an pou sa a pset pwal gen Huffman pye bwa,

17
00:01:09,760 --> 00:01:14,700
Se konsa konprann pa sèlman ki jan binè pyebwa travay, men tou espesyalman Huffman pye bwa,

18
00:01:14,700 --> 00:01:16,240
ki jan yo ap konstwi.

19
00:01:16,240 --> 00:01:20,210
Lè sa a, nou pral gen yon anpil nan kòd distribisyon nan sa a pset,

20
00:01:20,210 --> 00:01:22,480
epi n ap vin wè ki aktyèlman kèk nan kòd la

21
00:01:22,480 --> 00:01:24,670
nou pa ka kapab konprann konplètman ankò,

22
00:01:24,670 --> 00:01:30,080
ak sa moun yo pral. dosye yo c, men Lè sa a, akonpaye yo. dosye h

23
00:01:30,080 --> 00:01:34,300
pral ban nou ase konpreyansyon ke nou bezwen pou nou konnen ki jan moun ki fonksyon travay

24
00:01:34,300 --> 00:01:38,100
oswa omwen sa yo ap sipoze fè - entrain yo epi yo sorti -

25
00:01:38,100 --> 00:01:40,760
menm si nou pa konnen sa k ap pase nan ti bwat la nwa

26
00:01:40,760 --> 00:01:44,090
oswa ou pa konprann sa k ap pase nan ti bwat la nwa nan.

27
00:01:44,090 --> 00:01:49,400
Lè sa a, finalman, kòm dabitid, nou ap fè fas ak estrikti done nouvo,

28
00:01:49,400 --> 00:01:51,840
kalite espesifik nan nœuds ki pwen a sèten bagay,

29
00:01:51,840 --> 00:01:56,080
e konsa isit la gen yon plim ak papye pa sèlman pou pwosesis la konsepsyon

30
00:01:56,080 --> 00:01:58,470
ak ki lè ou ap eseye figi konnen kouman pset ou yo ta dwe travay

31
00:01:58,470 --> 00:02:00,520
men tou pandan debogaj.

32
00:02:00,520 --> 00:02:06,140
Ou ka gen gdb ansanm ak plim ou ak papye pandan w ap pran desann sa ki valè yo ye a,

33
00:02:06,140 --> 00:02:09,320
kote flèch ou yo ap lonje dwèt, ak bagay sa yo tankou sa.

34
00:02:09,320 --> 00:02:13,720
>> Premye kite pou yo gade nan Huffman pyebwa.

35
00:02:13,720 --> 00:02:19,600
Pye bwa yo se pye bwa Huffman binè, sa vle di ke chak ne sèlman gen 2 timoun yo.

36
00:02:19,600 --> 00:02:24,870
Nan Huffman pye bwa karakteristik la se ke valè yo pi souvan

37
00:02:24,870 --> 00:02:27,140
yo reprezante nan Bits yo gen mwens.

38
00:02:27,140 --> 00:02:32,690
Nou te wè nan egzanp konferans nan Morse kòd, ki kalite consolidée kèk lèt.

39
00:02:32,690 --> 00:02:38,030
Si w ap eseye tradui yon A oswa E yon, pou egzanp,

40
00:02:38,030 --> 00:02:43,940
w ap tradui ki souvan, se konsa olye pou yo gen yo sèvi ak seri a plen nan Bits

41
00:02:43,940 --> 00:02:48,640
afekte pou sa kalite abityèl done, ou konpresyon li desann nan mwens,

42
00:02:48,640 --> 00:02:53,730
ak Lè sa a, lèt sa yo ki ap reprezante mwens souvan yo reprezante ak pi long Bits

43
00:02:53,730 --> 00:02:59,840
paske ou kapab peye ke lè ou peze soti fwekans yo ke lèt sa yo parèt.

44
00:02:59,840 --> 00:03:03,020
Nou gen lide nan menm isit la nan Huffman pye bwa

45
00:03:03,020 --> 00:03:12,360
kote nou yo ap fè yon chèn, yon kalite chemen pou li ale nan karaktè yo ki sèten.

46
00:03:12,360 --> 00:03:14,470
Lè sa a, karaktè yo ki gen frekans ki pi

47
00:03:14,470 --> 00:03:17,940
yo pral reprezante ak Bits yo gen mwens.

48
00:03:17,940 --> 00:03:22,020
>> Fason ke ou konstwi yon pyebwa Huffman

49
00:03:22,020 --> 00:03:27,430
se lè w mete tout nan karaktè yo ki parèt nan tèks la

50
00:03:27,430 --> 00:03:30,630
ak kalkile frekans yo, konbyen fwa yo parèt.

51
00:03:30,630 --> 00:03:33,880
Sa a te swa gen yon konte nan konbyen fwa lèt sa yo parèt

52
00:03:33,880 --> 00:03:40,270
oswa petèt yon pousantaj nan soti nan tout karaktè yo ki jan anpil chak moun parèt.

53
00:03:40,270 --> 00:03:44,270
Se konsa, sa ou fè se yon fwa ou gen tout ki soti mappé,

54
00:03:44,270 --> 00:03:49,060
Lè sa a, ou gade pou 2 fwekans yo pi ba a epi Lè sa a, rantre nan yo tankou frè ak sè

55
00:03:49,060 --> 00:03:55,660
Lè sa a, kote ne nan paran yo gen yon frekans ki se sòm total la nan 2 timoun li yo.

56
00:03:55,660 --> 00:04:00,870
Lè sa a, ou pa konvansyon di ke ne gòch la,

57
00:04:00,870 --> 00:04:03,770
ou swiv ki pa swiv branch nan 0,

58
00:04:03,770 --> 00:04:08,140
ak Lè sa a, ne la rightmost se branch nan 1.

59
00:04:08,140 --> 00:04:16,040
Kòm nou te wè nan Morse kòd, gotcha nan youn te ke si ou te gen jis yon BEEP ak BEEP la

60
00:04:16,040 --> 00:04:18,120
li te Limit.

61
00:04:18,120 --> 00:04:22,430
Li te kapab swa dwe 1 lèt oswa li ka yon sekans nan 2 lèt yo.

62
00:04:22,430 --> 00:04:27,790
Se konsa, sa ki Huffman pye bwa fè a se paske pa nati nan karaktè yo ki

63
00:04:27,790 --> 00:04:34,140
oswa karaktè final nou an ke yo te vrè nœuds ki sot pase yo sou branch la -

64
00:04:34,140 --> 00:04:39,300
nou al gade nan sa yo kòm fèy - pa vèrtu nan ke gen pa kapab gen nenpòt ki anbigwite

65
00:04:39,300 --> 00:04:45,160
an tèm de ki lèt w ap eseye programme ak seri a nan Bits

66
00:04:45,160 --> 00:04:50,670
paske okenn kote ansanm Bits yo ki reprezante 1 lèt

67
00:04:50,670 --> 00:04:55,960
ou pral rankontre yon lòt lèt antye, e gen pa yo pral nenpòt konfizyon la.

68
00:04:55,960 --> 00:04:58,430
Men, nou pral ale nan egzanp ke ou nèg ka aktyèlman wè ke

69
00:04:58,430 --> 00:05:02,120
olye pou yo jis nou di ou ke sa a, se vre.

70
00:05:02,120 --> 00:05:06,390
>> Se pou yo gade nan yon egzanp senp nan yon pyebwa Huffman.

71
00:05:06,390 --> 00:05:09,380
Mwen gen yon fisèl isit la ke se 12 karaktè nan longè.

72
00:05:09,380 --> 00:05:14,010
Mwen gen 4 Kòm, 6 B, ak 2 CS.

73
00:05:14,010 --> 00:05:17,270
Premye etap mwen ta dwe konte.

74
00:05:17,270 --> 00:05:20,760
Konbyen fwa Yon parèt? Li parèt 4 fwa nan fil la.

75
00:05:20,760 --> 00:05:25,060
B parèt 6 fwa, ak C parèt 2 fwa.

76
00:05:25,060 --> 00:05:28,970
Natirèlman, mwen pral di mwen sèvi ak B pi souvan,

77
00:05:28,970 --> 00:05:35,970
Se konsa, mwen vle reprezante B avèk nimewo a mwens nan Bits, nimewo a mwens nan 0s ak 1S.

78
00:05:35,970 --> 00:05:42,600
Lè sa a, mwen tou ale nan atann C rive nan mande pou kantite lajan nan pi fò nan 0s ak 1S kòm byen.

79
00:05:42,600 --> 00:05:48,550
Premye sa mwen te fè isit la se mwen mete yo nan lòd moute an tèm de frekans.

80
00:05:48,550 --> 00:05:52,710
Nou wè ke C a ak A a, sa yo se 2 nou an ki pi ba frekans.

81
00:05:52,710 --> 00:06:00,290
Nou kreye yon ne paran, e ke ne paran pa gen yon lèt ki asosye ak li,

82
00:06:00,290 --> 00:06:05,070
men li fè sa gen yon frekans, ki se sòm total la.

83
00:06:05,070 --> 00:06:08,780
Sòm la vin tounen 2 + 4, ki se 6.

84
00:06:08,780 --> 00:06:10,800
Lè sa a, nou swiv branch lan kite.

85
00:06:10,800 --> 00:06:14,970
Si nou tout nou te nan ki ne, 6, Lè sa a, nou ta swiv 0 pou li ale nan C

86
00:06:14,970 --> 00:06:17,450
ak Lè sa a, 1 pou li ale nan A.

87
00:06:17,450 --> 00:06:20,300
Se konsa, kounye a nou gen 2 nœuds.

88
00:06:20,300 --> 00:06:23,920
Nou gen valè a 6 ak Lè sa a, nou menm tou nou gen yon lòt ne ak valè a 6.

89
00:06:23,920 --> 00:06:28,550
Se konsa, sa yo 2 yo se pa sèlman 2 ki pi ba a, men tou jis 2 a ki rete,

90
00:06:28,550 --> 00:06:33,820
pou nou antre nan sa yo pa yon lòt paran, ak sòm total la ke yo te 12.

91
00:06:33,820 --> 00:06:36,300
Se konsa, isit la nou gen pyebwa Huffman nou

92
00:06:36,300 --> 00:06:40,020
kote pou li ale nan B, ki ta ka jis pou ti jan nan 1

93
00:06:40,020 --> 00:06:45,430
ak Lè sa a, pou li ale nan Yon nou ta gen 01 ak Lè sa a, C ki gen 00.

94
00:06:45,430 --> 00:06:51,300
Se konsa, isit la nou wè ke nou ap fondamantalman ki reprezante sa yo charaktèr ak swa Bits 1 oswa 2

95
00:06:51,300 --> 00:06:55,160
kote B a, kòm prevwa, gen omwen nan.

96
00:06:55,160 --> 00:07:01,730
Lè sa a, nou te espere C rive gen pi plis nan yo, men depi li nan tankou yon ti Huffman pyebwa,

97
00:07:01,730 --> 00:07:06,020
Lè sa a, Yon lan tou se reprezante pa 2 Bits kòm opoze a yon kote nan mitan an.

98
00:07:07,820 --> 00:07:11,070
>> Jis ale sou yon lòt egzanp senp nan pye bwa a Huffman,

99
00:07:11,070 --> 00:07:19,570
di ou gen fisèl la "Hello."

100
00:07:19,570 --> 00:07:25,360
Ki sa ou fè se premye fwa ou ta di konbyen fwa H parèt nan sa a?

101
00:07:25,360 --> 00:07:34,200
H parèt yon sèl fwa ak Lè sa a, e parèt yon sèl fwa ak Lè sa a, nou gen l parèt de fwa

102
00:07:34,200 --> 00:07:36,580
ak o parèt yon fwa.

103
00:07:36,580 --> 00:07:44,310
Se konsa, Lè sa a, nou espere ki lèt yo dwe reprezante pa genyen pi piti kantite Bits?

104
00:07:44,310 --> 00:07:47,450
[Elèv] l. >> L. Yeah. l ki dwat.

105
00:07:47,450 --> 00:07:50,730
Nou atann pou l yo dwe reprezante pa genyen pi piti kantite Bits

106
00:07:50,730 --> 00:07:55,890
paske l se itilize pi nan fisèl la "Hello."

107
00:07:55,890 --> 00:08:04,280
Sa mwen ap pral fè koulye a, se trase soti sa yo nœuds.

108
00:08:04,280 --> 00:08:15,580
Mwen gen 1, ki se H, ak Lè sa a, yon lòt 1, ki se e, ak Lè sa a, yon 1, ki se o -

109
00:08:15,580 --> 00:08:23,410
kounye a mwen mete yo nan lòd - ak Lè sa a, 2, ki se l.

110
00:08:23,410 --> 00:08:32,799
Lè sa a, mwen di wout la ke mwen bati yon pyebwa Huffman se jwenn nœuds yo 2 ak fwekans yo pi piti

111
00:08:32,799 --> 00:08:38,010
epi fè yo frè ak sè pa kreye yon ne paran yo.

112
00:08:38,010 --> 00:08:41,850
Isit la nou gen 3 nœuds ak frekans ki pi ba a. Yo ap tout 1.

113
00:08:41,850 --> 00:08:50,620
Se konsa, isit la nou chwazi ki youn nou pral konekte premye.

114
00:08:50,620 --> 00:08:54,850
Se pou nou di mwen chwazi H la ak e a.

115
00:08:54,850 --> 00:09:01,150
Sòm la 1 + 1 se 2, men sa a ne pa gen yon lèt ki asosye ak li.

116
00:09:01,150 --> 00:09:04,440
Li jis kenbe valè a.

117
00:09:04,440 --> 00:09:10,950
Koulye a, nou gade nan 2 pwochen fwekans yo ki pi ba.

118
00:09:10,950 --> 00:09:15,590
Sa a 2 ak 1. Yo ki te kapab swa nan sa yo 2, men mwen pral chwazi yon sèl sa a.

119
00:09:15,590 --> 00:09:18,800
Sòm la se 3.

120
00:09:18,800 --> 00:09:26,410
Lè sa a, finalman, mwen sèlman gen 2 bò gòch, se konsa Lè sa a, ki vin 5.

121
00:09:26,410 --> 00:09:32,010
Lè sa a, isit la, kòm espere, si mwen ranpli nan kodaj la pou sa,

122
00:09:32,010 --> 00:09:37,480
1S yo toujou branch nan dwa ak 0s yo se youn nan bò gòch.

123
00:09:37,480 --> 00:09:45,880
Lè sa a, nou gen l reprezante pa jis ti jan 1 ak Lè sa a, o la pa 2

124
00:09:45,880 --> 00:09:52,360
ak Lè sa a, e nan pa 2 epi Lè sa a, H a tonbe desann nan 3 miyèt moso.

125
00:09:52,360 --> 00:09:59,750
Se konsa, ou ka transmèt mesaj sa a "Alo" olye pou yo aktyèlman lè l sèvi avèk karaktè yo

126
00:09:59,750 --> 00:10:02,760
pa jis 0s ak 1S.

127
00:10:02,760 --> 00:10:07,910
Sepandan, sonje ke nan ka plizyè nou te gen relasyon ak frekans nou an.

128
00:10:07,910 --> 00:10:11,900
Nou te ka genyen swa ansanm H la ak o an premye petèt.

129
00:10:11,900 --> 00:10:15,730
Oswa Lè sa a, pita sou lè nou te lan l reprezante pa 2

130
00:10:15,730 --> 00:10:19,410
kòm byen ke ansanm nan yon sèl reprezante pa 2, nou te ka genyen lye swa youn.

131
00:10:19,410 --> 00:10:23,630
>> Se konsa, lè ou voye 0s ak 1, ki aktyèlman pa garanti a

132
00:10:23,630 --> 00:10:27,090
ki benefisyè a ka rive li mesaj ou a dwa koupe baton an

133
00:10:27,090 --> 00:10:30,490
paske yo pa ta ka konnen ki desizyon ou te fè.

134
00:10:30,490 --> 00:10:34,920
Se konsa, lè nou ap fè fas ak konpresyon Huffman,

135
00:10:34,920 --> 00:10:40,090
yon jan kanmenm nou oblije di benefisyè a nan mesaj nou an ki jan nou deside -

136
00:10:40,090 --> 00:10:43,470
Yo bezwen konnen kèk kalite enfòmasyon anplis

137
00:10:43,470 --> 00:10:46,580
nan adisyon a mesaj la konprese.

138
00:10:46,580 --> 00:10:51,490
Yo bezwen konprann sa pyebwa sa a aktyèlman sanble,

139
00:10:51,490 --> 00:10:55,450
ki jan nou aktyèlman te fè desizyon sa yo.

140
00:10:55,450 --> 00:10:59,100
>> Isit la nou te jis ap fè kèk egzanp ki baze sou konte aktyèl la,

141
00:10:59,100 --> 00:11:01,550
men pafwa ou ka genyen tou yon pyebwa Huffman

142
00:11:01,550 --> 00:11:05,760
ki baze sou frekans lan nan ki lèt parèt, epi li pwosesis la egzak menm.

143
00:11:05,760 --> 00:11:09,090
Men mwen ap eksprime li an tèm de pousantaj oswa fraksyon yon,

144
00:11:09,090 --> 00:11:11,290
e konsa isit la egzak menm bagay la.

145
00:11:11,290 --> 00:11:15,300
Mwen jwenn 2 ki pi ba, rapò kantite yo, 2 nan pwochen ki pi ba, sòm la yo,

146
00:11:15,300 --> 00:11:19,390
jouk tan mwen genyen yon pye bwa plen.

147
00:11:19,390 --> 00:11:23,610
Menm si nou ta ka fè li swa fason, lè nou ap fè fas ak pousantaj,

148
00:11:23,610 --> 00:11:27,760
sa vle di nou ap divize bagay sa yo ak fè fas ak desimal ou pito flote

149
00:11:27,760 --> 00:11:30,900
si nou ap panse sou done estrikti nan yon tèt.

150
00:11:30,900 --> 00:11:32,540
Ki sa nou konnen sou cha?

151
00:11:32,540 --> 00:11:35,180
Ki sa ki nan yon komen pwoblèm lè nou ap fè fas ak cha?

152
00:11:35,180 --> 00:11:38,600
[Elèv] enpresizyon aritmetik. >> Yeah. Enpresizyon.

153
00:11:38,600 --> 00:11:43,760
Paske nan enpresizyon pwen k ap flote, pou sa a pset pou nou asire

154
00:11:43,760 --> 00:11:49,450
ke nou pa pèdi nenpòt valè, Lè sa a, nou ap aktyèlman yo pral fè fas ak konte a.

155
00:11:49,450 --> 00:11:54,880
Se konsa, si ou te panse a yon ne Huffman, si ou gade tounen nan estrikti a isit la,

156
00:11:54,880 --> 00:12:01,740
si ou gade nan sa yo vèt li gen yon frekans ki asosye ak li

157
00:12:01,740 --> 00:12:08,760
kòm byen ke li lonje dwèt nan yon ne a gòch li yo kòm osi byen yon ne a dwat li yo.

158
00:12:08,760 --> 00:12:13,970
Lè sa a, yo menm ki wouj la tou gen yon karaktè ki asosye ak yo.

159
00:12:13,970 --> 00:12:18,900
Nou pa pwal fè sa ki apa pou paran yo ak Lè sa a, nœuds yo final la,

160
00:12:18,900 --> 00:12:23,680
ki nou al gade nan kòm fèy yo, men pito sa yo pral jis yo gen valè nil.

161
00:12:23,680 --> 00:12:31,050
Pou chak ne n ap gen yon karaktè, senbòl la ki ki ne reprezante,

162
00:12:31,050 --> 00:12:40,490
Lè sa a, yon frekans kòm osi byen yon konsèy ak pitit li yo bò gòch kòm byen ke pitit dwa li yo.

163
00:12:40,490 --> 00:12:45,680
Fèy yo, ki se nan pati anba a trè, ta yo te genyen tou endikasyon ne

164
00:12:45,680 --> 00:12:49,550
sou bò goch yo ak sou bò dwat yo, men yo depi valè sa yo yo pa lonje dwèt nœuds reyèl,

165
00:12:49,550 --> 00:12:53,970
sa ki ta valè yo ta dwe ye? >> [Elèv] nil. >> Nil. Egzakteman.

166
00:12:53,970 --> 00:12:58,430
Isit la nan yon egzanp sou kouman ou ta ka reprezante frekans lan nan flote,

167
00:12:58,430 --> 00:13:02,130
men nou ap pral fè fas ak li avèk nonm antye yo,

168
00:13:02,130 --> 00:13:06,780
se konsa tout mwen te fè se chanje kalite a done a.

169
00:13:06,780 --> 00:13:09,700
>> Se pou nou ale nan yon ti jan plis nan yon egzanp konplèks.

170
00:13:09,700 --> 00:13:13,360
Men, kounye a ke nou te fè sa ki senp, li la jis pwosesis la menm.

171
00:13:13,360 --> 00:13:20,290
Ou jwenn 2 ki pi ba fwekans yo, rapò kantite fwekans yo

172
00:13:20,290 --> 00:13:22,450
ak sa a, se frekans nan nouvo nan ne paran ou a,

173
00:13:22,450 --> 00:13:29,310
ki lè sa a lonje dwèt sou bò goch li yo ak branch nan 0 ak dwa a ak branch nan 1.

174
00:13:29,310 --> 00:13:34,200
Si nou gen fisèl la "Sa a se cs50," Lè sa a, nou konte konbyen fwa se T mansyone,

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

176
00:13:38,420 --> 00:13:42,010
Lè sa a, sa mwen te fè isit la se ak nœuds yo wouj mwen jis te plante,

177
00:13:42,010 --> 00:13:48,530
M 'te di mwen pral gen sa yo karaktè evantyèlman nan fon an nan pyebwa m' yo.

178
00:13:48,530 --> 00:13:51,740
Moun sa yo ki pwal gen tout fèy yo.

179
00:13:51,740 --> 00:13:58,200
Lè sa a, sa mwen te fè se mwen Ranje yo nan frekans nan Ascending lòd,

180
00:13:58,200 --> 00:14:02,950
ak sa a se aktyèlman fason la ki kòd la pset fè li

181
00:14:02,950 --> 00:14:07,550
se li kalite li pa frekans ak Lè sa a, lòd avèk lèt ​​alfabè.

182
00:14:07,550 --> 00:14:13,870
Se konsa, li gen nimewo yo premye ak Lè sa a, lòd avèk lèt ​​alfabè pa frekans lan.

183
00:14:13,870 --> 00:14:18,520
Lè sa a, ki sa mwen ta fè se mwen ta jwenn ki pi ba a 2. Sa a 0 ak 5.

184
00:14:18,520 --> 00:14:22,390
Mwen ta rapò kantite yo, epi ki nan 2. Apre sa, mwen ta kontinye, jwenn pwochen 2 ki pi ba a.

185
00:14:22,390 --> 00:14:26,100
Moun sa yo se 1S an de, ak Lè sa a, sa yo vin 2 kòm byen.

186
00:14:26,100 --> 00:14:31,570
Koulye a mwen konnen pwochen etap mwen yo pral rantre nan nimewo ki pi ba a,

187
00:14:31,570 --> 00:14:41,380
ki se T a, 1 an, ak Lè sa a, chwazi youn nan nœuds yo ki gen 2 kòm frekans lan.

188
00:14:41,380 --> 00:14:44,560
Se konsa, isit la nou gen 3 opsyon.

189
00:14:44,560 --> 00:14:47,980
Ki sa ki mwen pral fè pou glise nan se jis vizyèlman ordonne yo pou ou

190
00:14:47,980 --> 00:14:51,790
pou ke ou ka wè ki jan mwen bati li.

191
00:14:51,790 --> 00:14:59,040
Ki sa ki kòd la ak kòd distribisyon ou a pral nan fè ta dwe enskri nan youn nan T

192
00:14:59,040 --> 00:15:01,410
ak ne a 0 ak 5.

193
00:15:01,410 --> 00:15:05,060
Se konsa, Lè sa a, ki montan lajan nan 3, ak Lè sa a, nou kontinye pwosesis la.

194
00:15:05,060 --> 00:15:08,660
2 a ak 2 a kounye a se ki pi ba a, se konsa Lè sa a, sa yo sòm a 4.

195
00:15:08,660 --> 00:15:12,560
Tout moun swiv byen lwen tèlman? Oke.

196
00:15:12,560 --> 00:15:16,410
Lè sa a, apre ke nou gen 3 an ak 3 an ki bezwen ajoute leve,

197
00:15:16,410 --> 00:15:21,650
Se konsa ankò mwen jis oblije chanje li pou ke ou ka wè vizyèlman konsa ke li pa jwenn twò lèd.

198
00:15:21,650 --> 00:15:25,740
Lè sa a, nou gen yon 6, epi Lè sa a, etap final nou an, se kounye a ke nou gen sèlman 2 nœuds

199
00:15:25,740 --> 00:15:30,440
nou rapò kantite moun ki fè rasin nan pyebwa nou an, ki se 10.

200
00:15:30,440 --> 00:15:34,100
Ak nimewo a 10 fè sans paske chak ne reprezante,

201
00:15:34,100 --> 00:15:40,750
valè yo, nimewo frekans yo, te konbyen fwa yo parèt nan fisèl la,

202
00:15:40,750 --> 00:15:46,350
ak Lè sa a, nou gen 5 karaktè nan fisèl nou an, se konsa ki fè sans.

203
00:15:48,060 --> 00:15:52,320
Si nou gade moute nan ki jan nou ta aktyèlman programme li,

204
00:15:52,320 --> 00:15:56,580
kòm espere, mwen la ak s la, ki parèt pi souvan nan

205
00:15:56,580 --> 00:16:01,350
yo reprezante pa kantite mwens nan miyèt moso.

206
00:16:03,660 --> 00:16:05,660
>> Fè atansyon isit la.

207
00:16:05,660 --> 00:16:09,780
Nan Huffman pye bwa ka a aktyèlman zafè.

208
00:16:09,780 --> 00:16:13,670
Yon S majuskul se diferan pase yon s miniskil.

209
00:16:13,670 --> 00:16:21,260
Si nou te gen "Sa a se CS50" ak lèt ​​majiskil, lè sa a yo nan miniskil ta sèlman parèt de fwa,

210
00:16:21,260 --> 00:16:27,120
ta dwe yon ne ak 2 kòm valè li yo, ak Lè sa a, majuskul S ta ka sèlman yon fwa.

211
00:16:27,120 --> 00:16:33,440
Se konsa, Lè sa a, pye bwa ou ta ka chanje estrikti paske ou gen aktyèlman gen yon fèy siplemantè isit la.

212
00:16:33,440 --> 00:16:36,900
Men, sòm total la ta dwe toujou 10.

213
00:16:36,900 --> 00:16:39,570
Sa a ki sa nou ap aktyèlman yo pral rele kontwòl la,

214
00:16:39,570 --> 00:16:44,060
adisyon a nan tout konte yo.

215
00:16:46,010 --> 00:16:50,990
>> Kounye a ke nou te kouvri Huffman pye bwa, nou ka plonje nan feyte Huff'n, pset la.

216
00:16:50,990 --> 00:16:52,900
Nou pwal kòmanse avèk yon seksyon nan kesyon,

217
00:16:52,900 --> 00:16:57,990
ak sa a ki pral fè ou jwenn abitye ak pye bwa binè ak kouman yo opere alantou ke:

218
00:16:57,990 --> 00:17:03,230
desen nœuds, kreye pwòp ou a tipedèf struct pou yon ne,

219
00:17:03,230 --> 00:17:07,230
ak wè kijan ou ta ka insert nan yon pyebwa binè, youn ki nan Ranje,

220
00:17:07,230 --> 00:17:09,050
Travelers li, epi bagay sa yo tankou sa.

221
00:17:09,050 --> 00:17:14,560
Konesans sa a se definitivman pral ede ou lè ou plonje nan pòsyon nan feyte Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Nan edisyon an estanda nan pset a, travay ou a se fè aplike feyte,

224
00:17:26,329 --> 00:17:30,240
ak nan vèsyon an aker travay ou a se fè aplike Huff.

225
00:17:30,240 --> 00:17:38,490
Ki sa ki Huff fè se li pran tèks ak Lè sa a, li tradui l 'nan 0s a ak 1,

226
00:17:38,490 --> 00:17:41,990
Se konsa pwosesis ki nou te fè sa pi wo a kote nou konte fwekans yo

227
00:17:41,990 --> 00:17:50,970
ak Lè sa a, te fè pye bwa a ak Lè sa a, te di, "Kouman pou mwen jwenn T?"

228
00:17:50,970 --> 00:17:54,840
T ap reprezante pa 100, bagay sa yo tankou sa,

229
00:17:54,840 --> 00:17:58,860
ak Lè sa a, Huff ta pran tèks la ak Lè sa a, pwodiksyon ki binè.

230
00:17:58,860 --> 00:18:04,920
Men tou paske nou konnen ke nou vle pèmèt benefisyè nou an mesaj la

231
00:18:04,920 --> 00:18:11,790
rkree egzak pyebwa a menm, li tou gen ladan enfòmasyon sou konte yo frekans.

232
00:18:11,790 --> 00:18:17,980
Lè sa a, ak feyte nou yo bay yon dosye binè nan 0s ak 1S

233
00:18:17,980 --> 00:18:21,740
yo ak ba yo tou enfòmasyon sou fwekans yo.

234
00:18:21,740 --> 00:18:26,740
Nou tradui tout nan tout sa yo tounen 0s ak 1S nan mesaj orijinal la ki te,

235
00:18:26,740 --> 00:18:29,350
se konsa n ap dekonprese sa.

236
00:18:29,350 --> 00:18:36,450
Si ou ap fè edisyon an estanda, ou pa bezwen aplike Huff,

237
00:18:36,450 --> 00:18:39,290
se konsa Lè sa a, ou ka jis sèvi ak aplikasyon an anplwaye nan Huff.

238
00:18:39,290 --> 00:18:42,080
Gen enstriksyon nan espèk a sou ki jan fè sa.

239
00:18:42,080 --> 00:18:48,780
Ou ka kouri aplikasyon an anplwaye nan Huff sou yon dosye tèks sèten

240
00:18:48,780 --> 00:18:53,270
ak Lè sa a, sèvi ak ke randman kòm opinyon ou nan soufle.

241
00:18:53,270 --> 00:18:59,330
>> Kòm mwen mansyone anvan, nou gen yon anpil nan kòd distribisyon pou yon sèl sa a.

242
00:18:59,330 --> 00:19:01,810
Mwen pral kòmanse ale atravè li.

243
00:19:01,810 --> 00:19:04,400
Mwen pral pase pifò tan an sou la. Dosye h

244
00:19:04,400 --> 00:19:07,660
paske se nan. dosye yo c, paske nou gen h la.

245
00:19:07,660 --> 00:19:11,650
ak ki bay nou ak prototip yo nan fonksyon yo,

246
00:19:11,650 --> 00:19:15,520
nou pa totalman bezwen konprann egzakteman -

247
00:19:15,520 --> 00:19:20,280
Si ou pa konprann ki sa k ap pase nan. Dosye yo c, Lè sa a, pa enkyete twòp,

248
00:19:20,280 --> 00:19:23,600
men definitivman eseye pran yon gade paske li ta ka bay kèk sijesyon

249
00:19:23,600 --> 00:19:29,220
epi li itil nan jwenn itilize lekti kòd lòt moun.

250
00:19:38,940 --> 00:19:48,270
>> Gade nan huffile.h, nan kòmantè yo li deklare yon kouch abstraction pou Huffman-kode dosye.

251
00:19:48,270 --> 00:20:01,660
Si nou desann, nou wè ki di ke gen yon maksimòm de 256 senbòl ki nou ta ka bezwen kòd pou.

252
00:20:01,660 --> 00:20:05,480
Sa gen ladan tout lèt nan alfabè a - majuskul ak miniskil -

253
00:20:05,480 --> 00:20:08,250
ak Lè sa a, senbòl ak nimewo, elatriye

254
00:20:08,250 --> 00:20:11,930
Lè sa a, isit la nou gen yon nimewo majik idantifye yon dosye Huffman-kode.

255
00:20:11,930 --> 00:20:15,890
Nan yon kòd Huffman yo pwal santi yo gen yon nimewo majik sèten

256
00:20:15,890 --> 00:20:18,560
ki asosye ak header la.

257
00:20:18,560 --> 00:20:21,110
Sa a ta ka sanble jis nimewo yon o aza majik,

258
00:20:21,110 --> 00:20:27,160
Men, si ou aktyèlman tradui l 'nan ASCII, lè sa a li aktyèlman eple soti Huff.

259
00:20:27,160 --> 00:20:34,290
Isit la nou gen yon struct pou yon dosye Huffman-ankode.

260
00:20:34,290 --> 00:20:39,670
Genyen nan tout nan karakteristik sa yo ki asosye avèk yon dosye Huff.

261
00:20:39,670 --> 00:20:47,080
Lè sa a, desann isit la nou gen header la pou yon dosye Huff, se konsa nou rele li Huffeader

262
00:20:47,080 --> 00:20:50,810
olye pou yo ajoute h siplemantè a paske li son menm bagay la tou de tout fason.

263
00:20:50,810 --> 00:20:52,720
Bèl.

264
00:20:52,720 --> 00:20:57,790
Nou gen yon nimewo majik asosye ak li.

265
00:20:57,790 --> 00:21:09,040
Si li nan yon vrè Huff dosye, li te pral fè nimewo a moute pi wo a, yon sèl sa a majik.

266
00:21:09,040 --> 00:21:14,720
Lè sa a, li pral gen yon etalaj.

267
00:21:14,720 --> 00:21:18,750
Se konsa, pou chak senbòl, ki gen 256,

268
00:21:18,750 --> 00:21:24,760
li pral fè yon lis ki sa frekans lan nan tout sa yo senbòl yo nan dosye a Huff.

269
00:21:24,760 --> 00:21:28,090
Lè sa a, finalman, nou gen yon kontwòl pou fwekans yo,

270
00:21:28,090 --> 00:21:32,160
ki ta dwe sòm total la nan tout sa yo frekans.

271
00:21:32,160 --> 00:21:36,520
Se konsa, se sa ki yon Huffeader se.

272
00:21:36,520 --> 00:21:44,600
Lè sa a, nou gen kèk fonksyon ki retounen ti jan nan pwochen nan dosye a Huff

273
00:21:44,600 --> 00:21:52,580
kòm byen ke ekri yon ti jan nan dosye a Huff, ak Lè sa a, sa a fonksyon isit la, hfclose,

274
00:21:52,580 --> 00:21:54,650
ki aktyèlman fèmen dosye a Huff.

275
00:21:54,650 --> 00:21:57,290
Anvan, nou te fè fas ak tou dwat jis fkloz,

276
00:21:57,290 --> 00:22:01,190
Men, lè ou gen yon dosye Huff, olye pou yo fclosing li

277
00:22:01,190 --> 00:22:06,080
ki sa w ap aktyèlman pral fè se hfclose ak hfopen li.

278
00:22:06,080 --> 00:22:13,220
Moun sa yo se fonksyon espesifik nan dosye yo Huff ke nou ap pral fè fas ak.

279
00:22:13,220 --> 00:22:19,230
Lè sa a, isit la nou li nan header a ak Lè sa a, ekri header la.

280
00:22:19,230 --> 00:22:25,700
>> Jis pa lekti. H dosye a nou kapab kalite ka resevwa yon sans de sa ki yon dosye Huff ta kapab,

281
00:22:25,700 --> 00:22:32,480
sa ki karakteristik li gen, san yo pa aktyèlman ale nan huffile.c a,

282
00:22:32,480 --> 00:22:36,750
ki, si nou plonje nan, a pwal yon ti jan plis konplèks.

283
00:22:36,750 --> 00:22:41,270
Li te gen tout nan dosye a mwen / O isit la ki gen rapò ak pwent.

284
00:22:41,270 --> 00:22:48,010
Isit la nou wè ke lè nou rele hfread, pou egzanp, li la toujou fè fas ak frèd.

285
00:22:48,010 --> 00:22:53,050
Nou pa resevwa debarase de sa yo fonksyon antyèman, men nou ap voye sa yo li dwe te pran swen nan

286
00:22:53,050 --> 00:22:59,760
andedan dosye a Huff olye pou yo fè tout sa a li tèt nou.

287
00:22:59,760 --> 00:23:02,300
Ou ka santi lib yo analysis nan sa a si w ap kirye

288
00:23:02,300 --> 00:23:08,410
epi ale epi kale kouch a tounen yon ti jan.

289
00:23:20,650 --> 00:23:24,060
>> Dosye a pwochen ke nou ap pral gade se tree.h.

290
00:23:24,060 --> 00:23:30,210
Anvan nan solisyon an glisad nou te di nou espere yon ne Huffman

291
00:23:30,210 --> 00:23:32,960
epi nou te fè yon ne struct tipedèf.

292
00:23:32,960 --> 00:23:38,360
Nou atann pou li genyen yon senbòl, frekans yon, ak Lè sa a, 2 zetwal ne.

293
00:23:38,360 --> 00:23:41,870
Nan ka sa a sa n ap fè se sa a se esansyèlman menm bagay la tou

294
00:23:41,870 --> 00:23:46,880
eksepte olye pou yo ne nou pral rele yo pyebwa yo.

295
00:23:48,790 --> 00:23:56,760
Nou gen yon fonksyon ki lè w rele fè pyebwa li retounen ou yon konsèy pyebwa.

296
00:23:56,760 --> 00:24:03,450
Retounen nan ortograf, lè ou te konn fè yon ne nouvo

297
00:24:03,450 --> 00:24:11,410
ou te di ne * nouvo mo = malok (sizof) ak bagay sa yo tankou sa.

298
00:24:11,410 --> 00:24:17,510
Fondamantalman, mktree yo pral fè fas ak ki pou ou.

299
00:24:17,510 --> 00:24:20,990
Menm jan tou, lè ou vle retire yon pyebwa,

300
00:24:20,990 --> 00:24:24,810
pou ki nan esansyèlman libere pyebwa sa a lè w ap fè ak li,

301
00:24:24,810 --> 00:24:33,790
olye pou yo fòmèlman rele gratis sou sa, w ap aktyèlman jis ale nan sèvi avèk fonksyon an rmtree

302
00:24:33,790 --> 00:24:40,360
ki kote ou pase nan konsèy la ak sa yo ki pye bwa yo epi Lè sa a, tree.c pral pran swen nan ke pou ou.

303
00:24:40,360 --> 00:24:42,490
>> Nou gade nan tree.c.

304
00:24:42,490 --> 00:24:47,240
Nou atann pou fonksyon yo menm eksepte wè aplikasyon sa a tou.

305
00:24:47,240 --> 00:24:57,720
Kòm nou espere, lè w rele mktree li mallocs gwosè a nan yon pye bwa nan yon konsèy,

306
00:24:57,720 --> 00:25:03,190
inisyalizasyon tout valè yo nan valè a nil, se konsa 0s oswa NULLs,

307
00:25:03,190 --> 00:25:08,280
ak Lè sa a, retounen konsèy la ak sa yo ki pyebwa ke ou te jis malloc'd ba ou.

308
00:25:08,280 --> 00:25:13,340
Isit la lè ou rele retire pye bwa li premye fè asire w ke ou pa ap doub libere.

309
00:25:13,340 --> 00:25:18,320
Li fè asire w ke ou gen aktyèlman yon pye bwa ki ou vle yo retire.

310
00:25:18,320 --> 00:25:23,330
Isit la paske yon pye bwa gen ladan tou timoun li yo,

311
00:25:23,330 --> 00:25:29,560
ki sa sa a fè se li recursive rele retire pye bwa nan ne an gòch nan pye bwa a

312
00:25:29,560 --> 00:25:31,650
kòm byen ke ne a dwat.

313
00:25:31,650 --> 00:25:37,790
Anvan li libere paran an, li bezwen yo libere timoun yo kòm byen.

314
00:25:37,790 --> 00:25:42,770
Paran tou se ka ranplase ak rasin.

315
00:25:42,770 --> 00:25:46,500
Premye paran an tout tan, se konsa tankou gwo-gran-gran gwo granpapa a-

316
00:25:46,500 --> 00:25:52,130
oswa pyebwa grann, premye nou dwe libere desann nivo yo an premye.

317
00:25:52,130 --> 00:25:58,490
Se konsa, Traverse jouk anba a, gratis sa yo, ak Lè sa a, vin tounen moute, gratis sa yo, elatriye

318
00:26:00,400 --> 00:26:02,210
Se konsa, sa a, se pye bwa.

319
00:26:02,210 --> 00:26:04,240
>> Koulye a, nou gade nan forè.

320
00:26:04,240 --> 00:26:09,860
Forest a se kote ou mete tout Huffman pye bwa ou an.

321
00:26:09,860 --> 00:26:12,910
Li nan ki di ke nou pwal gen yon bagay yo rele yon konplo

322
00:26:12,910 --> 00:26:22,320
ki gen ladan yon konsèy nan yon pyebwa kòm osi byen yon konsèy nan yon konplo yo rele pwochen.

323
00:26:22,320 --> 00:26:28,480
Ki sa ki fè sa ki estrikti sa a kalite gade tankou?

324
00:26:29,870 --> 00:26:32,490
Li kalite di li sou la.

325
00:26:34,640 --> 00:26:36,700
Dwa sou isit la.

326
00:26:37,340 --> 00:26:39,170
Yon lis lye.

327
00:26:39,170 --> 00:26:44,590
Nou wè ke lè nou gen yon konplo se tankou yon lis lye nan kav.

328
00:26:44,590 --> 00:26:53,020
Yon forè defini kòm yon lis lye nan kav,

329
00:26:53,020 --> 00:26:58,100
e konsa estrikti a nan forè se nou ap jis pral gen yon konsèy trase premye nou

330
00:26:58,100 --> 00:27:02,740
e ke konplo a gen yon pye bwa nan li ou pito lonje dwèt nan yon pyebwa

331
00:27:02,740 --> 00:27:06,190
ak Lè sa a, pwen trase nan pwochen, se konsa sou ak pou fè.

332
00:27:06,190 --> 00:27:11,100
Pou fè yon forè nou rele mkforest.

333
00:27:11,100 --> 00:27:14,930
Lè sa a, nou gen kèk fonksyon trè itil isit la.

334
00:27:14,930 --> 00:27:23,240
Nou gen ranmase kote ou pase nan yon forè ak Lè sa a, valè a retounen se yon * Tree,

335
00:27:23,240 --> 00:27:25,210
yon konsèy nan yon pyebwa.

336
00:27:25,210 --> 00:27:29,370
Ki sa ki chwazi pral fè se li pral ale nan forè a ke w ap lonje dwèt

337
00:27:29,370 --> 00:27:35,240
Lè sa a, retire yon pye bwa ak frekans ki pi ba a soti nan ki forè

338
00:27:35,240 --> 00:27:38,330
ak Lè sa a, ba ou konsèy la ak sa yo ki pyebwa.

339
00:27:38,330 --> 00:27:43,030
Yon fwa ou rele chwazi, pyebwa a pa pral egziste nan forè a ankò,

340
00:27:43,030 --> 00:27:48,550
men valè a retounen se konsèy la ak sa yo ki pyebwa.

341
00:27:48,550 --> 00:27:50,730
Lè sa a, ou gen plant.

342
00:27:50,730 --> 00:27:57,420
Depi ke ou pase nan yon konsèy nan yon pye bwa ki gen yon frekans ki pa 0,

343
00:27:57,420 --> 00:28:04,040
sa plant ap fè se li pral pran forè a, pran pye bwa a, ak plant ki anndan pyebwa ki nan forè an.

344
00:28:04,040 --> 00:28:06,370
Isit la nou gen rmforest.

345
00:28:06,370 --> 00:28:11,480
Menm jan ak retire pye bwa, ki fondamantalman libere tout pyebwa nou yo pou nou,

346
00:28:11,480 --> 00:28:16,600
retire forè pral gratis tout bagay ki genyen nan ke forè.

347
00:28:16,600 --> 00:28:24,890
>> Si nou gade nan forest.c, nou pral espere wè omwen 1 rmtree lòd nan la,

348
00:28:24,890 --> 00:28:30,090
paske gratis memwa nan forè a si yon forè gen pye bwa nan li,

349
00:28:30,090 --> 00:28:32,930
Lè sa a, evantyèlman w ap ale nan gen yo retire sa yo pyebwa tou.

350
00:28:32,930 --> 00:28:41,020
Si nou gade nan forest.c, nou gen mkforest nou an, ki se kòm nou espere.

351
00:28:41,020 --> 00:28:42,890
Nou malok bagay sa yo.

352
00:28:42,890 --> 00:28:51,740
Nou inisyalize trase nan premye nan forè a kòm nil paske li nan vid yo kòmanse avèk yo,

353
00:28:51,740 --> 00:29:05,940
Lè sa a, nou wè chwazi, ki retounen pyebwa a ak pwa ki pi ba a, frekans ki pi ba a,

354
00:29:05,940 --> 00:29:13,560
ak Lè sa a, vin debarase m de ki ne patikilye ki pwen ak sa yo ki pye bwa yo epi youn nan pwochen,

355
00:29:13,560 --> 00:29:16,760
Se konsa li pran ki soti nan lis la lye nan forè a.

356
00:29:16,760 --> 00:29:24,510
Lè sa a, isit la nou gen plant yo, ki mete anndan yon pye bwa nan lis la lye.

357
00:29:24,510 --> 00:29:29,960
Ki sa ki forè se li joliman kenbe li Ranje pou nou.

358
00:29:29,960 --> 00:29:37,910
Lè sa a, finalman, nou gen rmforest, epi, kòm espere, nou gen rmtree rele la.

359
00:29:46,650 --> 00:29:55,440
>> Gade nan kòd la distribisyon twò lwen, huffile.c te pwobableman pa lwen pi di a yo konprann,

360
00:29:55,440 --> 00:29:59,990
Lè nou konsidere ke dosye yo lòt tèt yo te trè senp yo swiv.

361
00:29:59,990 --> 00:30:03,090
Ki gen konesans nou nan pwent e li bay lis lye ak sa yo,

362
00:30:03,090 --> 00:30:04,860
nou te kapab swiv trè byen.

363
00:30:04,860 --> 00:30:10,500
Men, tout sa nou bezwen vrèman asire w ke nou konprann konplètman se. Dosye yo h

364
00:30:10,500 --> 00:30:15,840
paske ou bezwen yo dwe rele moun ki fonksyon, ki gen rapò ak valè sa yo retou,

365
00:30:15,840 --> 00:30:20,590
se konsa asire w ke ou konprann tout sa aksyon ki pral fèt

366
00:30:20,590 --> 00:30:24,290
nenpòt lè ou rele youn nan moun ki fonksyon.

367
00:30:24,290 --> 00:30:33,020
Men, aktyèlman konprann andedan nan li se pa byen nesesè paske nou gen sa yo. Dosye h.

368
00:30:35,170 --> 00:30:39,490
Nou gen 2 plis dosye kite nan kòd distribisyon nou an.

369
00:30:39,490 --> 00:30:41,640
>> Se pou yo gade nan pil fatra.

370
00:30:41,640 --> 00:30:47,230
Pil fatra nan kòmantè li yo isit la pran yon dosye Huffman-konprese

371
00:30:47,230 --> 00:30:55,580
ak Lè sa a, tradui ak jete li tout kontni li yo deyò.

372
00:31:01,010 --> 00:31:04,260
Isit la nou wè ke li nan rele hfopen.

373
00:31:04,260 --> 00:31:10,770
Sa a se kalite mirwar pote * opinyon = fopen,

374
00:31:10,770 --> 00:31:13,500
ak Lè sa a, ou pase nan enfòmasyon an.

375
00:31:13,500 --> 00:31:18,240
Li nan prèske eksepte olye de yon * dosye w ap pase nan yon Huffile;

376
00:31:18,240 --> 00:31:22,030
olye pou yo fopen w ap pase nan hfopen.

377
00:31:22,030 --> 00:31:29,280
Isit la nou li nan header a an premye, ki se kalite ki sanble ak ki jan nou li nan header a

378
00:31:29,280 --> 00:31:33,580
pou yon dosye bitmap.

379
00:31:33,580 --> 00:31:38,000
Sa n ap fè isit la se tcheke yo wè si wi ou non header enfòmasyon an

380
00:31:38,000 --> 00:31:44,330
gen nimewo a majik dwa ki endike ke li nan yon vrè Huff ranpli,

381
00:31:44,330 --> 00:31:53,610
Lè sa a, tout moun sa yo chèk a asire w ke dosye a ke nou louvri a se yon dosye aktyèl huffed oswa ou pa.

382
00:31:53,610 --> 00:32:05,330
Ki sa sa fè se li sorti fwekans yo nan tout nan senbòl yo ke nou ka wè

383
00:32:05,330 --> 00:32:09,790
ki nan yon tèminal nan yon tablo grafik.

384
00:32:09,790 --> 00:32:15,240
Nan pati sa a a pwal itil.

385
00:32:15,240 --> 00:32:24,680
Li te gen yon ti jan ak li ti jan pa ti jan nan ti jan a varyab ak Lè sa a, simagri li soti.

386
00:32:28,220 --> 00:32:35,430
Se konsa, si m 'te rele pil fatra sou hth.bin, ki se rezilta nan huffing yon dosye

387
00:32:35,430 --> 00:32:39,490
lè l sèvi avèk solisyon an anplwaye yo, mwen ta jwenn sa a.

388
00:32:39,490 --> 00:32:46,000
Li nan sorti tout moun sa yo karaktè ak Lè sa a, mete frekans la nan kote yo parèt.

389
00:32:46,000 --> 00:32:51,180
Si nou gade, pi fò nan yo se 0s eksepte pou sa a: H, ki parèt de fwa,

390
00:32:51,180 --> 00:32:54,820
ak Lè sa a, T, ki parèt yon fwa.

391
00:32:54,820 --> 00:33:07,860
Lè sa a, isit la nou gen mesaj la reyèl nan 0s ak 1S.

392
00:33:07,860 --> 00:33:15,450
Si nou gade nan hth.txt, ki se prezimableman mesaj orijinal la ki te huffed,

393
00:33:15,450 --> 00:33:22,490
nou espere wè kèk HS ak teritwar an la.

394
00:33:22,490 --> 00:33:28,720
Espesyalman, nou espere wè jis 1 T ak HS 2.

395
00:33:32,510 --> 00:33:37,440
Isit la nou yo nan hth.txt. Li tout bon gen HTH.

396
00:33:37,440 --> 00:33:41,270
Enkli nan la, malgre ke nou pa ka wè li, se yon karaktè newline.

397
00:33:41,270 --> 00:33:53,190
Hth.bin nan dosye Huff tou se kodaj karaktè a newline kòm byen.

398
00:33:55,680 --> 00:34:01,330
Isit la paske nou konnen lòd la se HTH ak Lè sa a, newline,

399
00:34:01,330 --> 00:34:07,340
nou ka wè ki pwobableman se H la reprezante nan jis yon sèl 1

400
00:34:07,340 --> 00:34:17,120
ak Lè sa a, T a se pwobableman 01 ak Lè sa a, H nan pwochen se 1 kòm byen

401
00:34:17,120 --> 00:34:21,139
ak Lè sa a, nou gen yon newline endike pa de 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Lè sa a, finalman, paske nou ap fè fas ak miltip c. Ak. Dosye h,

404
00:34:31,600 --> 00:34:36,350
nou pwal gen yon trè konplèks agiman du a,

405
00:34:36,350 --> 00:34:40,460
e konsa isit la nou gen yon makfil ki fè pil fatra pou ou.

406
00:34:40,460 --> 00:34:47,070
Men, aktyèlman, ou gen yo ale sou fè pwòp ou a puff.c dosye-a.

407
00:34:47,070 --> 00:34:54,330
Makfil a aktyèlman pa fè fas ak fè puff.c pou ou.

408
00:34:54,330 --> 00:34:59,310
Nou pap kite sa jiska ou edite makfil la.

409
00:34:59,310 --> 00:35:05,930
Lè ou antre nan yon lòd tankou fè tout, pou egzanp, li pral fè tout nan yo pou ou.

410
00:35:05,930 --> 00:35:10,760
Santi yo lib fè yon gade nan egzanp yo nan makfil soti nan pset ki sot pase a

411
00:35:10,760 --> 00:35:17,400
kòm byen ke pral koupe nan yon sèl sa a yo wè ki jan ou ka kapab fè dosye feyte ou

412
00:35:17,400 --> 00:35:20,260
pa koreksyon sa a makfil.

413
00:35:20,260 --> 00:35:22,730
Sa a sou li pou kòd distribisyon nou an.

414
00:35:22,730 --> 00:35:28,380
>> Yon fwa nou te vinn nan sa, Lè sa a, isit la nan jis yon lòt rapèl

415
00:35:28,380 --> 00:35:30,980
nan ki jan nou ap pral fè fas ak nœuds yo Huffman.

416
00:35:30,980 --> 00:35:35,400
Nou pa pwal yo dwe rele yo nœuds ankò; nou ap pral rele yo pye bwa

417
00:35:35,400 --> 00:35:39,260
kote nou ap pral reprezante senbòl yo ak yon Char,

418
00:35:39,260 --> 00:35:43,340
frekans yo, ki kantite evènman, ak yon antye relatif.

419
00:35:43,340 --> 00:35:47,370
Nou ap lè l sèvi avèk sa paske li nan pi presi pase yon flote.

420
00:35:47,370 --> 00:35:52,980
Lè sa a, nou gen yon lòt konsèy ak timoun nan bò gòch kòm byen ke timoun nan dwa.

421
00:35:52,980 --> 00:35:59,630
Yon forè, kòm nou te wè, se jis yon lis lye nan pyebwa yo.

422
00:35:59,630 --> 00:36:04,670
Alafen, lè nou bati dosye Huff nou an,

423
00:36:04,670 --> 00:36:07,580
nou vle forè nou yo gen ladan jis 1 pyebwa -

424
00:36:07,580 --> 00:36:12,420
1 pye bwa, 1 rasin ak timoun miltip.

425
00:36:12,420 --> 00:36:20,840
Byen bonè nan lè nou te jis ap fè pye bwa Huffman nou an,

426
00:36:20,840 --> 00:36:25,360
nou te kòmanse soti lè w mete tout nœuds yo sou ekran nou an

427
00:36:25,360 --> 00:36:27,790
yo t'ap di konsa nou pwal gen sa yo nœuds,

428
00:36:27,790 --> 00:36:32,920
evantyèlman yo pwal santi yo gen fèy yo, e sa se senbòl yo, sa a se frekans yo.

429
00:36:32,920 --> 00:36:42,070
Nan forè nou si nou jis gen 3 lèt, ki nan yon forè nan 3 pye bwa.

430
00:36:42,070 --> 00:36:45,150
Lè sa a, kòm nou ale sou, lè nou te ajoute paran a an premye,

431
00:36:45,150 --> 00:36:48,080
nou te fè yon forè nan 2 pye bwa.

432
00:36:48,080 --> 00:36:54,930
Nou retire 2 nan timoun sa yo soti nan forè nou yo ak Lè sa a, ranplase li ak yon ne paran

433
00:36:54,930 --> 00:36:58,820
ki te gen sa yo nœuds 2 kòm timoun yo.

434
00:36:58,820 --> 00:37:05,600
Lè sa a, finalman, etap dènye nou an ak fè egzanp nou an ak Kòm B a,, ak CS

435
00:37:05,600 --> 00:37:08,030
ta dwe fè paran final la,

436
00:37:08,030 --> 00:37:13,190
e konsa Lè sa a, ki ta ka pote konte total nou an nan pyebwa nan forè a nan 1.

437
00:37:13,190 --> 00:37:18,140
tout moun wè ki jan ou kòmanse soti ak pye bwa miltip nan forè ou

438
00:37:18,140 --> 00:37:22,520
ak fini ak 1 an? Oke. Fre.

439
00:37:25,530 --> 00:37:28,110
>> Ki sa nou bezwen pou fè pou feyte?

440
00:37:28,110 --> 00:37:37,110
Ki sa nou bezwen fè se asire ke, kòm toujou, yo di nou ki kalite a dwa a opinyon

441
00:37:37,110 --> 00:37:39,090
pou nou ka aktyèlman kouri pwogram nan.

442
00:37:39,090 --> 00:37:43,130
Nan ka sa a yo pwal santi yo dwe ban nou apre agiman premye yo lòd-liy

443
00:37:43,130 --> 00:37:53,440
2 pi plis: dosye a ke nou vle dekonprimra ak pwodiksyon an nan dosye a dekonprime.

444
00:37:53,440 --> 00:38:00,410
Men, yon fwa nou asire yo ke yo pase nou nan kantite lajan an dwa valè yo,

445
00:38:00,410 --> 00:38:05,820
nou vle asire yo ke D 'la se yon dosye Huff oswa ou pa.

446
00:38:05,820 --> 00:38:10,420
Lè sa a, yon fwa nou garanti ke li nan yon dosye Huff, lè sa a nou vle bati pyebwa nou yo,

447
00:38:10,420 --> 00:38:20,940
bati pyebwa sa a tankou ke li matche ak pye bwa a pou moun sa a ki te voye mesaj la bati a.

448
00:38:20,940 --> 00:38:25,840
Lè sa a, apre nou fin bati pyebwa a, Lè sa a, nou ka fè fas ak, nan 0s ak 1S yo ke yo te pase nan

449
00:38:25,840 --> 00:38:29,590
swiv sa yo ansanm pyebwa nou paske li nan idantik,

450
00:38:29,590 --> 00:38:33,510
ak Lè sa a, ekri mesaj sa soti, entèprete Bits yo tounen nan charaktèr.

451
00:38:33,510 --> 00:38:35,880
Lè sa a, nan fen a paske nou ap fè fas ak endikasyon isit la,

452
00:38:35,880 --> 00:38:38,110
nou vle asire ke nou pa genyen kote dlo ap koule memwa

453
00:38:38,110 --> 00:38:41,330
e ke nou gratis tout bagay.

454
00:38:42,820 --> 00:38:46,430
>> Garanti bon itilizasyon se chapo fin vye granmoun pou nou pa kounye a.

455
00:38:46,430 --> 00:38:51,980
Nou pran nan yon D ', ki a pwal non an nan dosye a soufle,

456
00:38:51,980 --> 00:38:56,010
ak Lè sa a, nou espesifye yon pwodiksyon,

457
00:38:56,010 --> 00:39:01,580
Se konsa non an nan dosye a pou pwodiksyon an souple, ki pral dosye a tèks.

458
00:39:03,680 --> 00:39:08,820
Sa a se l '. Epi, koulye a nou vle asire ke yo D 'a huffed oswa ou pa.

459
00:39:08,820 --> 00:39:16,420
Panse tounen, te gen anyen nan kòd la distribisyon ki ta ka ede nou

460
00:39:16,420 --> 00:39:21,570
ak konprann si yon dosye huffed oswa ou pa?

461
00:39:21,570 --> 00:39:26,910
Te gen enfòmasyon ki nan huffile.c sou Huffeader la.

462
00:39:26,910 --> 00:39:33,430
Nou konnen ke chak dosye Huff gen yon Huffeader asosye ak li ak yon kantite majik

463
00:39:33,430 --> 00:39:37,240
kòm byen ke yon etalaj de fwekans yo pou chak senbòl

464
00:39:37,240 --> 00:39:39,570
kòm osi byen yon kontwòl.

465
00:39:39,570 --> 00:39:43,180
Nou konnen ke, men nou menm tou nou te pran yon gade vit nan dump.c,

466
00:39:43,180 --> 00:39:49,120
nan ki li te lekti nan yon dosye Huff.

467
00:39:49,120 --> 00:39:53,990
Se konsa, fè sa, li te gen a tcheke si li vrèman te huffed oswa ou pa.

468
00:39:53,990 --> 00:40:03,380
Se konsa, petèt nou te ka sèvi ak dump.c kòm yon estrikti pou puff.c. nou

469
00:40:03,380 --> 00:40:12,680
Retounen nan pset 4 lè nou te gen copy.c nan dosye ki kopye nan rgb tripl

470
00:40:12,680 --> 00:40:14,860
epi nou entèprete sa pou Whodunit ak rdimansyonman,

471
00:40:14,860 --> 00:40:20,390
Menm jan an, ki sa ou ta ka fè se jis kouri yo lòd, ki tankou cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
epi sèvi ak kèk nan kòd la a.

473
00:40:23,600 --> 00:40:28,210
Sepandan, li pa k ap pase yo dwe kòm dwat nan yon pwosesis

474
00:40:28,210 --> 00:40:33,010
pou tradui dump.c ou a nan puff.c,

475
00:40:33,010 --> 00:40:36,160
men omwen li ba ou yon kote yo kòmanse

476
00:40:36,160 --> 00:40:40,540
sou kòman yo asire ke yo D 'a aktyèlman huffed oswa ou pa

477
00:40:40,540 --> 00:40:43,240
kòm byen ke yon bagay kèk lòt.

478
00:40:45,930 --> 00:40:50,250
Nou te asire ke bon itilizasyon ak asire ke se opinyon nan huffed.

479
00:40:50,250 --> 00:40:53,570
Chak fwa ke nou te fè ke nou te fè kont kouran bon erè nou an,

480
00:40:53,570 --> 00:41:01,520
se konsa retounen ak yon moun kite fimen fonksyon an si gen kèk echèk rive, si gen nan yon pwoblèm.

481
00:41:01,520 --> 00:41:07,170
>> Kounye a ki sa nou vle fè se bati pyebwa a vrè.

482
00:41:08,840 --> 00:41:12,640
Si nou gade nan Forest, gen 2 fonksyon prensipal

483
00:41:12,640 --> 00:41:15,800
ke nou ap pral vle vin trè abitye avèk yo.

484
00:41:15,800 --> 00:41:23,870
Genyen nan plant la fonksyon Boolean ke plant yon pyebwa frekans ki pa 0 andedan forè nou yo.

485
00:41:23,870 --> 00:41:29,250
Se konsa, gen ou pase nan yon konsèy nan yon forè ak yon konsèy nan yon pyebwa.

486
00:41:32,530 --> 00:41:40,340
Quick kesyon: Konbyen forè ou pral gen lè w ap bati yon pyebwa Huffman?

487
00:41:44,210 --> 00:41:46,650
Forè nou yo, se tankou twal nou an, dwa?

488
00:41:46,650 --> 00:41:50,800
Se konsa, nou ap sèlman pral gen 1 forè, men nou pwal gen pye bwa miltip.

489
00:41:50,800 --> 00:41:57,590
Se konsa, anvan ou rele plant yo, w ap prezimableman pral vle fè forè ou.

490
00:41:57,590 --> 00:42:04,430
Gen yon lòd pou ke si ou gade nan forest.h sou ki jan ou ka fè yon forè.

491
00:42:04,430 --> 00:42:09,270
Ou ka plante yon pye bwa. Nou konnen ki jan fè sa.

492
00:42:09,270 --> 00:42:11,590
Lè sa a, ou ka tou chwazi yon pyebwa soti nan forè a,

493
00:42:11,590 --> 00:42:17,540
retire yon pye bwa ak pwa a pi ba a epi ban nou konsèy la ak sa yo ki.

494
00:42:17,540 --> 00:42:23,090
Panse tounen nan lè nou te fè egzanp yo tèt nou,

495
00:42:23,090 --> 00:42:27,980
lè nou te fè desen li soti, nou tou senpleman jis ajoute lyen yo.

496
00:42:27,980 --> 00:42:31,680
Men, isit la olye pou yo jis ajoute lyen yo,

497
00:42:31,680 --> 00:42:40,630
panse a li pi plis pase jan w ap retire 2 nan moun ki nœuds ak Lè sa a, ranplase li pa yon lòt.

498
00:42:40,630 --> 00:42:44,200
Yo eksprime ki an tèm de davwa epi plante,

499
00:42:44,200 --> 00:42:48,840
w ap davwa 2 pye bwa ak Lè sa a, plante yon lòt pye bwa

500
00:42:48,840 --> 00:42:54,060
ki gen sa yo pyebwa 2 ke ou te chwazi kòm timoun yo.

501
00:42:57,950 --> 00:43:05,280
Yo pral bati pyebwa Huffman a, ou ka li nan senbòl yo ak fwekans yo nan lòd

502
00:43:05,280 --> 00:43:10,790
paske Huffeader a bay sa gade ou,

503
00:43:10,790 --> 00:43:14,250
ap ba ou yon etalaj de frekans yo.

504
00:43:14,250 --> 00:43:19,660
Se konsa, ou ka ale pi devan ak jis inyore anyen ak 0 a nan li

505
00:43:19,660 --> 00:43:23,760
paske nou pa vle 256 fèy nan fen li.

506
00:43:23,760 --> 00:43:27,960
Nou sèlman vle ki kantite fèy ki karaktè

507
00:43:27,960 --> 00:43:31,600
ke yo aktyèlman itilize nan dosye a.

508
00:43:31,600 --> 00:43:37,590
Ou ka li nan sa yo senbòl, ak chak nan sa yo senbòl ki gen frekans ki pa 0,

509
00:43:37,590 --> 00:43:40,440
sa yo pwal gen pyebwa.

510
00:43:40,440 --> 00:43:45,990
Ki sa ou ka fè se chak fwa ou li nan yon senbòl frekans ki pa 0,

511
00:43:45,990 --> 00:43:50,660
ou ka plante ki pyebwa ki nan forè an.

512
00:43:50,660 --> 00:43:56,620
Yon fwa ou plante pyebwa yo nan forè a, ou ka rantre nan sa yo pyebwa kòm frè ak sè,

513
00:43:56,620 --> 00:44:01,130
se konsa pral tounen nan plante ak davwa ki kote ou chwazi 2 ak Lè sa a, plant 1,

514
00:44:01,130 --> 00:44:05,820
ki kote ke ou 1 plante a se paran an nan 2 timoun yo ke ou te keyi.

515
00:44:05,820 --> 00:44:11,160
Se konsa, Lè sa a, fini ou rezilta a pwal yon pyebwa sèl nan forè ou.

516
00:44:16,180 --> 00:44:18,170
Sa a se ki jan ou bati pyebwa ou a.

517
00:44:18,170 --> 00:44:21,850
>> Genyen plizyè bagay ki ta kapab ale mal isit la

518
00:44:21,850 --> 00:44:26,580
paske nou ap fè fas ak fè pye bwa ak nouvo fè fas ak endikasyon ak bagay sa yo tankou sa.

519
00:44:26,580 --> 00:44:30,450
Anvan lè nou te fè fas ak endikasyon,

520
00:44:30,450 --> 00:44:36,580
chak fwa nou malloc'd nou te vle asire w ke li pa t 'tounen nou yon valè konsèy nil.

521
00:44:36,580 --> 00:44:42,770
Se konsa, nan plizyè etap nan pwosesis sa a gen pwal gen plizyè ka

522
00:44:42,770 --> 00:44:45,920
kote pwogram ou an te kapab febli.

523
00:44:45,920 --> 00:44:51,310
Ki sa ou vle fè se ou vle asire w ke ou okipe sa yo erè,

524
00:44:51,310 --> 00:44:54,580
ak nan espèk a li di yo okipe yo grasyeu,

525
00:44:54,580 --> 00:45:00,280
se konsa renmen enprime soti yon mesaj bay itilizatè a vle di yo poukisa pwogram nan gen kite fimen

526
00:45:00,280 --> 00:45:03,050
ak Lè sa a, san pèdi tan kite l '.

527
00:45:03,050 --> 00:45:09,490
Pou fè sa manyen erè, sonje ke ou vle tcheke li

528
00:45:09,490 --> 00:45:12,160
chak fwa yon sèl ke ta kapab gen yon echèk.

529
00:45:12,160 --> 00:45:14,660
Chak fwa yon sèl ke w ap fè yon konsèy nouvo

530
00:45:14,660 --> 00:45:17,040
ou vle asire w ke sa a, se siksè.

531
00:45:17,040 --> 00:45:20,320
Anvan sa nou itilize yo fè se fè yon konsèy ak nouvo malok li,

532
00:45:20,320 --> 00:45:22,380
ak Lè sa a, nou ta tcheke si ke konsèy se nil.

533
00:45:22,380 --> 00:45:25,670
Se konsa, gen pwal gen kèk ka kote ou jis ka fè sa,

534
00:45:25,670 --> 00:45:28,610
men pafwa w ap aktyèlman rele yon fonksyon

535
00:45:28,610 --> 00:45:33,100
e nan lespas de ki fonksyon, ki nan youn nan ki nan fè mallocing la.

536
00:45:33,100 --> 00:45:39,110
Nan ka sa a, si nou tounen gade dèyè a kèk nan fonksyon yo nan kòd la,

537
00:45:39,110 --> 00:45:42,260
kèk nan yo yo fonksyon Boolean.

538
00:45:42,260 --> 00:45:48,480
Nan ka abstrè si nou gen yon fonksyon Boolean rele foo,

539
00:45:48,480 --> 00:45:54,580
fondamantalman, nou ka asime ke nan adisyon a fè tou sa foo fè,

540
00:45:54,580 --> 00:45:57,210
depi li nan yon fonksyon Boolean, li retounen vre oubyen fo -

541
00:45:57,210 --> 00:46:01,300
vre si siksè, fo si se pa.

542
00:46:01,300 --> 00:46:06,270
Se konsa, nou vle tcheke si valè a retounen nan foo se vre oubyen fo.

543
00:46:06,270 --> 00:46:10,400
Si li nan fo, sa vle di ke nou ap pral vle enprime kèk kalite mesaj

544
00:46:10,400 --> 00:46:14,390
ak Lè sa a, kite pwogram nan.

545
00:46:14,390 --> 00:46:18,530
Ki sa nou vle fè se tcheke valè a retounen nan foo.

546
00:46:18,530 --> 00:46:23,310
Si foo retounen fo, Lè sa a, nou konnen ke nou rankontre kèk kalite erè

547
00:46:23,310 --> 00:46:25,110
e nou bezwen kite pwogram nou an.

548
00:46:25,110 --> 00:46:35,600
Yon fason yo fè sa a se gen yon kondisyon kote fonksyon aktyèl la li menm se eta sante ou.

549
00:46:35,600 --> 00:46:39,320
Di foo pran nan x.

550
00:46:39,320 --> 00:46:43,390
Nou ka gen kòm yon kondisyon si (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Fondamantalman, sa vle di si nan fen pwomenad foo li retounen vre,

552
00:46:50,900 --> 00:46:57,390
Lè sa a, nou ka fè sa a paske fonksyon an gen evalye foo

553
00:46:57,390 --> 00:47:00,500
yo nan lòd yo evalye kondisyon an antye.

554
00:47:00,500 --> 00:47:06,500
Se konsa, Lè sa a, lè sa a jan ou ka fè yon bagay si fonksyon an retounen vre epi se siksè.

555
00:47:06,500 --> 00:47:11,800
Men, lè ou se kont kouran erè, ou sèlman vle kite fimen, si fonksyon ou retounen fo.

556
00:47:11,800 --> 00:47:16,090
Ki sa ou ta ka fè se jis ajoute yon == ki fo oswa ki jis ajoute yon Bang nan devan li

557
00:47:16,090 --> 00:47:21,010
ak Lè sa a, ou gen si (! foo).

558
00:47:21,010 --> 00:47:29,540
Nan ki nan kò a ki kondisyon ou ta gen tout manyen la erè a,

559
00:47:29,540 --> 00:47:36,940
se konsa renmen, "pa t 'kapab kreye pye bwa sa a" ak Lè sa a, retounen 1 oswa yon bagay tankou sa.

560
00:47:36,940 --> 00:47:43,340
Ki sa ki sa li fè, menm si, se ke menm si foo tounen fo -

561
00:47:43,340 --> 00:47:46,980
Di foo retounen vre.

562
00:47:46,980 --> 00:47:51,060
Lè sa a, ou pa bezwen rele foo ankò. Sa se yon miskonsepsyon komen.

563
00:47:51,060 --> 00:47:54,730
Paske li te nan yon kondisyon ou, li te deja evalye,

564
00:47:54,730 --> 00:47:59,430
konsa ou te deja genyen rezilta a si w ap fè lè l sèvi avèk pye bwa oswa yon bagay tankou sa

565
00:47:59,430 --> 00:48:01,840
oswa plant oubyen chwazi oswa yon bagay.

566
00:48:01,840 --> 00:48:07,460
Li deja genyen ki valè. Li nan deja egzekite.

567
00:48:07,460 --> 00:48:10,730
Se konsa, li itil nan itilize fonksyon Boolean kòm kondisyon an

568
00:48:10,730 --> 00:48:13,890
paske si ou pa ou aktyèlman egzekite kò a nan riban an,

569
00:48:13,890 --> 00:48:18,030
li ègzekutra fonksyon an de tout fason.

570
00:48:22,070 --> 00:48:27,330
>> Dezyèm nou an etap dènye ap ekri mesaj la nan dosye a.

571
00:48:27,330 --> 00:48:33,070
Yon fwa nou bati pyebwa a Huffman, lè sa a ekri mesaj la nan dosye a se trè senp.

572
00:48:33,070 --> 00:48:39,260
Li trè senp kounye a nan jis swiv 0s la ak 1S.

573
00:48:39,260 --> 00:48:45,480
Se konsa, pa konvansyon nou konnen ke nan yon pyebwa Huffman 0s la endike kite

574
00:48:45,480 --> 00:48:48,360
ak 1S a endike dwat.

575
00:48:48,360 --> 00:48:53,540
Se konsa, Lè sa a, si w li nan ti jan pa ti jan, chak fwa ke ou jwenn yon 0

576
00:48:53,540 --> 00:48:59,100
ou pral swiv branch nan bò gòch, ak Lè sa a, chak fwa ou li nan yon 1

577
00:48:59,100 --> 00:49:02,100
w ap ale nan swiv branch a dwat.

578
00:49:02,100 --> 00:49:07,570
Lè sa a, w ap ale nan yo ap kontinye jouk ou frape yon fèy

579
00:49:07,570 --> 00:49:11,550
paske fèy yo pwal gen nan fen branch yo.

580
00:49:11,550 --> 00:49:16,870
Ki jan nou ka di si nou te frape yon fèy oswa ou pa?

581
00:49:19,800 --> 00:49:21,690
Nou te di l 'devan.

582
00:49:21,690 --> 00:49:24,040
[Elèv] Si endikasyon yo ki nil. >> Yeah.

583
00:49:24,040 --> 00:49:32,220
Nou kapab di si nou te frape yon fèy si pwent yo nan pyebwa tou de bò gòch la ak dwa yo se nil.

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

585
00:49:34,110 --> 00:49:40,320
Nou konnen nou vle li nan ti jan pa ti jan nan dosye Huff nou an.

586
00:49:43,870 --> 00:49:51,220
Kòm nou te wè anvan an dump.c, ki sa yo te fè se yo li nan ti jan pa ti jan nan dosye a Huff

587
00:49:51,220 --> 00:49:54,560
ak jis enprime konnen ki sa ki sa yo Bits yo te.

588
00:49:54,560 --> 00:49:58,430
Nou pa pwal yo dwe fè sa. Nou ap pral fè yon bagay ki nan yon ti jan pi plis konplèks.

589
00:49:58,430 --> 00:50:03,620
Men, sa nou kapab fè se nou ka pran ki ti jan nan kòd ki li nan ti jan an.

590
00:50:03,620 --> 00:50:10,250
Isit la nou gen ti jan nan nonb antye relatif ki reprezante ti jan li ye kounye a ke nou ap sou.

591
00:50:10,250 --> 00:50:15,520
Sa a pran swen de iteration tout Bits yo nan dosye a jiskaske ou frape nan fen dosye a.

592
00:50:15,520 --> 00:50:21,270
Ki baze sou sa, Lè sa a, w ap ale nan vle gen kèk kalite iterator

593
00:50:21,270 --> 00:50:26,760
Traverse pyebwa ou a.

594
00:50:26,760 --> 00:50:31,460
Lè sa a, ki baze sou si wi ou non ti jan la se 0 oswa 1,

595
00:50:31,460 --> 00:50:36,920
w ap ale nan vle swa deplase ki iterator a gòch la oswa deplase li a dwat a

596
00:50:36,920 --> 00:50:44,080
tout wout la jouk ou frape yon fèy, se konsa tout wout la jouk ki ne ke ou se sou

597
00:50:44,080 --> 00:50:48,260
pa lonje dwèt sou nenpòt ki plis nœuds.

598
00:50:48,260 --> 00:50:54,300
Poukisa nou ka fè sa avèk yon dosye Huffman, men se pa Morse kòd?

599
00:50:54,300 --> 00:50:56,610
Paske nan kòd Morse gen nan yon ti jan nan anbigwite.

600
00:50:56,610 --> 00:51:04,440
Nou te ka fè tankou, O rete tann, nou te frape yon lèt nan tout wout la, se konsa petèt sa a se lèt nou an,

601
00:51:04,440 --> 00:51:08,150
Lè nou konsidere ke si nou kontinye jis yon ti jan pi long, Lè sa a, nou ta gen frape yon lòt lèt.

602
00:51:08,150 --> 00:51:13,110
Men, ki pa nan pwal rive nan kodaj Huffman,

603
00:51:13,110 --> 00:51:17,540
pou nou ka Rest te asire ke wout la sèlman ke nou ap ale nan frape yon karaktè

604
00:51:17,540 --> 00:51:23,480
se si timoun yo kite la ak dwa ki ne la yo se nil.

605
00:51:28,280 --> 00:51:32,350
>> Finalman, nou vle libere tout nan memwa nou an.

606
00:51:32,350 --> 00:51:37,420
Nou vle tou de pre dosye a Huff ke nou ve yo te fè fas ak

607
00:51:37,420 --> 00:51:41,940
kòm byen ke retire tout nan pyebwa yo nan forè nou yo.

608
00:51:41,940 --> 00:51:46,470
Ki baze sou aplikasyon ou an, w ap pwobableman pral vle rele retire forè

609
00:51:46,470 --> 00:51:49,780
olye pou yo aktyèlman ale atravè tout tout nan pyebwa yo tèt ou.

610
00:51:49,780 --> 00:51:53,430
Men, si ou te fè nenpòt pye bwa tanporè, ou pral vle libere sa.

611
00:51:53,430 --> 00:51:59,060
Ou konnen kòd ou a pi bon, kidonk, ou konnen ki kote w ap allocation memwa.

612
00:51:59,060 --> 00:52:04,330
Se konsa, si ou ale nan, kòmanse nan menm kontwòl F'ing pou malok,

613
00:52:04,330 --> 00:52:08,330
wè nenpòt lè ou malok ak fè asire w ke ou libere nan tout sa

614
00:52:08,330 --> 00:52:10,190
men Lè sa a, jis ale atravè tout kòd ou a,

615
00:52:10,190 --> 00:52:14,260
konprann ki kote ou ka gen afekte memwa.

616
00:52:14,260 --> 00:52:21,340
Anjeneral ou ta ka jis di, "Nan fen yon dosye mwen jis ale nan retire forè sou forè m 'yo,"

617
00:52:21,340 --> 00:52:23,850
Se konsa, fondamantalman klè ke memwa, gratis ki,

618
00:52:23,850 --> 00:52:28,310
"Ak Lè sa a, mwen tou ale nan fèmen dosye a ak Lè sa a, pwogram mwen ki pral kite."

619
00:52:28,310 --> 00:52:33,810
Men, se tan sa a la sèlman ki pwogram ou an L Kite?

620
00:52:33,810 --> 00:52:37,880
Non, paske pafwa gen ta ka fèt yon yon erè ki te rive.

621
00:52:37,880 --> 00:52:42,080
Petèt nou pa t 'kapab louvri yon dosye oswa nou pa t' kapab fè yon lòt pye bwa

622
00:52:42,080 --> 00:52:49,340
oswa kèk kalite erè ki te pase nan pwosesis la alokasyon memwa ak se konsa li tounen nil.

623
00:52:49,340 --> 00:52:56,710
Yon erè ki te pase ak Lè sa a, nou tounen, yo kite fimen.

624
00:52:56,710 --> 00:53:02,040
Se konsa, Lè sa a, ou vle asire w ke nenpòt ki lè posib ke pwogram ou a ka kite fimen,

625
00:53:02,040 --> 00:53:06,980
ou vle libere tout nan memwa ou a la.

626
00:53:06,980 --> 00:53:13,370
Li pa nan jis pral fèt nan fen anpil nan fonksyon prensipal ke ou kite kòd ou a.

627
00:53:13,370 --> 00:53:20,780
Ou vle gade tounen nan chak egzanp ki kòd ou a potansyèlman ta ka retounen prematireman

628
00:53:20,780 --> 00:53:25,070
ak Lè sa a, gratis kèlkeswa sa memwa fè sans.

629
00:53:25,070 --> 00:53:30,830
Di ou te rele fè forè e ke tounen fo.

630
00:53:30,830 --> 00:53:34,230
Lè sa a, pwobableman ou pa pral bezwen yo retire forè ou

631
00:53:34,230 --> 00:53:37,080
paske ou pa gen yon forè ankò.

632
00:53:37,080 --> 00:53:42,130
Men, nan chak pwen nan kòd la kote ou ta ka retounen prematireman

633
00:53:42,130 --> 00:53:46,160
ou vle asire w ke ou libere nenpòt memwa posib.

634
00:53:46,160 --> 00:53:50,020
>> Se konsa, lè nou ap fè fas ak delivre memwa epi ki gen fwit potansyèl,

635
00:53:50,020 --> 00:53:55,440
nou vle pa sèlman sèvi ak jijman nou yo ak lojik nou

636
00:53:55,440 --> 00:54:01,850
men tou sèvi ak Valgrind kapab detèmine si nou te libere tout memwa nou byen oswa ou pa.

637
00:54:01,850 --> 00:54:09,460
Ou kapab swa kouri Valgrind sou feyte ak Lè sa a, ou gen tou pase l

638
00:54:09,460 --> 00:54:14,020
nimewo a dwa a bay lòd-liy agiman Valgrind.

639
00:54:14,020 --> 00:54:18,100
Ou ka kouri sa, men pwodiksyon an se yon ti jan skre.

640
00:54:18,100 --> 00:54:21,630
Nou te vinn yon ti jan yo itilize li ak ortograf, men nou toujou bezwen yon ti jan plis èd,

641
00:54:21,630 --> 00:54:26,450
se konsa Lè sa a, kouri li ak yon drapo kèk plis tankou fuit radyasyon-tcheke plen nan =,

642
00:54:26,450 --> 00:54:32,040
ki pral pwobableman ba nou kèk pwodiksyon plis itil sou Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Lè sa a, yon lòt pwent itil lè w ap debogaj se yo lòd, ki diff.

644
00:54:39,040 --> 00:54:48,520
Ou ka jwenn aksè aplikasyon anplwaye a nan Huff, kouri sa sou yon dosye tèks,

645
00:54:48,520 --> 00:54:55,400
ak Lè sa a, Sòti li nan yon dosye binè, yon binè Huff dosye, yo dwe espesifik.

646
00:54:55,400 --> 00:54:59,440
Lè sa a, si ou kouri soufle pwòp ou a sou sa dosye binè,

647
00:54:59,440 --> 00:55:03,950
Lè sa a, depreferans, dosye outputted tèks ou a pwal idantik

648
00:55:03,950 --> 00:55:08,200
nan yon sèl orijinal la ke ou te pase pous

649
00:55:08,200 --> 00:55:15,150
Isit la mwen sèvi ak hth.txt kòm egzanp lan, ak sa a, se yon sèl la te pale osijè de nan espèk ou a.

650
00:55:15,150 --> 00:55:21,040
Sa a se literalman jis HTH ak Lè sa a, yon newline.

651
00:55:21,040 --> 00:55:30,970
Men, definitivman santi yo lib, epi ou yo definitivman ankouraje yo sèvi ak pi long egzanp

652
00:55:30,970 --> 00:55:32,620
pou dosye tèks ou.

653
00:55:32,620 --> 00:55:38,110
>> Ou ka menm pran yon bal nan petèt konpresan ak Lè sa a, dekonpresyon

654
00:55:38,110 --> 00:55:41,600
kèk nan dosye yo ke ou te itilize nan ortograf tankou Lagè ak Lapè

655
00:55:41,600 --> 00:55:46,710
oswa Jane Austen oswa yon bagay tankou sa - ki ta ka kalite fre - oswa Austin Powers,

656
00:55:46,710 --> 00:55:51,880
kalite ki gen rapò ak pi gwo dosye paske nou pa t 'vle vini desann nan li

657
00:55:51,880 --> 00:55:55,590
si nou te itilize zouti nan pwochen isit la, ls-l.

658
00:55:55,590 --> 00:56:01,150
Nou abitye a ls, ki fondamantalman lis tout sa ki nan anyè aktyèl nou yo.

659
00:56:01,150 --> 00:56:07,860
Pase nan drapo l la-aktyèlman montre gwosè a nan tout sa yo dosye.

660
00:56:07,860 --> 00:56:12,690
Si ou ale nan espèk a pset, li aktyèlman ap mache ou atravè kreye dosye a binè,

661
00:56:12,690 --> 00:56:16,590
nan huffing li, epi ou wè sa a pou dosye ki piti anpil

662
00:56:16,590 --> 00:56:23,910
espas pri a nan konpresan li epi li tradui tout enfòmasyon sa a

663
00:56:23,910 --> 00:56:26,980
nan tout fwekans yo ak bagay sa yo tankou ki depas benefis aktyèl la

664
00:56:26,980 --> 00:56:30,000
nan konpresan dosye a an plas an premye.

665
00:56:30,000 --> 00:56:37,450
Men, si ou kouri li sou kèk fichye tèks pi long, Lè sa a, ou ta ka wè ke ou kòmanse jwenn kèk benefis

666
00:56:37,450 --> 00:56:40,930
nan konpresan sa yo dosye.

667
00:56:40,930 --> 00:56:46,210
>> Lè sa a, finalman, nou gen fin vye granmoun nou zanmi gdb, ki se definitivman pral vini an sou la men tou.

668
00:56:48,360 --> 00:56:55,320
>> nou gen nenpòt kesyon sou Huff pye bwa oubyen pwosesis la petèt nan fè pyebwa yo

669
00:56:55,320 --> 00:56:58,590
oswa nenpòt lòt kesyon ki sou feyte Huff'n?

670
00:57:00,680 --> 00:57:02,570
Oke. Mwen pral rete alantou pou yon ti jan.

671
00:57:02,570 --> 00:57:06,570
>> Di Bondye mèsi, tout moun. Sa a te solisyon 6. Ak bon chans.

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