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

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

3
00:00:04,810 --> 00:00:07,240
[Detta är CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hej, alla, och välkommen till Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
I Huff'n Puff vad vi gör kommer att ha att göra med en Huffman komprimerad fil

6
00:00:17,440 --> 00:00:20,740
och sedan blåsa tillbaka upp, så dekomprimering det,

7
00:00:20,740 --> 00:00:25,810
så att vi kan översätta från 0 och 1 som användaren skickar oss

8
00:00:25,810 --> 00:00:30,660
och omvandla den tillbaka till den ursprungliga texten.

9
00:00:30,660 --> 00:00:34,360
Pset 6 kommer att vara ganska coolt eftersom du kommer att se några av de verktyg

10
00:00:34,360 --> 00:00:41,730
som du använde i pset 4 och pset 5 och typ av kombinera dem till 1 ganska snyggt koncept

11
00:00:41,730 --> 00:00:43,830
när du kommer att tänka på det.

12
00:00:43,830 --> 00:00:50,110
>> Också utan tvekan var pset 4 och 5 de mest utmanande psets som vi hade att erbjuda.

13
00:00:50,110 --> 00:00:53,950
Så från och med nu har vi denna 1 mer pset i C,

14
00:00:53,950 --> 00:00:56,480
och sedan efter att vi är på att webbprogrammering.

15
00:00:56,480 --> 00:01:02,310
Så gratulerar er för att få över den tuffaste puckel i CS50.

16
00:01:03,630 --> 00:01:09,760
>> Flytta på för Huff'n Puff är vår verktygslåda för pset kommer att vara Huffman träd,

17
00:01:09,760 --> 00:01:14,700
så förstå inte bara hur binära träd arbete men också specifikt Huffman träd,

18
00:01:14,700 --> 00:01:16,240
hur de konstrueras.

19
00:01:16,240 --> 00:01:20,210
Och då ska vi ha en massa utdelning kod i pset,

20
00:01:20,210 --> 00:01:22,480
och vi kommer att se att faktiskt en del av koden

21
00:01:22,480 --> 00:01:24,670
Vi kanske inte kan till fullo förstå ännu,

22
00:01:24,670 --> 00:01:30,080
och så de kommer att vara. C-filer, men då deras medföljande. h-filer

23
00:01:30,080 --> 00:01:34,300
kommer att ge oss tillräckligt med kunskap som vi behöver, så att vi vet hur dessa funktioner fungerar

24
00:01:34,300 --> 00:01:38,100
eller åtminstone vad de ska göra - deras in-och utgångar -

25
00:01:38,100 --> 00:01:40,760
även om vi inte vet vad som händer i den svarta lådan

26
00:01:40,760 --> 00:01:44,090
eller förstår inte vad som händer i den svarta lådan i.

27
00:01:44,090 --> 00:01:49,400
Och slutligen, som vanligt har vi att göra med nya datastrukturer,

28
00:01:49,400 --> 00:01:51,840
specifika typer av noder som pekar på vissa saker,

29
00:01:51,840 --> 00:01:56,080
och så här med en penna och papper, inte bara för designprocessen

30
00:01:56,080 --> 00:01:58,470
och när du försöker lista ut hur din pset bör arbeta

31
00:01:58,470 --> 00:02:00,520
men också under felsökning.

32
00:02:00,520 --> 00:02:06,140
Du kan ha GDB tillsammans med ditt penna och papper medan du tar ner vad värdena,

33
00:02:06,140 --> 00:02:09,320
där dina pilarna pekar och sådana saker.

34
00:02:09,320 --> 00:02:13,720
>> Först ska vi titta på Huffman träd.

35
00:02:13,720 --> 00:02:19,600
Huffman träd är binära träd, vilket innebär att varje nod endast har 2 barn.

36
00:02:19,600 --> 00:02:24,870
I Huffman träd egenskapen är att de vanligaste värdena

37
00:02:24,870 --> 00:02:27,140
representeras av de minsta bitarna.

38
00:02:27,140 --> 00:02:32,690
Vi såg i föreläsningssalar exempel på morsekod, vilken typ av koncernens några brev.

39
00:02:32,690 --> 00:02:38,030
Om du försöker översätta ett A eller ett E, till exempel,

40
00:02:38,030 --> 00:02:43,940
du översätter det ofta, så istället för att behöva använda hela uppsättningen bitar

41
00:02:43,940 --> 00:02:48,640
avsatts för att vanliga datatyp komprimera du ner till färre,

42
00:02:48,640 --> 00:02:53,730
och sedan dessa bokstäver som utgjorde mindre ofta representerade med längre bitar

43
00:02:53,730 --> 00:02:59,840
eftersom du har råd att när du väga de frekvenser som dessa skrivelser visas.

44
00:02:59,840 --> 00:03:03,020
Vi har samma idé här i Huffman träd

45
00:03:03,020 --> 00:03:12,360
där vi gör en kedja, en slags väg för att komma till vissa tecken.

46
00:03:12,360 --> 00:03:14,470
Och sedan de tecken som har mest frekvensen

47
00:03:14,470 --> 00:03:17,940
kommer att vara representerade med minst antal bitar.

48
00:03:17,940 --> 00:03:22,020
>> Det sätt som du konstruera en Huffman träd

49
00:03:22,020 --> 00:03:27,430
är genom att placera alla de tecken som visas i texten

50
00:03:27,430 --> 00:03:30,630
och beräkna deras frekvens, hur ofta de förekommer.

51
00:03:30,630 --> 00:03:33,880
Detta kan antingen vara en räkningen på hur många gånger dessa bokstäver visas

52
00:03:33,880 --> 00:03:40,270
eller kanske en procentandel av av alla tecken hur många var och en visas.

53
00:03:40,270 --> 00:03:44,270
Och så vad du gör är när du har allt det utstakad,

54
00:03:44,270 --> 00:03:49,060
då du leta efter 2 lägsta frekvenserna och sedan gå med dem som syskon

55
00:03:49,060 --> 00:03:55,660
där då den överordnade noden har en frekvens som är summan av dess 2 barn.

56
00:03:55,660 --> 00:04:00,870
Och sedan genom konventionen säger att den vänstra noden,

57
00:04:00,870 --> 00:04:03,770
du följer det genom att följa 0 gren,

58
00:04:03,770 --> 00:04:08,140
och sedan längst till höger nod är 1 gren.

59
00:04:08,140 --> 00:04:16,040
Som vi såg i morsekod, var en gotcha att om du bara hade en ljudsignal och pip

60
00:04:16,040 --> 00:04:18,120
det var tvetydigt.

61
00:04:18,120 --> 00:04:22,430
Det kan antingen vara 1 bokstav eller det kan vara en sekvens av 2 bokstäver.

62
00:04:22,430 --> 00:04:27,790
Och så vad Huffman träd gör beror av naturen av tecknen

63
00:04:27,790 --> 00:04:34,140
eller våra sista faktiska tecken är de sista noderna på grenen -

64
00:04:34,140 --> 00:04:39,300
Vi hänvisar till de som löv - på grund av att det inte kan finnas någon tvetydighet

65
00:04:39,300 --> 00:04:45,160
enligt vilken bokstav du försöker koda med serien av bitar

66
00:04:45,160 --> 00:04:50,670
eftersom ingenstans längs de bitar som representerar 1 bokstav

67
00:04:50,670 --> 00:04:55,960
kommer du att stöta annan hela brevet, och det kommer inte finnas någon förvirring där.

68
00:04:55,960 --> 00:04:58,430
Men vi ska gå in exempel som ni faktiskt kan se att

69
00:04:58,430 --> 00:05:02,120
istället för oss berättar just om att det är sant.

70
00:05:02,120 --> 00:05:06,390
>> Låt oss titta på ett enkelt exempel på en Huffman träd.

71
00:05:06,390 --> 00:05:09,380
Jag har en sträng här som är 12 tecken långt.

72
00:05:09,380 --> 00:05:14,010
Jag har 4 As, 6 B, och 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Mitt första steg skulle vara att räkna.

74
00:05:17,270 --> 00:05:20,760
Hur många gånger verkar A? Det verkar 4 gånger i strängen.

75
00:05:20,760 --> 00:05:25,060
B visas 6 gånger, och C visas 2 gånger.

76
00:05:25,060 --> 00:05:28,970
Naturligtvis, jag kommer att säga att jag med B oftast,

77
00:05:28,970 --> 00:05:35,970
så jag vill representera B med minst antal bitar, det minsta antalet 0 och 1.

78
00:05:35,970 --> 00:05:42,600
Och då jag också kommer att förvänta sig C för att kräva mest mängd av 0 och 1 samt.

79
00:05:42,600 --> 00:05:48,550
Först vad jag gjorde här är jag placerade dem i stigande ordning i fråga om frekvens.

80
00:05:48,550 --> 00:05:52,710
Vi ser att C och A, de är våra 2 lägsta frekvenserna.

81
00:05:52,710 --> 00:06:00,290
Vi skapar en förälder nod och att överordnade noden inte har ett brev i samband med det,

82
00:06:00,290 --> 00:06:05,070
men det har en frekvens, som är summan.

83
00:06:05,070 --> 00:06:08,780
Summan blir 2 + 4, vilket är 6.

84
00:06:08,780 --> 00:06:10,800
Sedan följer vi den vänstra grenen.

85
00:06:10,800 --> 00:06:14,970
Om vi ​​på det 6 nod, då skulle vi följa 0 för att komma till C

86
00:06:14,970 --> 00:06:17,450
och sedan 1 för att få till A.

87
00:06:17,450 --> 00:06:20,300
Så nu har vi 2 noder.

88
00:06:20,300 --> 00:06:23,920
Vi har värdet 6 och vi har också en annan nod med värdet 6.

89
00:06:23,920 --> 00:06:28,550
Och så de 2 är inte bara 2 lägst men också bara 2 som är kvar,

90
00:06:28,550 --> 00:06:33,820
så vi går dem av en annan förälder, med summan är 12.

91
00:06:33,820 --> 00:06:36,300
Så här har vi vår Huffmanträd

92
00:06:36,300 --> 00:06:40,020
om att få till B, det skulle bara vara lite 1

93
00:06:40,020 --> 00:06:45,430
och sedan komma till en vi skulle ha 01 och sedan C med 00.

94
00:06:45,430 --> 00:06:51,300
Så här ser vi att i princip vi representerar dessa tecken med antingen 1 eller 2 bitar

95
00:06:51,300 --> 00:06:55,160
där B, som förväntat, har minst.

96
00:06:55,160 --> 00:07:01,730
Och sedan vi hade förväntat C ha mest, men eftersom det är en så liten Huffman träd,

97
00:07:01,730 --> 00:07:06,020
då A är även representerad av 2 bitar i motsats till någonstans i mitten.

98
00:07:07,820 --> 00:07:11,070
>> Bara att gå över en annan enkelt exempel på Huffman träd,

99
00:07:11,070 --> 00:07:19,570
säga att du har strängen "Hej."

100
00:07:19,570 --> 00:07:25,360
Vad du gör är du först skulle säga hur många gånger gör H visas i detta?

101
00:07:25,360 --> 00:07:34,200
H visas en gång och sedan e visas en gång och sedan har vi l förekommer två gånger

102
00:07:34,200 --> 00:07:36,580
och o visas en gång.

103
00:07:36,580 --> 00:07:44,310
Och så då förväntar vi oss vilken bokstav som representeras av det minsta antalet bitar?

104
00:07:44,310 --> 00:07:47,450
[Studenten] L. >> L.. Ja. l är rätt.

105
00:07:47,450 --> 00:07:50,730
Vi förväntar jag att företrädas av det minsta antalet bitar

106
00:07:50,730 --> 00:07:55,890
för att jag används mest i strängen "Hello".

107
00:07:55,890 --> 00:08:04,280
Vad jag ska göra nu är att dra ut dessa noder.

108
00:08:04,280 --> 00:08:15,580
Jag har 1, vilket är H, och sedan en annan 1, som är e, och sedan en 1, som är o -

109
00:08:15,580 --> 00:08:23,410
just nu är jag sätta dem i ordning - och sedan 2, vilket är l.

110
00:08:23,410 --> 00:08:32,799
Då säger jag det sätt som jag bygger en Huffman träd är att hitta de 2 noder med de minst frekvenserna

111
00:08:32,799 --> 00:08:38,010
och göra dem syskon genom att skapa en förälder nod.

112
00:08:38,010 --> 00:08:41,850
Här har vi 3 noder med den lägsta frekvensen. De är alla 1.

113
00:08:41,850 --> 00:08:50,620
Så här väljer vi vilken vi ska länka först.

114
00:08:50,620 --> 00:08:54,850
Låt oss säga att jag väljer H och e.

115
00:08:54,850 --> 00:09:01,150
Summan av 1 + 1 är 2, men denna nod inte har ett brev i samband med det.

116
00:09:01,150 --> 00:09:04,440
Det håller bara värdet.

117
00:09:04,440 --> 00:09:10,950
Nu ser vi på de närmaste 2 lägsta frekvenserna.

118
00:09:10,950 --> 00:09:15,590
Det är 2 och 1. Det kan vara någon av dessa 2, men jag kommer att välja här.

119
00:09:15,590 --> 00:09:18,800
Summan är 3.

120
00:09:18,800 --> 00:09:26,410
Och slutligen har jag bara 2 kvar, så då blir 5.

121
00:09:26,410 --> 00:09:32,010
Då här, som förväntat, om jag fylla i kodning för att

122
00:09:32,010 --> 00:09:37,480
1s är alltid rätt gren och 0: or är den vänstra.

123
00:09:37,480 --> 00:09:45,880
Då har vi L representeras av bara 1 bit och sedan o med 2

124
00:09:45,880 --> 00:09:52,360
och därefter e med 2 och sedan H faller ned till 3 bitar.

125
00:09:52,360 --> 00:09:59,750
Så du kan skicka meddelandet "Hej" istället för att faktiskt använda tecknen

126
00:09:59,750 --> 00:10:02,760
genom att bara 0 och 1.

127
00:10:02,760 --> 00:10:07,910
Kom dock ihåg att i flera fall hade vi band med vår frekvens.

128
00:10:07,910 --> 00:10:11,900
Vi kunde ha antingen gått H och O 1. Kanske.

129
00:10:11,900 --> 00:10:15,730
Eller senare när vi hade L representeras av 2

130
00:10:15,730 --> 00:10:19,410
samt gick en representeras av 2, kunde vi ha kopplat antingen en.

131
00:10:19,410 --> 00:10:23,630
>> Och så när du skickar 0 och 1, som faktiskt inte garanterar

132
00:10:23,630 --> 00:10:27,090
att mottagaren kan helt läsa ditt meddelande höger utanför bat

133
00:10:27,090 --> 00:10:30,490
eftersom de kanske inte vet vilket beslut du gjort.

134
00:10:30,490 --> 00:10:34,920
Så när vi har att göra med Huffman-komprimering,

135
00:10:34,920 --> 00:10:40,090
på något sätt måste vi tala om för mottagaren av vårt budskap om hur vi bestämde -

136
00:10:40,090 --> 00:10:43,470
De behöver veta någon form av extra information

137
00:10:43,470 --> 00:10:46,580
Förutom den komprimerade meddelandet.

138
00:10:46,580 --> 00:10:51,490
De måste förstå vad trädet egentligen ser ut,

139
00:10:51,490 --> 00:10:55,450
hur vi gjorde faktiskt dessa beslut.

140
00:10:55,450 --> 00:10:59,100
>> Här var vi bara göra exempel baserade på faktiska räkningen,

141
00:10:59,100 --> 00:11:01,550
men ibland kan du också ha en Huffman träd

142
00:11:01,550 --> 00:11:05,760
baserat på den frekvens där bokstäverna visas, och det är exakt samma process.

143
00:11:05,760 --> 00:11:09,090
Här jag uttrycka det i termer av procent eller en fraktion,

144
00:11:09,090 --> 00:11:11,290
och så här exakt samma sak.

145
00:11:11,290 --> 00:11:15,300
Jag tycker att 2 lägsta, summera dem, nästa 2 lägsta, summera dem,

146
00:11:15,300 --> 00:11:19,390
tills jag har en full träd.

147
00:11:19,390 --> 00:11:23,610
Även om vi kunde göra det hur som helst, när vi har att göra med procentsatser,

148
00:11:23,610 --> 00:11:27,760
det betyder att vi dela saker och hantera decimaler eller snarare flyter

149
00:11:27,760 --> 00:11:30,900
Om vi ​​tänker på datastrukturer i ett huvud.

150
00:11:30,900 --> 00:11:32,540
Vad vet vi om flottar?

151
00:11:32,540 --> 00:11:35,180
Vad är ett vanligt problem när vi har att göra med flöten?

152
00:11:35,180 --> 00:11:38,600
[Elev] oprecisa aritmetik. >> Ja. Inexakthet.

153
00:11:38,600 --> 00:11:43,760
På grund av flyttal vaghet, för pset så att vi ser till

154
00:11:43,760 --> 00:11:49,450
att vi inte förlorar några värden, så vi faktiskt kommer att ha att göra med räkningen.

155
00:11:49,450 --> 00:11:54,880
Så om du skulle tänka på en Huffman nod, om man ser tillbaka till strukturen här,

156
00:11:54,880 --> 00:12:01,740
om man tittar på de gröna har en frekvens i samband med det

157
00:12:01,740 --> 00:12:08,760
liksom det pekar på en nod till vänster samt en nod till sin rätt.

158
00:12:08,760 --> 00:12:13,970
Och sedan de röda det också har en karaktär i samband med dem.

159
00:12:13,970 --> 00:12:18,900
Vi kommer inte att göra separata dem för föräldrarna och sedan de sista noder,

160
00:12:18,900 --> 00:12:23,680
som vi kallar löv, utan de kommer bara att ha NULL-värden.

161
00:12:23,680 --> 00:12:31,050
För varje nod kommer vi att ha ett tecken, en symbol som den noden representerar,

162
00:12:31,050 --> 00:12:40,490
då en frekvens samt en pekare till dess vänstra underordnade och dess högra underordnade.

163
00:12:40,490 --> 00:12:45,680
Bladen, som är längst ner, skulle också ha nod pekare

164
00:12:45,680 --> 00:12:49,550
till deras vänster och till höger, men eftersom dessa värden inte pekar på faktiska noder,

165
00:12:49,550 --> 00:12:53,970
vad skulle deras värde vara? >> [Elev] NULL. >> NULL. Exakt.

166
00:12:53,970 --> 00:12:58,430
Här är ett exempel på hur du kan representera frekvensen i flottar,

167
00:12:58,430 --> 00:13:02,130
men vi kommer att ha att göra med det med heltal,

168
00:13:02,130 --> 00:13:06,780
så allt jag gjorde är att ändra datatypen där.

169
00:13:06,780 --> 00:13:09,700
>> Låt oss gå vidare till lite mer av en komplex exempel.

170
00:13:09,700 --> 00:13:13,360
Men nu när vi har gjort de enkla, det är bara samma process.

171
00:13:13,360 --> 00:13:20,290
Du hittar 2 lägsta frekvenserna, summera frekvenserna

172
00:13:20,290 --> 00:13:22,450
och det är den nya frekvensen av din förälder nod,

173
00:13:22,450 --> 00:13:29,310
som pekar sedan till vänster med 0 grenen och höger med 1 gren.

174
00:13:29,310 --> 00:13:34,200
Om vi ​​har strängen "Detta är CS50," vi räkna hur många gånger T nämns,

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

176
00:13:38,420 --> 00:13:42,010
Sen vad jag gjorde här är de röda noderna jag planterade,

177
00:13:42,010 --> 00:13:48,530
Jag sa att jag kommer att ha dessa tecken så småningom på botten av mitt träd.

178
00:13:48,530 --> 00:13:51,740
De kommer att vara alla av bladen.

179
00:13:51,740 --> 00:13:58,200
Sen vad jag gjorde är jag sorterade dem efter frekvens i stigande ordning,

180
00:13:58,200 --> 00:14:02,950
och detta är faktiskt det sätt som pset koden gör det

181
00:14:02,950 --> 00:14:07,550
är det sorterar det efter frekvens och sedan i alfabetisk ordning.

182
00:14:07,550 --> 00:14:13,870
Så det har siffrorna först och sedan alfabetiskt efter frekvensen.

183
00:14:13,870 --> 00:14:18,520
Så vad jag skulle göra är jag skulle hitta 2 lägsta. Det är 0 och 5.

184
00:14:18,520 --> 00:14:22,390
Jag skulle sammanfatta dem, och det är 2. Då skulle jag fortsätta söka efter nästa 2 lägst.

185
00:14:22,390 --> 00:14:26,100
Dessa är de två 1s, och sedan de blivit 2 också.

186
00:14:26,100 --> 00:14:31,570
Nu vet jag att mitt nästa steg kommer att gå det lägsta antalet,

187
00:14:31,570 --> 00:14:41,380
som är T, 1, och sedan välja en av de noder som har 2 som frekvensen.

188
00:14:41,380 --> 00:14:44,560
Så här har vi 3 alternativ.

189
00:14:44,560 --> 00:14:47,980
Vad jag ska göra för bilden är bara visuellt ändra dem åt dig

190
00:14:47,980 --> 00:14:51,790
så att du kan se hur jag bygger upp den.

191
00:14:51,790 --> 00:14:59,040
Vad koden och din distribution kod kommer att göra skulle gå med T en

192
00:14:59,040 --> 00:15:01,410
med 0 och 5 nod.

193
00:15:01,410 --> 00:15:05,060
Så då summor till 3 och sedan fortsätter vi processen.

194
00:15:05,060 --> 00:15:08,660
Den 2 och 2 är nu den lägsta, så då de belopp till 4.

195
00:15:08,660 --> 00:15:12,560
Alla följer hittills? Okej.

196
00:15:12,560 --> 00:15:16,410
Sedan efter att vi har 3 och 3 som behöver läggas upp,

197
00:15:16,410 --> 00:15:21,650
så igen jag bara byta den så att du kan se visuellt så att det inte blir för rörigt.

198
00:15:21,650 --> 00:15:25,740
Sedan har vi en 6, och sedan vår sista steget är nu att vi bara har 2 noder

199
00:15:25,740 --> 00:15:30,440
Vi summerar dem för att göra rot vår träd, vilket är 10.

200
00:15:30,440 --> 00:15:34,100
Och antalet 10 vettigt eftersom varje nod representerade,

201
00:15:34,100 --> 00:15:40,750
deras värde, deras frekvens nummer, var hur många gånger de dök upp i strängen,

202
00:15:40,750 --> 00:15:46,350
och sedan har vi 5 tecken i vår sträng, så det är vettigt.

203
00:15:48,060 --> 00:15:52,320
Om vi ​​tittar upp på hur vi faktiskt skulle koda det,

204
00:15:52,320 --> 00:15:56,580
som väntat, i-och s, som förekommer det oftast

205
00:15:56,580 --> 00:16:01,350
representeras av det minsta antalet bitar.

206
00:16:03,660 --> 00:16:05,660
>> Var försiktig här.

207
00:16:05,660 --> 00:16:09,780
I Huffman träd fallet betyder faktiskt.

208
00:16:09,780 --> 00:16:13,670
Ett versalt S är annorlunda än ett gement s..

209
00:16:13,670 --> 00:16:21,260
Om vi ​​hade "Detta är CS50" med versaler, då gement enda verkar två gånger,

210
00:16:21,260 --> 00:16:27,120
skulle vara en nod med 2 som dess värde, och sedan versaler S skulle bara vara en gång.

211
00:16:27,120 --> 00:16:33,440
Så då ditt träd skulle förändra strukturer eftersom du faktiskt har ett extra blad här.

212
00:16:33,440 --> 00:16:36,900
Men summan fortfarande skulle vara 10.

213
00:16:36,900 --> 00:16:39,570
Det är vad vi faktiskt kommer att vara ringa kontrollsumma,

214
00:16:39,570 --> 00:16:44,060
tillsats av samtliga räknas.

215
00:16:46,010 --> 00:16:50,990
>> Nu när vi har täckt Huffman träd, kan vi dyka in Huff'n Puff, den pset.

216
00:16:50,990 --> 00:16:52,900
Vi kommer att börja med en del av frågorna,

217
00:16:52,900 --> 00:16:57,990
och detta kommer att få dig van med binära träd och hur du använder runt det:

218
00:16:57,990 --> 00:17:03,230
ritning noder, skapa din egen typedef struct för en nod,

219
00:17:03,230 --> 00:17:07,230
och se hur du kan infoga i ett binärt träd, en som är sorterad,

220
00:17:07,230 --> 00:17:09,050
korsar den och sånt.

221
00:17:09,050 --> 00:17:14,560
Den kunskapen kommer definitivt att hjälpa dig när du dyker i Huff'n Puff delen

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

223
00:17:19,150 --> 00:17:26,329
I standardversionen av pset, är din uppgift att genomföra Puff,

224
00:17:26,329 --> 00:17:30,240
och i hacker versionen din uppgift är att genomföra Huff.

225
00:17:30,240 --> 00:17:38,490
Vad Huff gör är det tar text och sedan översätter det till 0 och 1,

226
00:17:38,490 --> 00:17:41,990
så den process som vi gjorde ovan där vi räknade frekvenserna

227
00:17:41,990 --> 00:17:50,970
och sedan gjorde trädet och sade sedan, "Hur får jag t?"

228
00:17:50,970 --> 00:17:54,840
T representeras av 100, saker,

229
00:17:54,840 --> 00:17:58,860
och sedan Huff skulle ta texten och sedan utgång som binär.

230
00:17:58,860 --> 00:18:04,920
Men också för att vi vet att vi vill att vår mottagare av meddelandet

231
00:18:04,920 --> 00:18:11,790
att återskapa exakt samma träd, innehåller den också information om frekvensen räknas.

232
00:18:11,790 --> 00:18:17,980
Sedan med Puff vi får en binär fil av 0 och 1

233
00:18:17,980 --> 00:18:21,740
och ges även information om frekvenserna.

234
00:18:21,740 --> 00:18:26,740
Vi översätter alla dessa 0 och 1 tillbaka till det ursprungliga meddelandet som var,

235
00:18:26,740 --> 00:18:29,350
så vi dekomprimering det.

236
00:18:29,350 --> 00:18:36,450
Om du gör det Standard Edition, behöver du inte genomföra Huff,

237
00:18:36,450 --> 00:18:39,290
så kan du bara använda den personal genomförandet av Huff.

238
00:18:39,290 --> 00:18:42,080
Det finns instruktioner i spec på hur man gör det.

239
00:18:42,080 --> 00:18:48,780
Du kan köra den personal genomförandet av Huff på en viss textfil

240
00:18:48,780 --> 00:18:53,270
och sedan använda denna utgång som din ingång till Puff.

241
00:18:53,270 --> 00:18:59,330
>> Som jag nämnde tidigare har vi en hel del utdelning kod för detta.

242
00:18:59,330 --> 00:19:01,810
Jag ska börja gå igenom den.

243
00:19:01,810 --> 00:19:04,400
Jag kommer att tillbringa större delen av tiden på. H-filer

244
00:19:04,400 --> 00:19:07,660
eftersom de. c-filer, eftersom vi har. h.

245
00:19:07,660 --> 00:19:11,650
och som ger oss med prototyper av de funktioner,

246
00:19:11,650 --> 00:19:15,520
vi inte helt behöver förstå exakt -

247
00:19:15,520 --> 00:19:20,280
Om du inte förstår vad som händer i de. C filerna ska du inte oroa dig för mycket,

248
00:19:20,280 --> 00:19:23,600
men definitivt försöka att ta en titt, eftersom det kan ge några tips

249
00:19:23,600 --> 00:19:29,220
och det är bra att vänja sig att läsa andra människors kod.

250
00:19:38,940 --> 00:19:48,270
>> Titta på huffile.h, i kommentarerna den förklarar ett lager av abstraktion för Huffman-kodade filer.

251
00:19:48,270 --> 00:20:01,660
Om vi ​​går ner, ser vi att det är högst 256 tecken som vi kanske behöver koder för.

252
00:20:01,660 --> 00:20:05,480
Detta inkluderar alla bokstäver i alfabetet - versaler och gemener -

253
00:20:05,480 --> 00:20:08,250
och sedan symboler och siffror, etc.

254
00:20:08,250 --> 00:20:11,930
Så här har vi ett magiskt nummer som identifierar en Huffman-kodad fil.

255
00:20:11,930 --> 00:20:15,890
Inom en huffmankod de ska ha ett visst magiskt tal

256
00:20:15,890 --> 00:20:18,560
associerad med huvudet.

257
00:20:18,560 --> 00:20:21,110
Detta kan se ut som bara en slumpmässig magiskt nummer,

258
00:20:21,110 --> 00:20:27,160
men om du verkligen översätta det till ASCII, då stavar faktiskt ut Huff.

259
00:20:27,160 --> 00:20:34,290
Här har vi en struct för en Huffman-kodad fil.

260
00:20:34,290 --> 00:20:39,670
Det finns alla dessa egenskaper som en Huff fil.

261
00:20:39,670 --> 00:20:47,080
Sen här nere har vi rubriken för en Huff fil, så vi kallar det Huffeader

262
00:20:47,080 --> 00:20:50,810
stället för att lägga den extra h eftersom det låter lika ändå.

263
00:20:50,810 --> 00:20:52,720
Söt.

264
00:20:52,720 --> 00:20:57,790
Vi har ett magiskt nummer associerade med den.

265
00:20:57,790 --> 00:21:09,040
Om det är en verklig Huff fil, kommer det att vara nummer upp ovan denna magiska en.

266
00:21:09,040 --> 00:21:14,720
Och så kommer det att ha en array.

267
00:21:14,720 --> 00:21:18,750
Så för varje symbol, av vilka det finns 256,

268
00:21:18,750 --> 00:21:24,760
det kommer att lista vad Frekvensen av dessa symboler inom Huff filen.

269
00:21:24,760 --> 00:21:28,090
Och slutligen har vi en kontrollsumma för frekvenserna,

270
00:21:28,090 --> 00:21:32,160
som bör vara summan av dessa frekvenser.

271
00:21:32,160 --> 00:21:36,520
Så det är vad en Huffeader är.

272
00:21:36,520 --> 00:21:44,600
Sedan har vi några funktioner som returnerar nästa bit i Huff filen

273
00:21:44,600 --> 00:21:52,580
samt skriver lite till Huff filen och sedan denna funktion här,, hfclose

274
00:21:52,580 --> 00:21:54,650
som stänger faktiskt Huff filen.

275
00:21:54,650 --> 00:21:57,290
Förut var vi att göra med rakt bara fclose,

276
00:21:57,290 --> 00:22:01,190
men när du har en Huff fil, i stället för att fclosing det

277
00:22:01,190 --> 00:22:06,080
vad du egentligen ska göra är hfclose och hfopen det.

278
00:22:06,080 --> 00:22:13,220
De är specifika funktioner till Huff filer som vi kommer att ha att göra med.

279
00:22:13,220 --> 00:22:19,230
Så här vi läser i huvudet och sedan skriva rubriken.

280
00:22:19,230 --> 00:22:25,700
>> Bara genom att läsa. H. filen kan vi slags få en känsla för vad en Huff fil kan vara,

281
00:22:25,700 --> 00:22:32,480
vilka egenskaper den har, utan att faktiskt gå in i huffile.c,

282
00:22:32,480 --> 00:22:36,750
som, om vi dyka i, kommer att vara lite mer komplicerat.

283
00:22:36,750 --> 00:22:41,270
Den har alla de I / O-här behandlar pekare.

284
00:22:41,270 --> 00:22:48,010
Här ser vi att när vi kallar hfread till exempel, det är fortfarande arbetar med fread.

285
00:22:48,010 --> 00:22:53,050
Vi ska inte bli av med dessa funktioner helt, men vi skickar dem tas om hand

286
00:22:53,050 --> 00:22:59,760
inuti Huff fil i stället för att göra allt det själva.

287
00:22:59,760 --> 00:23:02,300
Du kan gärna söka igenom detta om du är nyfiken

288
00:23:02,300 --> 00:23:08,410
och gå och skala lagret tillbaka lite.

289
00:23:20,650 --> 00:23:24,060
>> Nästa fil som vi kommer att titta på är tree.h.

290
00:23:24,060 --> 00:23:30,210
Tidigare i Walkthrough glider vi sagt att vi förväntar oss en Huffman nod

291
00:23:30,210 --> 00:23:32,960
och vi gjorde en typedef struct nod.

292
00:23:32,960 --> 00:23:38,360
Vi räknar med att ha en symbol, en frekvens, och sedan 2 stjärnor noden.

293
00:23:38,360 --> 00:23:41,870
I det här fallet vad vi gör är att detta är i stort sett samma

294
00:23:41,870 --> 00:23:46,880
utom i stället för nod ska vi kalla dem träd.

295
00:23:48,790 --> 00:23:56,760
Vi har en funktion som när du ringer gör träd returneras dig ett träd pekare.

296
00:23:56,760 --> 00:24:03,450
Tillbaka till Speller, när du gör en ny nod

297
00:24:03,450 --> 00:24:11,410
du sa nod * nytt ord = malloc (sizeof) och sådana saker.

298
00:24:11,410 --> 00:24:17,510
I grund och botten är mktree kommer att ha att göra med det för dig.

299
00:24:17,510 --> 00:24:20,990
Likaså när du vill ta bort ett träd,

300
00:24:20,990 --> 00:24:24,810
så som i huvudsak är att befria trädet när du är klar med det,

301
00:24:24,810 --> 00:24:33,790
i stället för att uttryckligen kalla fritt på det, är du faktiskt bara att använda funktionen rmtree

302
00:24:33,790 --> 00:24:40,360
där du passerar i pekaren till det trädet och sedan tree.c tar hand om det åt dig.

303
00:24:40,360 --> 00:24:42,490
>> Vi ser på tree.c.

304
00:24:42,490 --> 00:24:47,240
Vi förväntar oss samma funktioner förutom att se genomförandet också.

305
00:24:47,240 --> 00:24:57,720
Som vi väntat, när du ringer mktree det mallocs storleken av ett träd i en pekare,

306
00:24:57,720 --> 00:25:03,190
initierar alla värden till det NULL värde, så 0s eller nollor,

307
00:25:03,190 --> 00:25:08,280
och återgår sedan pekaren till det trädet som du bara har malloc'd till dig.

308
00:25:08,280 --> 00:25:13,340
Här när du ringer bort träd det gör först kontrollera att du inte dubbla är att befria.

309
00:25:13,340 --> 00:25:18,320
Det ser till att du faktiskt har ett träd som du vill ta bort.

310
00:25:18,320 --> 00:25:23,330
Här eftersom ett träd innefattar även dess barn,

311
00:25:23,330 --> 00:25:29,560
Vad detta innebär är man kallar rekursivt ta bort träd på vänster nod i trädet

312
00:25:29,560 --> 00:25:31,650
liksom rätt noden.

313
00:25:31,650 --> 00:25:37,790
Innan det frigör förälder måste det frigöra barnen också.

314
00:25:37,790 --> 00:25:42,770
Moderbolaget är även utbytbar med root.

315
00:25:42,770 --> 00:25:46,500
Den första föräldern, så som den store-store-store-store-farfar

316
00:25:46,500 --> 00:25:52,130
eller mormor träd, först måste vi frigöra ner nivåerna först.

317
00:25:52,130 --> 00:25:58,490
Så korsar till botten, fri dem, och sedan komma tillbaka upp, utan dem, etc.

318
00:26:00,400 --> 00:26:02,210
Så det är trädet.

319
00:26:02,210 --> 00:26:04,240
>> Nu tittar vi på skogen.

320
00:26:04,240 --> 00:26:09,860
Forest är där du placerar alla dina Huffman träd.

321
00:26:09,860 --> 00:26:12,910
Det säger att vi kommer att ha något som kallas en tomt

322
00:26:12,910 --> 00:26:22,320
som innehåller en pekare till ett träd och en pekare till en tomt som kallas nästa.

323
00:26:22,320 --> 00:26:28,480
Vilken struktur gör denna typ av ut?

324
00:26:29,870 --> 00:26:32,490
Det slags säger där borta.

325
00:26:34,640 --> 00:26:36,700
Här borta.

326
00:26:37,340 --> 00:26:39,170
En länkad lista.

327
00:26:39,170 --> 00:26:44,590
Vi ser att när vi har en tomt är det som en länkad lista av tomter.

328
00:26:44,590 --> 00:26:53,020
En skog definieras som en länkad lista av tomter,

329
00:26:53,020 --> 00:26:58,100
och så struktur skogen är vi bara kommer att ha en pekare till vår första tomten

330
00:26:58,100 --> 00:27:02,740
och att tomten har ett träd i den, eller snarare pekar på ett träd

331
00:27:02,740 --> 00:27:06,190
och sedan pekar på nästa tomt, så vidare och så vidare.

332
00:27:06,190 --> 00:27:11,100
För att göra en skog som vi kallar mkforest.

333
00:27:11,100 --> 00:27:14,930
Sedan har vi några ganska användbara funktioner här.

334
00:27:14,930 --> 00:27:23,240
Vi har plocka där du passerar i en skog och sedan returvärdet är ett träd *,

335
00:27:23,240 --> 00:27:25,210
en pekare till ett träd.

336
00:27:25,210 --> 00:27:29,370
Hur pick gör det kommer att gå in i skogen som du pekar på

337
00:27:29,370 --> 00:27:35,240
sedan bort ett träd med den lägsta frekvensen från skogen

338
00:27:35,240 --> 00:27:38,330
och sedan ge dig pekaren till det trädet.

339
00:27:38,330 --> 00:27:43,030
När du ringer plocka, kommer trädet finns inte i skogen längre,

340
00:27:43,030 --> 00:27:48,550
men returvärdet är pekaren till det trädet.

341
00:27:48,550 --> 00:27:50,730
Då har du växt.

342
00:27:50,730 --> 00:27:57,420
Förutsatt att du skickar in en pekare till ett träd som har en icke-0 frekvens,

343
00:27:57,420 --> 00:28:04,040
hur anläggningen kommer att göra är det kommer att ta skogen, ta trädet, och plantera det trädet inne i skogen.

344
00:28:04,040 --> 00:28:06,370
Här har vi rmforest.

345
00:28:06,370 --> 00:28:11,480
I likhet med avlägsna träd, som i princip befriade alla våra träd för oss,

346
00:28:11,480 --> 00:28:16,600
ta bort skog kommer fri allt som står i skogen.

347
00:28:16,600 --> 00:28:24,890
>> Om vi ​​tittar på forest.c, vi förväntar oss att se minst 1 rmtree kommando där,

348
00:28:24,890 --> 00:28:30,090
eftersom att frigöra minne i skogen om en skog har träd i den,

349
00:28:30,090 --> 00:28:32,930
så småningom du kommer att behöva ta bort dessa träd också.

350
00:28:32,930 --> 00:28:41,020
Om vi ​​tittar på forest.c har vi vår mkforest, vilket är som vi förväntar oss.

351
00:28:41,020 --> 00:28:42,890
Vi malloc saker.

352
00:28:42,890 --> 00:28:51,740
Vi initiera den första tomten i skogen som NULL eftersom det är tomt till att börja med,

353
00:28:51,740 --> 00:29:05,940
då ser vi plocka, som returnerar trädet med den lägsta vikten, den lägsta frekvensen,

354
00:29:05,940 --> 00:29:13,560
och sedan gör sig av just nod som pekar på att trädet och nästa en,

355
00:29:13,560 --> 00:29:16,760
så det tar att av den länkade listan av skogen.

356
00:29:16,760 --> 00:29:24,510
Och så här har vi växt, som infogar ett träd i den länkade listan.

357
00:29:24,510 --> 00:29:29,960
Vilken skog gör är det snyggt håller det sorteras för oss.

358
00:29:29,960 --> 00:29:37,910
Och slutligen har vi rmforest och som väntat har vi rmtree kallas där.

359
00:29:46,650 --> 00:29:55,440
>> Man tittar på fördelningen koden så långt var huffile.c förmodligen den absolut svåraste att förstå,

360
00:29:55,440 --> 00:29:59,990
medan de andra filerna själva var ganska enkla att följa.

361
00:29:59,990 --> 00:30:03,090
Med vår kunskap om pekare och länkade listor och sådant,

362
00:30:03,090 --> 00:30:04,860
vi kunde följa ganska bra.

363
00:30:04,860 --> 00:30:10,500
Men allt vi behöver verkligen se till att vi förstår är det. H-filer

364
00:30:10,500 --> 00:30:15,840
eftersom du måste ringa dessa funktioner, som handlar om de returvärden,

365
00:30:15,840 --> 00:30:20,590
så se till att du till fullo förstår vilka åtgärder kommer att genomföras

366
00:30:20,590 --> 00:30:24,290
när du ringer ett av dessa funktioner.

367
00:30:24,290 --> 00:30:33,020
Men egentligen förstå inuti det inte helt nödvändigt eftersom vi har dem. H-filer.

368
00:30:35,170 --> 00:30:39,490
Vi har 2 fler filer kvar i vår distribution kod.

369
00:30:39,490 --> 00:30:41,640
>> Låt oss titta på soptippen.

370
00:30:41,640 --> 00:30:47,230
Dumpa genom sin kommentar här tar Huffman-komprimerad fil

371
00:30:47,230 --> 00:30:55,580
och sedan översätter och dumpar allt innehåll ut.

372
00:31:01,010 --> 00:31:04,260
Här ser vi att det ringer hfopen.

373
00:31:04,260 --> 00:31:10,770
Detta är typ av spegling att lämna * ingång = fopen,

374
00:31:10,770 --> 00:31:13,500
och då du passerar i informationen.

375
00:31:13,500 --> 00:31:18,240
Det är nästan identiska med undantag istället för en fil * du passerar en Huffile,

376
00:31:18,240 --> 00:31:22,030
istället för fopen du passerar i hfopen.

377
00:31:22,030 --> 00:31:29,280
Här läser vi i huvudet först, vilket är typ av liknar hur vi läser i huvudet

378
00:31:29,280 --> 00:31:33,580
för en bitmappsfil.

379
00:31:33,580 --> 00:31:38,000
Vad vi gör här är att kontrollera för att se om rubrikinformationen

380
00:31:38,000 --> 00:31:44,330
innehåller rätt magiska nummer som anger att det är en verklig Huff fil,

381
00:31:44,330 --> 00:31:53,610
då alla dessa kontroller för att se till att filen som vi öppen är en verklig blåste fil eller inte.

382
00:31:53,610 --> 00:32:05,330
Vad detta innebär är det matar frekvenserna för alla de symboler som vi kan se

383
00:32:05,330 --> 00:32:09,790
inom en terminal i en grafisk tabell.

384
00:32:09,790 --> 00:32:15,240
Denna del kommer att vara användbar.

385
00:32:15,240 --> 00:32:24,680
Den har en lite och läser bit för bit in i variabel bit och sedan skriver ut det.

386
00:32:28,220 --> 00:32:35,430
Så om jag skulle kalla dump den hth.bin, som är resultatet av huffing en fil

387
00:32:35,430 --> 00:32:39,490
med personal lösningen, skulle jag få detta.

388
00:32:39,490 --> 00:32:46,000
Det mata alla dessa tecken och sedan sätta den frekvens med vilken de visas.

389
00:32:46,000 --> 00:32:51,180
Om vi ​​ser, de flesta av dem är 0s förutom detta: H, som visas två gånger,

390
00:32:51,180 --> 00:32:54,820
och sedan T, som visas en gång.

391
00:32:54,820 --> 00:33:07,860
Och så här har vi själva meddelandet i 0 och 1.

392
00:33:07,860 --> 00:33:15,450
Om vi ​​tittar på hth.txt, vilket förmodligen det ursprungliga meddelandet som blåste,

393
00:33:15,450 --> 00:33:22,490
Vi förväntar oss att se några Hs och Ts där.

394
00:33:22,490 --> 00:33:28,720
Specifikt förväntar vi oss att se bara 1 T och 2 HS.

395
00:33:32,510 --> 00:33:37,440
Här är vi i hth.txt. Det har verkligen HTH.

396
00:33:37,440 --> 00:33:41,270
Ingår i det, även om vi inte kan se det, är ett radmatningstecken.

397
00:33:41,270 --> 00:33:53,190
Den Huff Filen hth.bin också kodar för nyradstecken också.

398
00:33:55,680 --> 00:34:01,330
Här eftersom vi vet att ordern är HTH och sedan nyrad,

399
00:34:01,330 --> 00:34:07,340
kan vi se att förmodligen H representeras av bara en enda 1

400
00:34:07,340 --> 00:34:17,120
och då T är troligen 01 och sedan nästa H är 1 samt

401
00:34:17,120 --> 00:34:21,139
och sedan har vi en nyrad anges med två 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Och slutligen, eftersom vi har att göra med flera. C och. H-filer,

404
00:34:31,600 --> 00:34:36,350
vi kommer att ha en ganska komplex argument till kompilatorn,

405
00:34:36,350 --> 00:34:40,460
och så här har vi en Makefile som gör dumpa dig.

406
00:34:40,460 --> 00:34:47,070
Men faktiskt, måste du gå om att göra din egen puff.c fil.

407
00:34:47,070 --> 00:34:54,330
Makefile faktiskt inte behandlar göra puff.c för dig.

408
00:34:54,330 --> 00:34:59,310
Vi lämnar det upp till dig att redigera Makefile.

409
00:34:59,310 --> 00:35:05,930
När du anger ett kommando som gör allt, till exempel, kommer det att göra dem alla till dig.

410
00:35:05,930 --> 00:35:10,760
Känn dig fri att titta på exempel på Makefile från tidigare pset

411
00:35:10,760 --> 00:35:17,400
liksom att gå bort av denna för att se hur du skulle kunna göra ditt Puff fil

412
00:35:17,400 --> 00:35:20,260
genom att redigera den här Makefile.

413
00:35:20,260 --> 00:35:22,730
Det är ungefär det för vår distribution kod.

414
00:35:22,730 --> 00:35:28,380
>> När vi har fått igenom det, så här är bara en påminnelse

415
00:35:28,380 --> 00:35:30,980
hur vi ska ha att göra med Huffman noderna.

416
00:35:30,980 --> 00:35:35,400
Vi kommer inte att kalla dem noder längre, vi kommer att kalla dem träd

417
00:35:35,400 --> 00:35:39,260
där vi kommer att representera sin symbol med en röding,

418
00:35:39,260 --> 00:35:43,340
deras frekvens, antalet förekomster, med ett heltal.

419
00:35:43,340 --> 00:35:47,370
Vi använder det för att det är mer exakt än en flottör.

420
00:35:47,370 --> 00:35:52,980
Och då vi har en annan pekaren till vänster barnet samt rätt barn.

421
00:35:52,980 --> 00:35:59,630
En skog, som vi såg, är bara en länkad lista av träd.

422
00:35:59,630 --> 00:36:04,670
I slutändan, när vi bygger upp vår Huff fil,

423
00:36:04,670 --> 00:36:07,580
Vi vill att vår skog ska innehålla bara 1 träd -

424
00:36:07,580 --> 00:36:12,420
1 träd, 1 rot med flera barn.

425
00:36:12,420 --> 00:36:20,840
Tidigare när vi bara göra våra Huffman träd,

426
00:36:20,840 --> 00:36:25,360
Vi började genom att placera alla noder på vår skärm

427
00:36:25,360 --> 00:36:27,790
och säger att vi ska ha dessa noder,

428
00:36:27,790 --> 00:36:32,920
Så småningom ska bli bladen, och detta är deras symbol, det är deras frekvens.

429
00:36:32,920 --> 00:36:42,070
I vår skog om vi bara har 3 bokstäver, det är en skog av 3 träd.

430
00:36:42,070 --> 00:36:45,150
Och sedan när vi går på, när vi lagt den första föräldern,

431
00:36:45,150 --> 00:36:48,080
Vi gjorde en skog av 2 träd.

432
00:36:48,080 --> 00:36:54,930
Vi bort 2 av dessa barn från vår skog och ersatt det med en förälder nod

433
00:36:54,930 --> 00:36:58,820
som hade de 2 noder som barn.

434
00:36:58,820 --> 00:37:05,600
Och sedan slutligen, vår sista steget med att göra vårt exempel med As, B, och Cs

435
00:37:05,600 --> 00:37:08,030
skulle vara att göra det slutliga moderbolaget,

436
00:37:08,030 --> 00:37:13,190
och så då skulle föra vår totala räkningen på träd i skogen till 1.

437
00:37:13,190 --> 00:37:18,140
Ser alla hur du börjar med flera träd i skogen

438
00:37:18,140 --> 00:37:22,520
och sluta med 1? Okej. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Vad behöver vi göra för Puff?

440
00:37:28,110 --> 00:37:37,110
Vad vi behöver göra är att se till att, som alltid, de ger oss rätt typ av ingång

441
00:37:37,110 --> 00:37:39,090
så att vi verkligen kan köra programmet.

442
00:37:39,090 --> 00:37:43,130
I detta fall kommer att ge oss efter deras första kommandoradsargument

443
00:37:43,130 --> 00:37:53,440
2 mer: den fil som vi vill expandera och utgången där den uppackade filen.

444
00:37:53,440 --> 00:38:00,410
Men när vi ser till att de passerar oss i rätt mängd värden,

445
00:38:00,410 --> 00:38:05,820
Vi vill se till att ingången är en Huff fil eller inte.

446
00:38:05,820 --> 00:38:10,420
Och sedan när vi garantera att det är en Huff fil, så vi vill bygga vårt träd,

447
00:38:10,420 --> 00:38:20,940
bygga upp trädet så att det matchar trädet att den person som skickade meddelandet byggas.

448
00:38:20,940 --> 00:38:25,840
Sedan efter vi bygger trädet, då kan vi ta itu med 0 och 1 som de gått i,

449
00:38:25,840 --> 00:38:29,590
Följ dem längs vår träd eftersom det är identiskt,

450
00:38:29,590 --> 00:38:33,510
och sedan skriva det budskap, tolka bitarna tillbaka i tecken.

451
00:38:33,510 --> 00:38:35,880
Och sedan i slutet eftersom vi har att göra med pekare här,

452
00:38:35,880 --> 00:38:38,110
Vi vill se till att vi inte har några minnesläckor

453
00:38:38,110 --> 00:38:41,330
och att vi gratis allt.

454
00:38:42,820 --> 00:38:46,430
>> Korrekt användning är gammal hatt för oss nu.

455
00:38:46,430 --> 00:38:51,980
Vi tar in en ingång, vilket kommer att bli namnet på filen att blåsa,

456
00:38:51,980 --> 00:38:56,010
och då vi anger en utgång,

457
00:38:56,010 --> 00:39:01,580
så namnet på filen för den puffade utmatning, som kommer att vara textfilen.

458
00:39:03,680 --> 00:39:08,820
Det är användningen. Och nu vill vi se till att ingången är huffed eller inte.

459
00:39:08,820 --> 00:39:16,420
Tänka tillbaka, var det något i distributionen kod som kan hjälpa oss

460
00:39:16,420 --> 00:39:21,570
med att förstå om en fil blåste eller inte?

461
00:39:21,570 --> 00:39:26,910
Det var information i huffile.c om Huffeader.

462
00:39:26,910 --> 00:39:33,430
Vi vet att varje Huff filen har en Huffeader i samband med det ett magiskt nummer

463
00:39:33,430 --> 00:39:37,240
såväl som en array av frekvenserna för varje symbol

464
00:39:37,240 --> 00:39:39,570
samt en kontrollsumma.

465
00:39:39,570 --> 00:39:43,180
Vi vet det, men vi tog också en titt på dump.c,

466
00:39:43,180 --> 00:39:49,120
där det läsa in en Huff fil.

467
00:39:49,120 --> 00:39:53,990
Och så för att göra det, måste den kontrollera om det verkligen var blåste eller inte.

468
00:39:53,990 --> 00:40:03,380
Så kanske vi kunde använda dump.c som en struktur för vår puff.c.

469
00:40:03,380 --> 00:40:12,680
Tillbaka till pset 4 när vi hade filen copy.c som kopieras i RGB tripplar

470
00:40:12,680 --> 00:40:14,860
och vi tolkade det för DECKARE och ändra storlek,

471
00:40:14,860 --> 00:40:20,390
liknande, vad du kan göra bara köra kommandot som cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
och använda en del av koden där.

473
00:40:23,600 --> 00:40:28,210
Men, det kommer inte att vara så enkelt för en process

474
00:40:28,210 --> 00:40:33,010
för översättning din dump.c till puff.c,

475
00:40:33,010 --> 00:40:36,160
men åtminstone det ger dig någonstans att börja

476
00:40:36,160 --> 00:40:40,540
om hur man kan säkerställa att ingången faktiskt blåste eller inte

477
00:40:40,540 --> 00:40:43,240
liksom några andra saker.

478
00:40:45,930 --> 00:40:50,250
Vi har säkerställt korrekt användning och se till att ingången är huffed.

479
00:40:50,250 --> 00:40:53,570
Varje gång vi har gjort att vi har gjort vårt rätta felkontroll,

480
00:40:53,570 --> 00:41:01,520
så tillbaka och avsluta funktionen om något fel uppstår, om det finns ett problem.

481
00:41:01,520 --> 00:41:07,170
>> Nu vad vi vill göra är att bygga själva trädet.

482
00:41:08,840 --> 00:41:12,640
Om vi ​​tittar i Forest finns 2 huvudfunktioner

483
00:41:12,640 --> 00:41:15,800
att vi kommer att vilja bli väl förtrogen med.

484
00:41:15,800 --> 00:41:23,870
Det är den booleska funktionen växt som växter en icke-0 frekvens träd inne vår skog.

485
00:41:23,870 --> 00:41:29,250
Och så det du skickar i en pekare till en skog och en pekare till ett träd.

486
00:41:32,530 --> 00:41:40,340
Snabb fråga: Hur många skogar har du när du bygger en Huffman träd?

487
00:41:44,210 --> 00:41:46,650
Vår skog är som vår duk, eller hur?

488
00:41:46,650 --> 00:41:50,800
Så vi bara kommer att ha 1 skog, men vi kommer att ha flera träd.

489
00:41:50,800 --> 00:41:57,590
Så innan du ringer växt, du kommer förmodligen att vilja göra din skog.

490
00:41:57,590 --> 00:42:04,430
Det finns ett kommando för att om du tittar in forest.h på hur du kan göra en skog.

491
00:42:04,430 --> 00:42:09,270
Du kan plantera ett träd. Vi vet hur man gör det.

492
00:42:09,270 --> 00:42:11,590
Och då kan du också välja ett träd från skogen,

493
00:42:11,590 --> 00:42:17,540
bort ett träd med den lägsta vikt och ger dig pekaren till det.

494
00:42:17,540 --> 00:42:23,090
Tänker tillbaka på när vi gjorde de exempel själva,

495
00:42:23,090 --> 00:42:27,980
när vi drar ut, vi helt enkelt bara lagt till länkar.

496
00:42:27,980 --> 00:42:31,680
Men här i stället för att bara lägga länkarna,

497
00:42:31,680 --> 00:42:40,630
tänka på det mer som du tar bort 2 av dessa noder och sedan ersätta den med en annan.

498
00:42:40,630 --> 00:42:44,200
För att uttrycka det i termer av att plocka och plantera,

499
00:42:44,200 --> 00:42:48,840
du plockar 2 träd och sedan plantera ett annat träd

500
00:42:48,840 --> 00:42:54,060
som har de 2 träd som du plockat som barn.

501
00:42:57,950 --> 00:43:05,280
Att bygga Huffman s träd, kan du läsa i symboler och frekvenser för

502
00:43:05,280 --> 00:43:10,790
eftersom Huffeader ger det till dig,

503
00:43:10,790 --> 00:43:14,250
ger dig en rad av frekvenserna.

504
00:43:14,250 --> 00:43:19,660
Så du kan gå vidare och bara ignorera något med 0 i det

505
00:43:19,660 --> 00:43:23,760
eftersom vi inte vill 256 blad i slutet av den.

506
00:43:23,760 --> 00:43:27,960
Vi vill bara antalet blad som är tecken

507
00:43:27,960 --> 00:43:31,600
som faktiskt används i filen.

508
00:43:31,600 --> 00:43:37,590
Du kan läsa i dessa symboler, och var och en av dessa symboler som har icke-0 frekvenser,

509
00:43:37,590 --> 00:43:40,440
de kommer att bli träd.

510
00:43:40,440 --> 00:43:45,990
Vad du kan göra är varje gång du läser i en icke-0 frekvens symbol,

511
00:43:45,990 --> 00:43:50,660
du kan plantera det där trädet i skogen.

512
00:43:50,660 --> 00:43:56,620
När du plantera träden i skogen, kan du gå med dessa träd som syskon,

513
00:43:56,620 --> 00:44:01,130
så gå tillbaka till plantering och plocka där du väljer 2 och sedan växt 1,

514
00:44:01,130 --> 00:44:05,820
om detta 1 att du planterar är förälder till de 2 barnen som du plockat.

515
00:44:05,820 --> 00:44:11,160
Så då din slutresultatet kommer att bli ett enda träd i skogen.

516
00:44:16,180 --> 00:44:18,170
Det är hur du bygger ditt träd.

517
00:44:18,170 --> 00:44:21,850
>> Det finns flera saker som kan gå fel här

518
00:44:21,850 --> 00:44:26,580
eftersom vi har att göra med att göra nya träd och hantera pekare och sånt.

519
00:44:26,580 --> 00:44:30,450
Innan när vi hade att göra med pekare,

520
00:44:30,450 --> 00:44:36,580
när vi malloc'd vi ville se till att det inte returnera oss en NULL-pekare värde.

521
00:44:36,580 --> 00:44:42,770
Så vid flera steg i denna process det kommer att bli flera fall

522
00:44:42,770 --> 00:44:45,920
där ditt program kan misslyckas.

523
00:44:45,920 --> 00:44:51,310
Vad du vill göra är att du vill vara säker på att du hanterar dessa fel,

524
00:44:51,310 --> 00:44:54,580
och i spec står att hantera dem graciöst,

525
00:44:54,580 --> 00:45:00,280
så vill skriva ut ett meddelande till användaren berätta varför programmet måste sluta

526
00:45:00,280 --> 00:45:03,050
och sedan omgående avsluta det.

527
00:45:03,050 --> 00:45:09,490
För att göra detta felhantering, kom ihåg att du vill kontrollera den

528
00:45:09,490 --> 00:45:12,160
varje gång att det kan finnas ett fel.

529
00:45:12,160 --> 00:45:14,660
Varenda gång du gör en ny pekare

530
00:45:14,660 --> 00:45:17,040
du vill vara säker på att det är framgångsrikt.

531
00:45:17,040 --> 00:45:20,320
Innan vad vi brukade göra är att göra en ny pekare och malloc det,

532
00:45:20,320 --> 00:45:22,380
och då skulle vi kontrollera huruvida pekaren är NULL.

533
00:45:22,380 --> 00:45:25,670
Så det kommer att bli några fall där du bara kan göra det,

534
00:45:25,670 --> 00:45:28,610
men ibland du faktiskt ringer en funktion

535
00:45:28,610 --> 00:45:33,100
och inom den funktionen, det är den som gör det mallocing.

536
00:45:33,100 --> 00:45:39,110
I så fall, om vi ser tillbaka till vissa funktioner i koden,

537
00:45:39,110 --> 00:45:42,260
några av dem är booleska funktioner.

538
00:45:42,260 --> 00:45:48,480
I det abstrakta fallet om vi har en boolesk funktion som kallas foo,

539
00:45:48,480 --> 00:45:54,580
I princip kan vi anta att förutom att göra allt foo gör,

540
00:45:54,580 --> 00:45:57,210
eftersom det är ett booleskt funktion returnerar det sant eller falskt -

541
00:45:57,210 --> 00:46:01,300
sant om det lyckas, falskt om inte.

542
00:46:01,300 --> 00:46:06,270
Så vi vill kontrollera om returvärdet av foo är sant eller falskt.

543
00:46:06,270 --> 00:46:10,400
Om det är falskt, det betyder att vi kommer att vilja skriva ut någon form av meddelande

544
00:46:10,400 --> 00:46:14,390
och avsluta programmet.

545
00:46:14,390 --> 00:46:18,530
Vad vi vill göra är att kontrollera returvärdet foo.

546
00:46:18,530 --> 00:46:23,310
Om foo returnerar false, då vi vet att vi stött på någon typ av fel

547
00:46:23,310 --> 00:46:25,110
och vi måste avsluta vårt program.

548
00:46:25,110 --> 00:46:35,600
Ett sätt att göra detta är att ha ett tillstånd där den faktiska funktionen i sig är ditt tillstånd.

549
00:46:35,600 --> 00:46:39,320
Säg foo tar i x.

550
00:46:39,320 --> 00:46:43,390
Vi kan ha som ett villkor om (foo (x)).

551
00:46:43,390 --> 00:46:50,900
I grund och botten innebär att om i slutet av köra foo den returnerar sant,

552
00:46:50,900 --> 00:46:57,390
då kan vi göra detta eftersom funktionen måste utvärdera foo

553
00:46:57,390 --> 00:47:00,500
För att utvärdera hela tillståndet.

554
00:47:00,500 --> 00:47:06,500
Så då det är hur du kan göra något om funktionen returnerar true och är framgångsrik.

555
00:47:06,500 --> 00:47:11,800
Men när du är felkontroll, vill du bara sluta om din funktion returnerar false.

556
00:47:11,800 --> 00:47:16,090
Vad du kan göra är att lägga bara en == falska eller bara lägga en smäll framför den

557
00:47:16,090 --> 00:47:21,010
och då har du if (! foo).

558
00:47:21,010 --> 00:47:29,540
I detta organ av detta villkor du skulle ha alla felhantering,

559
00:47:29,540 --> 00:47:36,940
så vill, "Kunde inte skapa detta träd" och sedan återvända 1 eller något liknande.

560
00:47:36,940 --> 00:47:43,340
Vad som gör, är dock att även om foo återvände falskt -

561
00:47:43,340 --> 00:47:46,980
Säg foo returnerar true.

562
00:47:46,980 --> 00:47:51,060
Då behöver du inte ringa foo igen. Det är en vanlig missuppfattning.

563
00:47:51,060 --> 00:47:54,730
Eftersom det var i ditt tillstånd, det redan utvärderats,

564
00:47:54,730 --> 00:47:59,430
så har du redan ett resultat om du använder gör träd eller något liknande

565
00:47:59,430 --> 00:48:01,840
eller växt eller plocka eller något.

566
00:48:01,840 --> 00:48:07,460
Det har redan detta värde. Det är redan körs.

567
00:48:07,460 --> 00:48:10,730
Så det är bra att använda booleska funktioner som villkoret

568
00:48:10,730 --> 00:48:13,890
eftersom om du faktiskt utföra kroppen av slingan,

569
00:48:13,890 --> 00:48:18,030
den utför funktionen ändå.

570
00:48:22,070 --> 00:48:27,330
>> Vår näst sista steget är att skriva meddelandet till filen.

571
00:48:27,330 --> 00:48:33,070
När vi bygga Huffman träd, och sedan skriva meddelandet till filen är ganska enkelt.

572
00:48:33,070 --> 00:48:39,260
Det är ganska enkelt nu att bara följa 0 och 1.

573
00:48:39,260 --> 00:48:45,480
Och så genom konvention vet vi att i en Huffman trädet 0s indikerar kvar

574
00:48:45,480 --> 00:48:48,360
och 1s anger rätt.

575
00:48:48,360 --> 00:48:53,540
Så då om du läser i bit för bit, varje gång du får en 0

576
00:48:53,540 --> 00:48:59,100
du följa den vänstra grenen, och sedan varje gång du läser i en 1

577
00:48:59,100 --> 00:49:02,100
du kommer att följa den rätta grenen.

578
00:49:02,100 --> 00:49:07,570
Och då du kommer att fortsätta tills du träffar ett löv

579
00:49:07,570 --> 00:49:11,550
eftersom bladen kommer att vara i slutet av grenarna.

580
00:49:11,550 --> 00:49:16,870
Hur kan vi berätta om vi har träffat en löv eller inte?

581
00:49:19,800 --> 00:49:21,690
Vi sa det innan.

582
00:49:21,690 --> 00:49:24,040
[Eleven] Om pekare är NULL. >> Ja.

583
00:49:24,040 --> 00:49:32,220
Vi kan berätta om vi har drabbats ett löv om pekare till både vänster och höger träd är NULL.

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

585
00:49:34,110 --> 00:49:40,320
Vi vet att vi vill läsa i bit för bit i vår Huff fil.

586
00:49:43,870 --> 00:49:51,220
Som vi såg tidigare i dump.c, är vad de gjorde de läser i bit för bit in i Huff filen

587
00:49:51,220 --> 00:49:54,560
och bara skrivas ut vad dessa bitar var.

588
00:49:54,560 --> 00:49:58,430
Vi kommer inte att göra det. Vi kommer att göra något som är lite mer komplicerat.

589
00:49:58,430 --> 00:50:03,620
Men vad vi kan göra är att vi kan ta det lite kod som läser in i lite.

590
00:50:03,620 --> 00:50:10,250
Här har vi heltalet bit representerar den aktuella biten som vi är på.

591
00:50:10,250 --> 00:50:15,520
Detta tar hand om iterera alla bitar i filen tills du träffar i slutet av filen.

592
00:50:15,520 --> 00:50:21,270
Baserat på det, då du kommer att vilja ha någon form av iterator

593
00:50:21,270 --> 00:50:26,760
att korsa ditt träd.

594
00:50:26,760 --> 00:50:31,460
Och sedan baserat på huruvida biten är 0 eller 1,

595
00:50:31,460 --> 00:50:36,920
du kommer att vilja antingen flytta den iterator till vänster eller flytta det åt höger

596
00:50:36,920 --> 00:50:44,080
ända tills du träffar ett löv, så hela vägen tills den nod som du är på

597
00:50:44,080 --> 00:50:48,260
pekar inte på några fler noder.

598
00:50:48,260 --> 00:50:54,300
Varför kan vi göra detta med en Huffman-fil, men inte morsekod?

599
00:50:54,300 --> 00:50:56,610
För i morsekod finns lite tvetydighet.

600
00:50:56,610 --> 00:51:04,440
Vi kan vara som, oh vänta, vi har träffat en bokstav på vägen, så kanske det här är vårt brev,

601
00:51:04,440 --> 00:51:08,150
medan om vi fortsatte bara lite längre, då skulle vi ha hit en annan bokstav.

602
00:51:08,150 --> 00:51:13,110
Men det kommer inte att hända i Huffman-kodning,

603
00:51:13,110 --> 00:51:17,540
så att vi kan lita på att det enda sättet att vi kommer att träffa ett tecken

604
00:51:17,540 --> 00:51:23,480
är om det nodens vänstra och högra barn är NULL.

605
00:51:28,280 --> 00:51:32,350
>> Slutligen vill vi frigöra alla våra minne.

606
00:51:32,350 --> 00:51:37,420
Vi vill både nära den Huff fil som vi har att göra med

607
00:51:37,420 --> 00:51:41,940
samt ta bort alla träd i vår skog.

608
00:51:41,940 --> 00:51:46,470
Baserat på din implementering, du kommer förmodligen att vilja ringa bort skog

609
00:51:46,470 --> 00:51:49,780
istället för att faktiskt gå igenom alla träden själv.

610
00:51:49,780 --> 00:51:53,430
Men om du gjort några tillfälliga träd, kommer du vill frigöra det.

611
00:51:53,430 --> 00:51:59,060
Du vet att din kod bäst, så du vet vart du fördela minne.

612
00:51:59,060 --> 00:52:04,330
Och så om du går in, börja med att även Styrning F'ing för malloc,

613
00:52:04,330 --> 00:52:08,330
se när du malloc och se till att du befria allt det

614
00:52:08,330 --> 00:52:10,190
men sedan bara gå igenom din kod,

615
00:52:10,190 --> 00:52:14,260
förstå var du kan ha allokerat minne.

616
00:52:14,260 --> 00:52:21,340
Brukar du kanske bara säga, "I slutet av en fil jag bara tänker ta bort skog på min skog,"

617
00:52:21,340 --> 00:52:23,850
så i princip klart att minnet, fri att,

618
00:52:23,850 --> 00:52:28,310
"Och sedan jag kommer också att avsluta ärendet och sedan mitt program kommer att sluta."

619
00:52:28,310 --> 00:52:33,810
Men är det den enda gången som ditt program avslutas?

620
00:52:33,810 --> 00:52:37,880
Nej, eftersom det ibland kan ha varit ett misstag som hände.

621
00:52:37,880 --> 00:52:42,080
Kanske kunde vi inte öppna en fil eller vi kunde inte göra annat träd

622
00:52:42,080 --> 00:52:49,340
eller någon form av fel hände i minnesallokering processen och det återvände NULL.

623
00:52:49,340 --> 00:52:56,710
Ett fel inträffade och sedan vi återvände och sluta.

624
00:52:56,710 --> 00:53:02,040
Så då du vill vara säker på att en eventuell tid som ditt program kan sluta,

625
00:53:02,040 --> 00:53:06,980
du vill frigöra all din minne där.

626
00:53:06,980 --> 00:53:13,370
Det är inte bara kommer att vara i slutet av de viktigaste funktionen som du avslutar din kod.

627
00:53:13,370 --> 00:53:20,780
Du vill se tillbaka på alla instanser att din kod eventuellt kan återvända i förtid

628
00:53:20,780 --> 00:53:25,070
och sedan fri oavsett minne vettigt.

629
00:53:25,070 --> 00:53:30,830
Säg att du hade ringt göra skog och det återvände falskt.

630
00:53:30,830 --> 00:53:34,230
Så har du förmodligen inte kommer att behöva ta bort din skog

631
00:53:34,230 --> 00:53:37,080
eftersom du inte har en skog än.

632
00:53:37,080 --> 00:53:42,130
Men vid varje punkt i koden där du kan återvända i förtid

633
00:53:42,130 --> 00:53:46,160
du vill vara säker på att du frigör eventuell minne.

634
00:53:46,160 --> 00:53:50,020
>> Så när vi har att göra med att frigöra minne och har potentiella läckor,

635
00:53:50,020 --> 00:53:55,440
Vi vill inte bara använda vårt omdöme och vår logik

636
00:53:55,440 --> 00:54:01,850
men även använda Valgrind att avgöra om vi har befriat alla våra minne korrekt eller ej.

637
00:54:01,850 --> 00:54:09,460
Du kan antingen köra Valgrind på Puff och då måste man också ge det

638
00:54:09,460 --> 00:54:14,020
rätt antal kommandoradsargument med valgrind.

639
00:54:14,020 --> 00:54:18,100
Du kan köra det, men utgången är lite kryptiskt.

640
00:54:18,100 --> 00:54:21,630
Vi har fått lite van vid det med Speller, men vi behöver fortfarande lite mer hjälp,

641
00:54:21,630 --> 00:54:26,450
så då kör det med några fler flaggor som läckan-check = full,

642
00:54:26,450 --> 00:54:32,040
som förmodligen kommer att ge oss lite mer användbar utgången på Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Sedan en annan bra tips när du felsöker är skillnad kommandot.

644
00:54:39,040 --> 00:54:48,520
Du kan komma åt den personal genomförande av Huff, köra den på en textfil,

645
00:54:48,520 --> 00:54:55,400
och sedan mata den till en binär fil, en binär Huff fil, för att vara specifik.

646
00:54:55,400 --> 00:54:59,440
Sen om du kör din egen puff på den binär fil,

647
00:54:59,440 --> 00:55:03,950
då helst är din utmatade textfil kommer att vara identiska

648
00:55:03,950 --> 00:55:08,200
till den ursprungliga som du gått i.

649
00:55:08,200 --> 00:55:15,150
Här Jag använder hth.txt som exempel, och det är en talade om i din spec.

650
00:55:15,150 --> 00:55:21,040
Det är bokstavligen bara HTH och sedan en ny rad.

651
00:55:21,040 --> 00:55:30,970
Men definitivt gärna och du definitivt uppmuntras att använda längre exempel

652
00:55:30,970 --> 00:55:32,620
för din textfil.

653
00:55:32,620 --> 00:55:38,110
>> Du kan även ta ett skott på kanske komprimera och sedan dekomprimering

654
00:55:38,110 --> 00:55:41,600
några av de filer som du använde i Speller som Krig och fred

655
00:55:41,600 --> 00:55:46,710
eller Jane Austen eller något liknande - det skulle vara ganska häftigt - eller Austin Powers,

656
00:55:46,710 --> 00:55:51,880
typ att hantera större filer eftersom vi inte skulle komma ner till den

657
00:55:51,880 --> 00:55:55,590
om vi använde nästa verktyg här, ls-l.

658
00:55:55,590 --> 00:56:01,150
Vi är vana vid ls, som i princip visar alla innehållet i vår nuvarande katalog.

659
00:56:01,150 --> 00:56:07,860
Passerar i flaggan-l faktiskt visar storleken på dessa filer.

660
00:56:07,860 --> 00:56:12,690
Om du går igenom pset spec, går det faktiskt dig att skapa den binära filen,

661
00:56:12,690 --> 00:56:16,590
av huffing det, och du ser att för mycket små filer

662
00:56:16,590 --> 00:56:23,910
utrymme kostnaden att komprimera den och översätta all denna information

663
00:56:23,910 --> 00:56:26,980
av alla frekvenser och sånt som uppväger den faktiska nyttan

664
00:56:26,980 --> 00:56:30,000
att komprimera filen i första hand.

665
00:56:30,000 --> 00:56:37,450
Men om du kör det på några längre textfiler, så du kanske se att du börjar få lite nytta

666
00:56:37,450 --> 00:56:40,930
att komprimera dessa filer.

667
00:56:40,930 --> 00:56:46,210
>> Och slutligen har vi vår gamle vän GDB, som definitivt kommer att komma väl till pass också.

668
00:56:48,360 --> 00:56:55,320
>> Har vi några frågor om Huff träd eller processen kanske att göra träden

669
00:56:55,320 --> 00:56:58,590
eller några andra frågor om Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okej. Jag stannar runt för lite.

671
00:57:02,570 --> 00:57:06,570
>> Tack, alla. Detta var Genomgång 6. Och lycka till.

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