1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Návod - Problém Set 6]

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

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

4
00:00:07,240 --> 00:00:12,180
>> Ahoj, všichni, vítejte na Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
V Puff Huff'n, co děláme se bude zabývat souboru Huffman komprimovaného

6
00:00:17,440 --> 00:00:20,740
a pak nafukování ji zpět nahoru, tak dekompresi to,

7
00:00:20,740 --> 00:00:25,810
takže můžeme přeložit z 0s a 1s, že uživatel odešle dotaz

8
00:00:25,810 --> 00:00:30,660
a převést jej zpět do původního textu.

9
00:00:30,660 --> 00:00:34,360
Pset 6 bude docela v pohodě, protože budete vidět některé z nástrojů

10
00:00:34,360 --> 00:00:41,730
které jste použili v PSet 4 a PSet 5 a druhu a sloučit je do 1 pěkně úhledné koncepce

11
00:00:41,730 --> 00:00:43,830
když přijde na to myslet.

12
00:00:43,830 --> 00:00:50,110
>> Také, pravděpodobně, Pset 4 a 5 byly nejnáročnější psets, které jsme měli nabídnout.

13
00:00:50,110 --> 00:00:53,950
Takže od teď, máme tuto 1 větší PSet v C,

14
00:00:53,950 --> 00:00:56,480
a pak po tom jsme na programování pro web.

15
00:00:56,480 --> 00:01:02,310
Takže gratuluji sebe pro překonání nejtěžší hrb v CS50.

16
00:01:03,630 --> 00:01:09,760
>> Pohybující se na pro Puff Huff'n, naše toolbox pro tento PSet se bude Huffman stromy,

17
00:01:09,760 --> 00:01:14,700
takže pochopení nejen jak binární stromy práci, ale také specificky Huffman stromy,

18
00:01:14,700 --> 00:01:16,240
jak to početně jsou.

19
00:01:16,240 --> 00:01:20,210
A pak budeme mít spoustu distribuční kódu v tomto PSet,

20
00:01:20,210 --> 00:01:22,480
a my přijdeme vidět, že skutečně některé z kódu

21
00:01:22,480 --> 00:01:24,670
bychom nebyli schopni plně pochopit ještě,

22
00:01:24,670 --> 00:01:30,080
a tak ti budou. c soubory, ale pak jejich doprovod. h soubory

23
00:01:30,080 --> 00:01:34,300
nám dá dostatek pochopení, že potřebujeme, abychom věděli, jak tyto funkce pracují

24
00:01:34,300 --> 00:01:38,100
nebo alespoň to, co mají dělat - jejich vstupů a výstupů -

25
00:01:38,100 --> 00:01:40,760
i když nevíme, co se děje v černé skříňce,

26
00:01:40,760 --> 00:01:44,090
nebo nechápou, co se děje v černé skříňce uvnitř.

27
00:01:44,090 --> 00:01:49,400
A pak konečně, jako obvykle, máme co do činění s novými datovými strukturami,

28
00:01:49,400 --> 00:01:51,840
specifické typy uzlů, které poukazují na některé věci,

29
00:01:51,840 --> 00:01:56,080
a tak zde mají tužku a papír nejen pro návrhového procesu

30
00:01:56,080 --> 00:01:58,470
a když se snažíte přijít na to, jak vaše Pset by měl fungovat

31
00:01:58,470 --> 00:02:00,520
ale i při ladění.

32
00:02:00,520 --> 00:02:06,140
Můžete mít GDB vedle vašeho pera a papíru, zatímco vy se stanoví, jaké hodnoty jsou,

33
00:02:06,140 --> 00:02:09,320
, kde se vaše šipky směřují, a podobné věci.

34
00:02:09,320 --> 00:02:13,720
>> Nejprve se podívejme na stromy Huffman.

35
00:02:13,720 --> 00:02:19,600
Huffman stromy jsou binární stromy, což znamená, že každý uzel má pouze 2 děti.

36
00:02:19,600 --> 00:02:24,870
V stromů Huffman charakteristika je, že nejčastější hodnoty

37
00:02:24,870 --> 00:02:27,140
jsou zastoupeny nejmenším počtem bitů.

38
00:02:27,140 --> 00:02:32,690
Viděli jsme v přednáškových příkladů Morseovy abecedy, jaký druh konsolidovaných některé dopisy.

39
00:02:32,690 --> 00:02:38,030
Pokud se snažíte přeložit A nebo e, například,

40
00:02:38,030 --> 00:02:43,940
jste překládání, že často, takže místo by bylo nutné použít kompletní sadu bitů

41
00:02:43,940 --> 00:02:48,640
přiděleny pro uvedené obvyklého typu dat, zkomprimovat jej do méně,

42
00:02:48,640 --> 00:02:53,730
a pak ty dopisy, které jsou zastoupeny méně často jsou zastoupeny s delšími bitů

43
00:02:53,730 --> 00:02:59,840
protože si to mohou dovolit, že když se naváží frekvence, které tyto dopisy se objeví.

44
00:02:59,840 --> 00:03:03,020
Máme stejný nápad tady na stromech Huffman

45
00:03:03,020 --> 00:03:12,360
kde jsme udělali řetěz, druh cesty se dostat do některých postav.

46
00:03:12,360 --> 00:03:14,470
A pak postavy, které mají největší frekvenci

47
00:03:14,470 --> 00:03:17,940
se bude zastoupen s nejmenším počtem bitů.

48
00:03:17,940 --> 00:03:22,020
>> Způsob, jakým si vytvořit Huffman strom

49
00:03:22,020 --> 00:03:27,430
je tím všechny znaky, které se vyskytují v textu

50
00:03:27,430 --> 00:03:30,630
a výpočet jejich četnost, jak často se objevují.

51
00:03:30,630 --> 00:03:33,880
To by mohlo být buď počet, kolikrát se tyto dopisy se objeví

52
00:03:33,880 --> 00:03:40,270
nebo možná procento ze všech postav, kolik každý z nich objeví.

53
00:03:40,270 --> 00:03:44,270
A tak to, co děláte, je, až budete mít všechny tyto zmapována,

54
00:03:44,270 --> 00:03:49,060
pak se podíváte na 2 nejnižších frekvencí a pak se k nim připojil jako sourozenci

55
00:03:49,060 --> 00:03:55,660
kde pak nadřazený uzel má frekvenci, která je suma 2 děti.

56
00:03:55,660 --> 00:04:00,870
A pak se podle konvence říká, že levý uzel,

57
00:04:00,870 --> 00:04:03,770
budete následovat, že po 0 větev,

58
00:04:03,770 --> 00:04:08,140
a pak se úplně vpravo uzel je 1 větev.

59
00:04:08,140 --> 00:04:16,040
Jak jsme viděli v Morseově abecedě, ten gotcha bylo, že pokud jste měli jen pípnutí a pípnutí

60
00:04:16,040 --> 00:04:18,120
to byl nejednoznačný.

61
00:04:18,120 --> 00:04:22,430
Mohlo by to být buď 1 písmeno nebo to mohlo být posloupnost 2 písmen.

62
00:04:22,430 --> 00:04:27,790
A tak to, co Huffman stromy dělá, je, protože podle povahy postav

63
00:04:27,790 --> 00:04:34,140
nebo naše konečné skutečné postavy jako poslední uzly na pobočce -

64
00:04:34,140 --> 00:04:39,300
máme na mysli ty, které jsou listy - na základě, že nemůže být jakákoliv nejednoznačnost

65
00:04:39,300 --> 00:04:45,160
z hlediska toho, které písmeno se snažíte enkódování s řadou bitů

66
00:04:45,160 --> 00:04:50,670
protože nikde podél bitů, které představují 1 písmeno

67
00:04:50,670 --> 00:04:55,960
setkáte další celý dopis, a tam nebudou žádné zmatek tam.

68
00:04:55,960 --> 00:04:58,430
Ale půjdeme do příklady, které vy můžete skutečně vidět, že

69
00:04:58,430 --> 00:05:02,120
místo z nás jen říkám, že je to pravda.

70
00:05:02,120 --> 00:05:06,390
>> Pojďme se podívat na jednoduchý příklad stromu Huffman.

71
00:05:06,390 --> 00:05:09,380
Mám řetězec, který je zde 12 znaků.

72
00:05:09,380 --> 00:05:14,010
Mám 4 As, 6 BS a 2 Čs.

73
00:05:14,010 --> 00:05:17,270
Můj první krok by bylo počítat.

74
00:05:17,270 --> 00:05:20,760
Kolikrát se objeví? Zdá se, 4 krát v řetězci.

75
00:05:20,760 --> 00:05:25,060
B se objeví 6 krát, a C se objeví 2 krát.

76
00:05:25,060 --> 00:05:28,970
Samozřejmě, budu říkat, že jsem pomocí B nejčastěji,

77
00:05:28,970 --> 00:05:35,970
tak chci reprezentovat B s nejmenším počtem bitů, při menším počtu 0s a 1s.

78
00:05:35,970 --> 00:05:42,600
A pak jsem také bude očekávat C vyžadovat největší množství 0s a 1s stejně.

79
00:05:42,600 --> 00:05:48,550
První, co jsem udělal je zde jsem umístil je ve vzestupném pořadí podle frekvence.

80
00:05:48,550 --> 00:05:52,710
Vidíme, že C a A, které jsou naše 2 nejnižších frekvencí.

81
00:05:52,710 --> 00:06:00,290
Máme vytvořit nadřazený uzel, a že nadřazený uzel nemá písmeno s ním spojené,

82
00:06:00,290 --> 00:06:05,070
ale má frekvenci, která je součtem.

83
00:06:05,070 --> 00:06:08,780
Součet stane 2 + 4, což je 6.

84
00:06:08,780 --> 00:06:10,800
Pak se vydáme po levé větev.

85
00:06:10,800 --> 00:06:14,970
Pokud jsme byli v té 6 uzlu, pak bychom následovat 0 dostat se do C

86
00:06:14,970 --> 00:06:17,450
a pak 1 se dostat do A.

87
00:06:17,450 --> 00:06:20,300
Takže teď máme 2 uzly.

88
00:06:20,300 --> 00:06:23,920
Máme hodnotu 6 a pak také další uzel s hodnotou 6.

89
00:06:23,920 --> 00:06:28,550
A tak ti, 2 nejsou jen 2 nejnižší, ale také jen 2, které jsou vlevo,

90
00:06:28,550 --> 00:06:33,820
tak jsme připojit se k těm jiným rodičem, s suma je 12.

91
00:06:33,820 --> 00:06:36,300
Takže tady máme Huffmanova stromu

92
00:06:36,300 --> 00:06:40,020
kde se dostat do B, to by bylo prostě bit 1

93
00:06:40,020 --> 00:06:45,430
a pak se dostat do budeme mít 01, a pak C s 00.

94
00:06:45,430 --> 00:06:51,300
Takže zde vidíme, že v podstatě jsme zastupující tyto znaky s 1 nebo 2 bity

95
00:06:51,300 --> 00:06:55,160
kde B, jak předpovídal, má nejméně.

96
00:06:55,160 --> 00:07:01,730
A pak jsme očekávali C mají nejvíce, ale protože je to takový malý Huffman strom,

97
00:07:01,730 --> 00:07:06,020
pak je také reprezentována 2 bitů oproti někde uprostřed.

98
00:07:07,820 --> 00:07:11,070
>> Stačí si projít další jednoduchý příklad stromu Huffman,

99
00:07:11,070 --> 00:07:19,570
že máte řetězec "Hello."

100
00:07:19,570 --> 00:07:25,360
Co uděláte jako první byste říci, jak kolikrát se H objevit v tomto?

101
00:07:25,360 --> 00:07:34,200
H se objeví jednou a pak e se objeví jednou a pak jsme l objevilo dvakrát

102
00:07:34,200 --> 00:07:36,580
a o objevují jednou.

103
00:07:36,580 --> 00:07:44,310
A pak se můžeme očekávat, které písmeno bude zastoupena nejmenším počtem bitů?

104
00:07:44,310 --> 00:07:47,450
[Student] l. >> L. Jo. l má pravdu.

105
00:07:47,450 --> 00:07:50,730
Předpokládáme l být zastoupen nejmenším počtem bitů

106
00:07:50,730 --> 00:07:55,890
proto, že jsem se používá nejčastěji v řetězci "Hello."

107
00:07:55,890 --> 00:08:04,280
Co budu dělat, teď je čerpat z těchto uzlů.

108
00:08:04,280 --> 00:08:15,580
Mám 1, který je H, a pak ještě 1, což je e, a pak se 1, což je o -

109
00:08:15,580 --> 00:08:23,410
teď jsem seřízení - a pak 2, který je l.

110
00:08:23,410 --> 00:08:32,799
Pak jsem řekl tak, že jsem postavit Huffman strom je najít 2 uzly s nejméně frekvencí

111
00:08:32,799 --> 00:08:38,010
a aby jim sourozence vytvořením nadřazený uzel.

112
00:08:38,010 --> 00:08:41,850
Zde máme 3 uzly s nejnižší frekvencí. Všichni jsou 1.

113
00:08:41,850 --> 00:08:50,620
Tak tady jsme si vybrat, který z nich budeme propojit první.

114
00:08:50,620 --> 00:08:54,850
Řekněme, že jsem si vybrat H a E.

115
00:08:54,850 --> 00:09:01,150
Součet 1 + 1 = 2, ale tento uzel nemá písmeno s ním spojené.

116
00:09:01,150 --> 00:09:04,440
Je to jen má hodnotu.

117
00:09:04,440 --> 00:09:10,950
Nyní se podíváme na další 2 nejnižších frekvencí.

118
00:09:10,950 --> 00:09:15,590
To je 2 a 1. To by mohlo být jedním z těch 2, ale budu si vybrat tento jeden.

119
00:09:15,590 --> 00:09:18,800
Součet je 3.

120
00:09:18,800 --> 00:09:26,410
A pak konečně, mám jen 2 vlevo, tak pak to bude 5.

121
00:09:26,410 --> 00:09:32,010
Pak zde, jak se očekávalo, když jsem vyplnit kódování pro to,

122
00:09:32,010 --> 00:09:37,480
1s se vždy ten správný obor a 0s je levá.

123
00:09:37,480 --> 00:09:45,880
Pak máme l reprezentovaný pouze 1 bit a pak na Õ 2

124
00:09:45,880 --> 00:09:52,360
a pak e o 2 a pak H klesá na 3 bitů.

125
00:09:52,360 --> 00:09:59,750
Takže můžete přenášet tuto zprávu "Hello" namísto skutečně použití znaků

126
00:09:59,750 --> 00:10:02,760
jen o 0s a 1s.

127
00:10:02,760 --> 00:10:07,910
Pamatujte však, že v několika případech jsme měli vztahy s naší frekvencí.

128
00:10:07,910 --> 00:10:11,900
Mohli jsme buď připojil k H a o První možná.

129
00:10:11,900 --> 00:10:15,730
Nebo pak o něco později, když jsme měli l představované 2

130
00:10:15,730 --> 00:10:19,410
, jakož i připojil které reprezentuje 2, mohli jsme spojeny buď jeden.

131
00:10:19,410 --> 00:10:23,630
>> A tak, když pošlete 0s a 1s, že ve skutečnosti nezaručuje

132
00:10:23,630 --> 00:10:27,090
že příjemce může plně číst zprávy hned bat

133
00:10:27,090 --> 00:10:30,490
protože nemusí vědět, kdy rozhodnutí jste udělali.

134
00:10:30,490 --> 00:10:34,920
Takže když máme co do činění s kompresí Huffman,

135
00:10:34,920 --> 00:10:40,090
nějak musíme říct příjemce našeho poselství, jak jsme se rozhodli -

136
00:10:40,090 --> 00:10:43,470
Potřebují vědět, nějaké další informace

137
00:10:43,470 --> 00:10:46,580
kromě zprávy stlačeného vzduchu.

138
00:10:46,580 --> 00:10:51,490
Je třeba, aby pochopili, co strom vlastně vypadá,

139
00:10:51,490 --> 00:10:55,450
jak jsme vlastně dělal ty rozhodnutí.

140
00:10:55,450 --> 00:10:59,100
>> Zde jsme dělali jen to, příklady založené na skutečné počtu,

141
00:10:59,100 --> 00:11:01,550
ale někdy může mít také Huffman strom

142
00:11:01,550 --> 00:11:05,760
na základě frekvenci, při které se objeví písmena, a to je přesně stejný postup.

143
00:11:05,760 --> 00:11:09,090
Tady jsem vyjádřit to v procentech nebo zlomkem

144
00:11:09,090 --> 00:11:11,290
a tak zde přesně to samé.

145
00:11:11,290 --> 00:11:15,300
Zjistil jsem, 2 nejnižší, shrnout je, další 2 nejnižší, shrnout je,

146
00:11:15,300 --> 00:11:19,390
až budu mít plnou strom.

147
00:11:19,390 --> 00:11:23,610
I když bychom mohli udělat to buď tak, když máme co do činění s procenty,

148
00:11:23,610 --> 00:11:27,760
to znamená, že jsme rozdělení věci a nakládání s desetinných míst, či spíše plave

149
00:11:27,760 --> 00:11:30,900
pokud budeme přemýšlet o datových struktur hlavy.

150
00:11:30,900 --> 00:11:32,540
Co víme o plováky?

151
00:11:32,540 --> 00:11:35,180
Co je to běžný problém, kdy máme co do činění s plováky?

152
00:11:35,180 --> 00:11:38,600
[Student] Nepřesné aritmetika. Jo >>. Nepřesnost.

153
00:11:38,600 --> 00:11:43,760
Vzhledem k tomu, v pohyblivé řádové čárce nepřesnosti, pro tento PSet tak, že se ujistit,

154
00:11:43,760 --> 00:11:49,450
že abychom neztratili žádné hodnoty, pak jsme vlastně bude jednat s hrabětem.

155
00:11:49,450 --> 00:11:54,880
Takže pokud jste měli myslet na uzlu Huffman, když se podíváte zpět do struktury zde,

156
00:11:54,880 --> 00:12:01,740
když se podíváte na zelených má frekvenci s ním spojené

157
00:12:01,740 --> 00:12:08,760
stejně jako to ukazuje na uzel na jeho levé straně, stejně jako uzel na jeho pravé straně.

158
00:12:08,760 --> 00:12:13,970
Potom červený ty tam také mají charakter jsou s nimi spojeny.

159
00:12:13,970 --> 00:12:18,900
Nebudeme dělat samostatné ty pro rodiče a pak koncových uzlů,

160
00:12:18,900 --> 00:12:23,680
které označujeme jako listy, ale spíše těch budou muset jen hodnoty NULL.

161
00:12:23,680 --> 00:12:31,050
Pro každý uzel budeme mít charakter, symbol, že uzel reprezentuje,

162
00:12:31,050 --> 00:12:40,490
pak frekvence, stejně jako ukazatel na jeho levé dítě, stejně jako jeho pravé dítě.

163
00:12:40,490 --> 00:12:45,680
Listy, které jsou na samém dně, by také mít uzlů odkazy

164
00:12:45,680 --> 00:12:49,550
po jejich levici a jejich práva, ale protože tyto hodnoty nejsou poukazem na skutečné uzly,

165
00:12:49,550 --> 00:12:53,970
co by jejich hodnota byla? >> [Student] NULL. >> NULL. Přesně tak.

166
00:12:53,970 --> 00:12:58,430
Zde je příklad toho, jak by se Vám mohl představovat frekvenci v plováky,

167
00:12:58,430 --> 00:13:02,130
ale budeme jednat s ním s celými čísly,

168
00:13:02,130 --> 00:13:06,780
takže vše, co udělal, je změnit datový typ tam.

169
00:13:06,780 --> 00:13:09,700
>> Pojďme na trochu více komplexní příklad.

170
00:13:09,700 --> 00:13:13,360
Ale teď, když jsme udělali jednoduché ty, je to jen stejný proces.

171
00:13:13,360 --> 00:13:20,290
Můžete najít 2 nejnižších kmitočtů, sečíst frekvence

172
00:13:20,290 --> 00:13:22,450
a to je nová frekvence vašeho nadřazeného uzlu,

173
00:13:22,450 --> 00:13:29,310
který pak ukazuje na jeho levé straně s 0 pobočky a právo s 1 pobočkou.

174
00:13:29,310 --> 00:13:34,200
Pokud máme řetězec "To je cs50," pak budeme počítat, kolikrát je T uvedeno,

175
00:13:34,200 --> 00:13:38,420
h zmíněno, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Pak to, co jsem udělal tu je s červenými uzly jsem zasadil,

177
00:13:42,010 --> 00:13:48,530
Řekl jsem, že budu mít tyto znaky nakonec na dně mého stromu.

178
00:13:48,530 --> 00:13:51,740
Ti budou mít všechny listy.

179
00:13:51,740 --> 00:13:58,200
Pak to, co jsem udělal je, že jsem seřazena je podle četnosti ve vzestupném pořadí,

180
00:13:58,200 --> 00:14:02,950
a to je vlastně způsob, že Pset kód dělá

181
00:14:02,950 --> 00:14:07,550
Je to druhy to tím, že frekvence a pak podle abecedy.

182
00:14:07,550 --> 00:14:13,870
Tak to má čísla první a pak abecedně podle frekvence.

183
00:14:13,870 --> 00:14:18,520
Tak co bych udělal je, že jsem se najít 2 nejnižší. To je 0 a 5.

184
00:14:18,520 --> 00:14:22,390
Chtěl bych shrnout je, a to je 2. Pak bych pokračovat, najít další 2 nejnižší.

185
00:14:22,390 --> 00:14:26,100
To jsou dva 1s, a pak ty, se 2, jakož.

186
00:14:26,100 --> 00:14:31,570
Teď vím, že můj další krok bude se připojí nejnižší číslo,

187
00:14:31,570 --> 00:14:41,380
který je T, 1, a potom výběrem jednoho z uzlů, které má dvě jako frekvence.

188
00:14:41,380 --> 00:14:44,560
Takže tu máme 3 možnosti.

189
00:14:44,560 --> 00:14:47,980
Co budu dělat po snímku je jen vizuálně změnit jejich pořadí pro vás

190
00:14:47,980 --> 00:14:51,790
takže můžete vidět, jak jsem buduje.

191
00:14:51,790 --> 00:14:59,040
Co kód a vaše distribuce kód bude dělat by se připojit k T jeden

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

193
00:15:01,410 --> 00:15:05,060
Takže, že částky na 3, a pak budeme pokračovat v procesu.

194
00:15:05,060 --> 00:15:08,660
2 a 2 jsou nyní nejnižší, takže pak ty součet pro 4.

195
00:15:08,660 --> 00:15:12,560
Každý po tak daleko? Dobře.

196
00:15:12,560 --> 00:15:16,410
Pak po tom máme 3 a 3, které je třeba sečíst,

197
00:15:16,410 --> 00:15:21,650
takže opět jsem jen přepínání to tak, že můžete vidět vizuálně tak, že to není příliš komplikovaná.

198
00:15:21,650 --> 00:15:25,740
Pak máme 6, a pak se naše poslední krok je nyní, že máme jen 2 uzly

199
00:15:25,740 --> 00:15:30,440
Shrneme ty, aby se kořen našeho stromu, což je 10.

200
00:15:30,440 --> 00:15:34,100
A číslo 10 dává smysl, protože každý uzel představuje,

201
00:15:34,100 --> 00:15:40,750
jejich hodnota, jejich četnost číslo, bylo kolikrát se objevily v řetězci,

202
00:15:40,750 --> 00:15:46,350
a pak máme 5 znaků v našem řetězci, tak to dává smysl.

203
00:15:48,060 --> 00:15:52,320
Podíváme-li se na to, jak se budeme skutečně zakódovat,

204
00:15:52,320 --> 00:15:56,580
podle očekávání, i a y, které se objevují nejčastěji

205
00:15:56,580 --> 00:16:01,350
jsou zastoupeny nejmenším počtem bitů.

206
00:16:03,660 --> 00:16:05,660
>> Buďte opatrní.

207
00:16:05,660 --> 00:16:09,780
V stromů Huffman případ skutečně záleží.

208
00:16:09,780 --> 00:16:13,670
Velká S se liší malým s.

209
00:16:13,670 --> 00:16:21,260
Pokud bychom měli "To je CS50" s velkými písmeny, pak malá s by se zobrazí pouze dvakrát,

210
00:16:21,260 --> 00:16:27,120
by uzel s 2 jako jeho hodnotu, a pak se velká S by pouze jednou.

211
00:16:27,120 --> 00:16:33,440
Takže váš strom by se změnily struktury, protože máte skutečně zvláštní list zde.

212
00:16:33,440 --> 00:16:36,900
Ale částka bude stále 10.

213
00:16:36,900 --> 00:16:39,570
To je to, co jsme vlastně bude volat kontrolní součet,

214
00:16:39,570 --> 00:16:44,060
přidání všech směrech.

215
00:16:46,010 --> 00:16:50,990
>> Teď, když jsme probrali Huffman stromy, můžeme se ponořit do Puff Huff'n se PSet.

216
00:16:50,990 --> 00:16:52,900
Budeme začít s částí otázek,

217
00:16:52,900 --> 00:16:57,990
a to bude vám zvyklí s binárními stromy a jak pracovat kolem toho:

218
00:16:57,990 --> 00:17:03,230
kreslení uzly, vytvořit si vlastní typedef struct pro uzel,

219
00:17:03,230 --> 00:17:07,230
a vidět, jak byste mohli vložit do binárního stromu, jeden, který je seřazena,

220
00:17:07,230 --> 00:17:09,050
křížení je, a podobné věci.

221
00:17:09,050 --> 00:17:14,560
Že znalosti se určitě pomůže, když se ponoříte do části Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
z PSet.

223
00:17:19,150 --> 00:17:26,329
Ve standardním vydání PSet, vaším úkolem je realizovat Puff,

224
00:17:26,329 --> 00:17:30,240
a ve hacker verzi vaším úkolem je realizovat Huff.

225
00:17:30,240 --> 00:17:38,490
Co Huff dělá, je, že trvá textu a pak to překládá do 0s a 1s,

226
00:17:38,490 --> 00:17:41,990
tak proces, který jsme udělali výše, kde jsme napočítali frekvence

227
00:17:41,990 --> 00:17:50,970
a pak se na strom a pak řekl: "Jak se dostanu T?"

228
00:17:50,970 --> 00:17:54,840
T je zastoupena 100, a podobné věci,

229
00:17:54,840 --> 00:17:58,860
a pak Huff by se text a pak výstupní že binární.

230
00:17:58,860 --> 00:18:04,920
Ale také proto, že víme, že chceme, aby náš příjemce zprávy

231
00:18:04,920 --> 00:18:11,790
znovu přesně stejný strom, ale také obsahuje informace o frekvenčních počítá.

232
00:18:11,790 --> 00:18:17,980
Pak se Puff je nám dán binární soubor 0s a 1s

233
00:18:17,980 --> 00:18:21,740
a vzhledem k tomu i informace o frekvencích.

234
00:18:21,740 --> 00:18:26,740
Překládáme všechny ty 0s a 1s zpět do původní zprávy, která byla,

235
00:18:26,740 --> 00:18:29,350
takže jsme dekomprese, že.

236
00:18:29,350 --> 00:18:36,450
Pokud děláte standardní edici, nemusíte provádět Huff,

237
00:18:36,450 --> 00:18:39,290
takže pak stačí použít zaměstnanců provádění Huff.

238
00:18:39,290 --> 00:18:42,080
Tam jsou instrukce v spec o tom, jak to udělat.

239
00:18:42,080 --> 00:18:48,780
Můžete spustit zaměstnance provádění Huff na určité textového souboru

240
00:18:48,780 --> 00:18:53,270
a pak použít tento výstup jako vstup Puff.

241
00:18:53,270 --> 00:18:59,330
>> Jak jsem již zmínil dříve, máme spoustu distribuce kódu pro tento jeden.

242
00:18:59,330 --> 00:19:01,810
Chystám se začít chodit přes něj.

243
00:19:01,810 --> 00:19:04,400
Budu trávit většinu času na. H soubory

244
00:19:04,400 --> 00:19:07,660
protože v. soubory C, protože máme. H

245
00:19:07,660 --> 00:19:11,650
a že nám poskytuje prototypy funkcí,

246
00:19:11,650 --> 00:19:15,520
nemáme plně nutné přesně pochopit -

247
00:19:15,520 --> 00:19:20,280
Pokud nechcete pochopit, co se děje v. Soubory C, pak se nemusíte starat moc,

248
00:19:20,280 --> 00:19:23,600
ale rozhodně zkuste se podívat, protože by to mohlo dát nějaké rady

249
00:19:23,600 --> 00:19:29,220
a je užitečné si zvyknout na čtení kódu jiných lidí.

250
00:19:38,940 --> 00:19:48,270
>> Při pohledu na huffile.h, do komentářů, že deklaruje vrstvu abstrakce pro Huffman-kódované soubory.

251
00:19:48,270 --> 00:20:01,660
Pokud půjdeme dolů, vidíme, že je maximálně 256 znaků, které bychom mohli potřebovat kódy.

252
00:20:01,660 --> 00:20:05,480
To zahrnuje všechna písmena abecedy - velká a malá -

253
00:20:05,480 --> 00:20:08,250
a pak symboly a čísla, atd.

254
00:20:08,250 --> 00:20:11,930
Pak zde máme magic number, který stanovil Huffman kódovaný soubor.

255
00:20:11,930 --> 00:20:15,890
V rámci kódu Huffman, že budeš mít určitý magické číslo

256
00:20:15,890 --> 00:20:18,560
spojený s záhlaví.

257
00:20:18,560 --> 00:20:21,110
To může vypadat jako jen náhodné magické číslo,

258
00:20:21,110 --> 00:20:27,160
ale pokud jste skutečně přeložit do ASCII, pak to vlastně vysvětluje rozzlobit.

259
00:20:27,160 --> 00:20:34,290
Zde máme struct pro Huffman kódování souboru.

260
00:20:34,290 --> 00:20:39,670
Je tu všechny tyto charakteristiky spojené se souborem Huff.

261
00:20:39,670 --> 00:20:47,080
Pak tady máme hlavičku pro soubor Huff, tak říkáme, že Huffeader

262
00:20:47,080 --> 00:20:50,810
namísto přidání další h, protože to zní stejně tak.

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

264
00:20:52,720 --> 00:20:57,790
Máme kouzelné číslo s ním spojené.

265
00:20:57,790 --> 00:21:09,040
Pokud je to skutečný Huff soubor, to bude číslo nahoře, to kouzlo jeden.

266
00:21:09,040 --> 00:21:14,720
A pak to bude mít pole.

267
00:21:14,720 --> 00:21:18,750
Tak pro každý symbol, který je 256,

268
00:21:18,750 --> 00:21:24,760
bude to seznam toho, co četnost těchto symbolů je v souboru Huff.

269
00:21:24,760 --> 00:21:28,090
A pak konečně, máme kontrolní součet kmitočtů,

270
00:21:28,090 --> 00:21:32,160
, které by měly být součet těchto frekvencí.

271
00:21:32,160 --> 00:21:36,520
Tak to je to, co Huffeader je.

272
00:21:36,520 --> 00:21:44,600
Pak máme některé funkce, které vracejí další bit v souboru Huff

273
00:21:44,600 --> 00:21:52,580
stejně jako zapíše bit souboru Huff, a pak se tato funkce zde, hfclose,

274
00:21:52,580 --> 00:21:54,650
které skutečně zavře soubor Huff.

275
00:21:54,650 --> 00:21:57,290
Dříve jsme se zabývali přímo jen fclose,

276
00:21:57,290 --> 00:22:01,190
ale když máte soubor Huff, místo toho, aby ji fclosing

277
00:22:01,190 --> 00:22:06,080
co jste vlastně dělat, je hfclose a hfopen ji.

278
00:22:06,080 --> 00:22:13,220
To jsou specifické funkce Huffová soubory, které budeme k řešení.

279
00:22:13,220 --> 00:22:19,230
Pak zde čteme v záhlaví a pak psát záhlaví.

280
00:22:19,230 --> 00:22:25,700
>> Jen tím, že čtení. H soubor můžeme trochu získat pocit z toho, co soubor Huff může být,

281
00:22:25,700 --> 00:22:32,480
jaké vlastnosti má, aniž by se skutečně jít do huffile.c,

282
00:22:32,480 --> 00:22:36,750
které, pokud bychom ponořit, bude trochu složitější.

283
00:22:36,750 --> 00:22:41,270
Má všechny souboru I / O tu se zabývá ukazateli.

284
00:22:41,270 --> 00:22:48,010
Zde vidíme, že když voláme hfread, například, je to stále vypořádává s fread.

285
00:22:48,010 --> 00:22:53,050
Nejsme zbavit těchto funkcí zcela, ale posíláme, které mají být postaráno

286
00:22:53,050 --> 00:22:59,760
uvnitř souboru Huff místo dělá vše pro to sami.

287
00:22:59,760 --> 00:23:02,300
Můžete klidně prohledá to, pokud jste zvědaví,

288
00:23:02,300 --> 00:23:08,410
a jít a kůra vrstvě zadní trochu.

289
00:23:20,650 --> 00:23:24,060
>> Další obrázek, který budeme podívat se na tree.h.

290
00:23:24,060 --> 00:23:30,210
Předtím v Walkthrough sklouzne jsme řekli, očekáváme Huffmanova uzel

291
00:23:30,210 --> 00:23:32,960
a udělali jsme typedef struct uzel.

292
00:23:32,960 --> 00:23:38,360
Očekáváme, že mají symbol, frekvence, a pak 2 uzlů hvězdy.

293
00:23:38,360 --> 00:23:41,870
V tomto případě, co děláme, je to v podstatě stejný

294
00:23:41,870 --> 00:23:46,880
kromě namísto uzlu budeme nazývat stromy.

295
00:23:48,790 --> 00:23:56,760
Máme funkci, která při volání, aby strom to vrátí vám strom ukazatel.

296
00:23:56,760 --> 00:24:03,450
Zpět na Speller, když jste dělali nový uzel

297
00:24:03,450 --> 00:24:11,410
jste řekl uzel * nové slovo = malloc (sizeof) a podobné věci.

298
00:24:11,410 --> 00:24:17,510
V podstatě, mktree se bude zabývat, že pro vás.

299
00:24:17,510 --> 00:24:20,990
Podobně, pokud chcete odstranit strom,

300
00:24:20,990 --> 00:24:24,810
tak to je v podstatě uvolnění strom, když jste s ním udělal,

301
00:24:24,810 --> 00:24:33,790
místo aby byl explicitně volat zdarma na to, že jste ve skutečnosti jen tak použít funkci rmtree

302
00:24:33,790 --> 00:24:40,360
kde předáte ukazatel na daný strom a pak tree.c se postará o to pro vás.

303
00:24:40,360 --> 00:24:42,490
>> Díváme se do tree.c.

304
00:24:42,490 --> 00:24:47,240
Očekáváme, že stejné funkce, kromě nedočkalo realizace stejně.

305
00:24:47,240 --> 00:24:57,720
Jak jsme očekávali, když budete volat mktree to mallocs velikosti stromu do ukazatele,

306
00:24:57,720 --> 00:25:03,190
inicializuje všechny hodnoty s hodnotou NULL, takže 0s nebo hodnoty Null,

307
00:25:03,190 --> 00:25:08,280
a vrátí ukazatel na daný strom, který jste právě malloc'd pro vás.

308
00:25:08,280 --> 00:25:13,340
Zde, když zavoláte odstranit strom nejprve zajistí, že nejste double uvolnění.

309
00:25:13,340 --> 00:25:18,320
To zajišťuje, že budete mít ve skutečnosti strom, který chcete odebrat.

310
00:25:18,320 --> 00:25:23,330
Zde protože strom i své děti,

311
00:25:23,330 --> 00:25:29,560
Co to však je, že vyžaduje rekurzivně odstranit strom na levé uzel stromu

312
00:25:29,560 --> 00:25:31,650
stejně jako správné uzlu.

313
00:25:31,650 --> 00:25:37,790
Před tím, než se uvolní rodiče, je třeba osvobodit děti stejně.

314
00:25:37,790 --> 00:25:42,770
Parent je také zaměnitelný s kořenem.

315
00:25:42,770 --> 00:25:46,500
Vůbec první rodič, tak jako velký-velký-velký-velký-dědeček

316
00:25:46,500 --> 00:25:52,130
nebo babička strom, musíme nejprve uvolnit se stanoví úrovně první.

317
00:25:52,130 --> 00:25:58,490
Takže traverz až na dno, bez těch, a pak se vrátit nahoru, bez těch, atd.

318
00:26:00,400 --> 00:26:02,210
Tak to je strom.

319
00:26:02,210 --> 00:26:04,240
>> Nyní se podíváme na les.

320
00:26:04,240 --> 00:26:09,860
Forest je místo, kde můžete umístit všechny své stromy Huffman.

321
00:26:09,860 --> 00:26:12,910
Je to tím, že budeme mít něco jako plot

322
00:26:12,910 --> 00:26:22,320
, který obsahuje ukazatel na strom, stejně jako ukazatel na pozemku s názvem další.

323
00:26:22,320 --> 00:26:28,480
Jaká struktura se tento druh vypadat?

324
00:26:29,870 --> 00:26:32,490
Je to druh to říká tam.

325
00:26:34,640 --> 00:26:36,700
Přímo tady.

326
00:26:37,340 --> 00:26:39,170
Spojový seznam.

327
00:26:39,170 --> 00:26:44,590
Vidíme, že když máme pozemek je to jako propojeného seznamu parcel.

328
00:26:44,590 --> 00:26:53,020
Les je definován jako propojeného seznamu pozemků,

329
00:26:53,020 --> 00:26:58,100
a tak struktura lesa je, že se to jen tak, aby se ukazatel na první ploše

330
00:26:58,100 --> 00:27:02,740
a že pozemek má strom v něm, nebo spíše poukazuje ke stromu

331
00:27:02,740 --> 00:27:06,190
a pak se odkazuje na následující pozemku, tak dále a tak dále.

332
00:27:06,190 --> 00:27:11,100
Chcete-li les říkáme mkforest.

333
00:27:11,100 --> 00:27:14,930
Pak máme některé docela užitečné funkce zde.

334
00:27:14,930 --> 00:27:23,240
Máme vybrat, kde předáte v lese a pak návratová hodnota je strom *,

335
00:27:23,240 --> 00:27:25,210
ukazatel na strom.

336
00:27:25,210 --> 00:27:29,370
Co pick bude dělat, je, že půjde do lesa, že jste ukázal na

337
00:27:29,370 --> 00:27:35,240
pak odstraňte strom s nejnižším kmitočtu z toho lesa

338
00:27:35,240 --> 00:27:38,330
a pak vám ukazatel na ten strom.

339
00:27:38,330 --> 00:27:43,030
Jakmile zavoláte vybrat, bude strom neexistuje v lese už,

340
00:27:43,030 --> 00:27:48,550
ale návratová hodnota je ukazatel na ten strom.

341
00:27:48,550 --> 00:27:50,730
Pak máte rostlinu.

342
00:27:50,730 --> 00:27:57,420
Za předpokladu, že předáte ukazatel na strom, který má non-0 frekvenci,

343
00:27:57,420 --> 00:28:04,040
co rostlina bude dělat, je, že bude trvat do lesa, vezměte strom, a závod, který strom uvnitř lesa.

344
00:28:04,040 --> 00:28:06,370
Zde máme rmforest.

345
00:28:06,370 --> 00:28:11,480
Podobné odstranit strom, který v podstatě osvobodil všechny z našich stromů pro nás,

346
00:28:11,480 --> 00:28:16,600
odebrat les svobodná vůle vše obsažené v tomto lese.

347
00:28:16,600 --> 00:28:24,890
>> Podíváme-li se do forest.c, budeme očekávat, že alespoň 1 rmtree příkaz tam,

348
00:28:24,890 --> 00:28:30,090
protože na volné paměti v lese, pokud les má stromy v něm,

349
00:28:30,090 --> 00:28:32,930
pak nakonec budete muset odstranit ty stromy taky.

350
00:28:32,930 --> 00:28:41,020
Podíváme-li se do forest.c, máme mkforest, což je, jak jsme očekávali.

351
00:28:41,020 --> 00:28:42,890
My malloc věci.

352
00:28:42,890 --> 00:28:51,740
Jsme inicializaci první pozemek v lese jako NULL, protože je prázdná začít,

353
00:28:51,740 --> 00:29:05,940
pak vidíme, vybrat, které vrací strom s nejnižší váhou, nejnižší frekvence,

354
00:29:05,940 --> 00:29:13,560
a pak zbaví daného uzlu, který odkazuje na ten strom a ten příští,

355
00:29:13,560 --> 00:29:16,760
tak to trvá, že z propojeného seznamu lesa.

356
00:29:16,760 --> 00:29:24,510
A pak tu máme závod, který vloží stromu do propojeného seznamu.

357
00:29:24,510 --> 00:29:29,960
Co les dělá, je to pěkně drží to jsou seřazena pro nás.

358
00:29:29,960 --> 00:29:37,910
A pak konečně, máme rmforest a, jak se očekávalo, máme rmtree vzýval tam.

359
00:29:46,650 --> 00:29:55,440
>> Při pohledu na distribuční kód tak daleko, huffile.c byl pravděpodobně zdaleka nejtěžší pochopit,

360
00:29:55,440 --> 00:29:59,990
vzhledem k tomu, dalších souborů sami byli docela jednoduché následovat.

361
00:29:59,990 --> 00:30:03,090
Při naší znalosti ukazatelů a vzájemně provázaných seznamů a takových,

362
00:30:03,090 --> 00:30:04,860
jsme byli schopni sledovat docela dobře.

363
00:30:04,860 --> 00:30:10,500
Ale všechno, co potřebujeme opravdu ujistit, že plně chápeme je. H soubory

364
00:30:10,500 --> 00:30:15,840
protože je třeba, aby se volání těchto funkcí, které se zabývají těmito návratové hodnoty,

365
00:30:15,840 --> 00:30:20,590
takže se ujistěte, že jste plně porozuměli, jaká akce se bude provádět

366
00:30:20,590 --> 00:30:24,290
kdykoliv volat jednu z těchto funkcí.

367
00:30:24,290 --> 00:30:33,020
Ale ve skutečnosti porozumění uvnitř ní není zcela nutné, protože máme ty. H soubory.

368
00:30:35,170 --> 00:30:39,490
Máme 2 další soubory, které zůstaly v naší distribuční kódu.

369
00:30:39,490 --> 00:30:41,640
>> Pojďme se podívat na skládce.

370
00:30:41,640 --> 00:30:47,230
Dump jeho komentáři zde trvá Huffman-komprimovaný soubor

371
00:30:47,230 --> 00:30:55,580
a pak překládá a skládky všichni její obsah ven.

372
00:31:01,010 --> 00:31:04,260
Zde vidíme, že je to volání hfopen.

373
00:31:04,260 --> 00:31:10,770
To je druh zrcadlení soubor * vstup = fopen,

374
00:31:10,770 --> 00:31:13,500
a pak se projít v informaci.

375
00:31:13,500 --> 00:31:18,240
Je to téměř identické, s výjimkou místo souboru * jste procházející v Huffile;

376
00:31:18,240 --> 00:31:22,030
místo fopen jste mimochodem v hfopen.

377
00:31:22,030 --> 00:31:29,280
Zde čteme v záhlaví první, který je tak trochu podobné tomu, jak čteme v záhlaví

378
00:31:29,280 --> 00:31:33,580
pro bitmapový soubor.

379
00:31:33,580 --> 00:31:38,000
Co tady děláme je kontrola, zda informace v hlavičce

380
00:31:38,000 --> 00:31:44,330
obsahuje správné magické číslo, které označuje, že je to skutečný Huff soubor,

381
00:31:44,330 --> 00:31:53,610
pak všechny tyto kontroly, aby se ujistil, že soubor, který jsme otevřený je skutečný rozzlobil soubor, nebo ne.

382
00:31:53,610 --> 00:32:05,330
Co to však je, že výstupy frekvence všech symbolů, které můžeme vidět

383
00:32:05,330 --> 00:32:09,790
v rámci terminálu do grafického tabulky.

384
00:32:09,790 --> 00:32:15,240
Tato část bude užitečná.

385
00:32:15,240 --> 00:32:24,680
Má trochu a čte kousek po kousku do proměnné bit a pak vytiskne ji.

386
00:32:28,220 --> 00:32:35,430
Takže pokud bych měl zavolat skládku na hth.bin, která je výsledkem rozzlobí souboru

387
00:32:35,430 --> 00:32:39,490
pomocí zaměstnanců řešení, bych si to.

388
00:32:39,490 --> 00:32:46,000
Je to výstup všech těchto znaků a pak uvedení frekvenci, při které se objeví.

389
00:32:46,000 --> 00:32:51,180
Podíváme-li se, většina z nich jsou 0s kromě toho: H, který se objeví dvakrát,

390
00:32:51,180 --> 00:32:54,820
a pak T, která se objeví jednou.

391
00:32:54,820 --> 00:33:07,860
A pak tu máme skutečný zprávu 0s a 1s.

392
00:33:07,860 --> 00:33:15,450
Pokud se podíváme na hth.txt, což je pravděpodobně původní zprávy, která byla odfrkl,

393
00:33:15,450 --> 00:33:22,490
očekáváme nějaké Hs a TS tam.

394
00:33:22,490 --> 00:33:28,720
Konkrétně, očekáváme jen 1 T a 2 HS.

395
00:33:32,510 --> 00:33:37,440
Tady jsme v hth.txt. To má skutečně HTH.

396
00:33:37,440 --> 00:33:41,270
Zahrnuty tam, ačkoli my nemůžeme vidět, je znak nového řádku.

397
00:33:41,270 --> 00:33:53,190
Soubor Huff hth.bin je také kódování znaku nového řádku stejně.

398
00:33:55,680 --> 00:34:01,330
Zde protože víme, že řád je HTH a pak nový řádek,

399
00:34:01,330 --> 00:34:07,340
je vidět, že asi H je reprezentována jen jedním 1

400
00:34:07,340 --> 00:34:17,120
a pak T je pravděpodobně 01 a pak další H 1, stejně

401
00:34:17,120 --> 00:34:21,139
a pak máme nový řádek označena dvěma 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> A pak konečně, protože máme co do činění s více. C a. H soubory,

404
00:34:31,600 --> 00:34:36,350
budeme mít pěkně složitá argument kompilátor,

405
00:34:36,350 --> 00:34:40,460
a tak zde máme Makefile, které umožňuje výpis pro vás.

406
00:34:40,460 --> 00:34:47,070
Ale ve skutečnosti, budete muset jít o tom své vlastní puff.c soubor.

407
00:34:47,070 --> 00:34:54,330
Makefile vlastně neřeší dělat puff.c pro vás.

408
00:34:54,330 --> 00:34:59,310
Odjíždíme, že na vás upravit Makefile.

409
00:34:59,310 --> 00:35:05,930
Když zadáte příkaz, jako je, aby všem, například, bude to dělat všechny z nich pro vás.

410
00:35:05,930 --> 00:35:10,760
Neváhejte se podívat na příklady Makefile z minulého PSet

411
00:35:10,760 --> 00:35:17,400
stejně jako jít pryč z tohohle vidět, jak byste měli být schopni, aby se váš Puff soubor

412
00:35:17,400 --> 00:35:20,260
úpravou tohoto souboru Makefile.

413
00:35:20,260 --> 00:35:22,730
To je asi tak pro náš distribuční kódu.

414
00:35:22,730 --> 00:35:28,380
>> Jakmile jsme se dostali přes to, že pak je tu jen další připomínkou toho,

415
00:35:28,380 --> 00:35:30,980
o tom, jak budeme jednat s uzly Huffman.

416
00:35:30,980 --> 00:35:35,400
Nebudeme se volat je uzliny už, budeme se nazývat stromy

417
00:35:35,400 --> 00:35:39,260
kde budeme zastupovat jejich symbol, char,

418
00:35:39,260 --> 00:35:43,340
jejich frekvence, počet výskytů, s celé číslo.

419
00:35:43,340 --> 00:35:47,370
Používáme to, protože to je to přesnější než plováku.

420
00:35:47,370 --> 00:35:52,980
A pak máme další ukazatel na levé dítěte stejně jako pravé dítě.

421
00:35:52,980 --> 00:35:59,630
Les, jak jsme viděli, je jen provázaný seznam stromů.

422
00:35:59,630 --> 00:36:04,670
Nakonec, když jsme budování naší Huff soubor,

423
00:36:04,670 --> 00:36:07,580
chceme, aby naše lesy obsahovat pouze 1 strom -

424
00:36:07,580 --> 00:36:12,420
1 strom, 1 root s více dětmi.

425
00:36:12,420 --> 00:36:20,840
Dříve, když jsme byli jen, že naše Huffman stromy,

426
00:36:20,840 --> 00:36:25,360
jsme začali tím všechny uzly na naší obrazovce

427
00:36:25,360 --> 00:36:27,790
a říkat budeme mít tyto uzly,

428
00:36:27,790 --> 00:36:32,920
nakonec se budeš listy, a to je jejich symbol, je to jejich četnost.

429
00:36:32,920 --> 00:36:42,070
V našem lese, kdybychom se 3 písmena, to je les 3 stromů.

430
00:36:42,070 --> 00:36:45,150
A pak, jak budeme pokračovat, když jsme přidali první rodiče,

431
00:36:45,150 --> 00:36:48,080
jsme se les 2 stromů.

432
00:36:48,080 --> 00:36:54,930
Odstranili jsme 2 z těchto dětí z našeho lesa a pak nahradil ji nadřazeného uzlu

433
00:36:54,930 --> 00:36:58,820
že měl ty 2 uzly jako děti.

434
00:36:58,820 --> 00:37:05,600
A pak konečně, naše poslední krok s výrobou náš příklad s As, Bs, a Cs

435
00:37:05,600 --> 00:37:08,030
by ke konečnému rodiče,

436
00:37:08,030 --> 00:37:13,190
a tak, pak by to přinést naše celkové počtu stromů v lese na 1.

437
00:37:13,190 --> 00:37:18,140
Má každý vidět, jak se začít s několika stromy v lese

438
00:37:18,140 --> 00:37:22,520
a skončit s 1? Dobře. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Co musíme udělat pro Puff?

440
00:37:28,110 --> 00:37:37,110
Co musíme udělat, je zajistit, že jako vždy, nám dávají ten správný typ vstupu

441
00:37:37,110 --> 00:37:39,090
tak, že se může ve skutečnosti spustit program.

442
00:37:39,090 --> 00:37:43,130
V tomto případě jsou to bude, že nám po jejich prvním argument příkazového řádku

443
00:37:43,130 --> 00:37:53,440
2 více: soubor, který chceme dekomprimovat a výstup dekomprimovaného souboru.

444
00:37:53,440 --> 00:38:00,410
Ale jakmile jsme se ujistili, že kolem nás ve správném množství hodnot,

445
00:38:00,410 --> 00:38:05,820
Chceme zajistit, aby vstup je soubor Huff, nebo ne.

446
00:38:05,820 --> 00:38:10,420
A pak ještě jednou vám zaručit, že je to soubor Huff, pak chceme budovat náš strom,

447
00:38:10,420 --> 00:38:20,940
vybudovat strom tak, že odpovídá strom, že osoba, která zaslala zprávu postavený.

448
00:38:20,940 --> 00:38:25,840
Pak po stavíme strom, pak se můžeme zabývat 0s a 1s, že prošel v roce,

449
00:38:25,840 --> 00:38:29,590
těm, které spolu náš strom, protože je to stejné,

450
00:38:29,590 --> 00:38:33,510
a pak napsat, že poselství, interpretovat bity zpět do znaků.

451
00:38:33,510 --> 00:38:35,880
A pak na konci, protože máme co do činění s ukazateli tady,

452
00:38:35,880 --> 00:38:38,110
Chceme se ujistit, že nemáme žádné úniky paměti

453
00:38:38,110 --> 00:38:41,330
a že jsme volní všechno.

454
00:38:42,820 --> 00:38:46,430
>> Zajištění řádného využití je starý klobouk pro nás teď.

455
00:38:46,430 --> 00:38:51,980
Bereme v vstup, který bude název souboru nafouknout,

456
00:38:51,980 --> 00:38:56,010
a pak jsme se specifikovat výstup,

457
00:38:56,010 --> 00:39:01,580
takže název souboru pro želírovacího výstup, který bude textový soubor.

458
00:39:03,680 --> 00:39:08,820
To je s nimi nakládáno. A teď chceme zajistit, že vstup je rozzlobil, nebo ne.

459
00:39:08,820 --> 00:39:16,420
Když vzpomínám, bylo něco, co v distribuční kódu, který nám může pomoci

460
00:39:16,420 --> 00:39:21,570
s pochopením, zda je soubor rozzlobil, nebo ne?

461
00:39:21,570 --> 00:39:26,910
Tam byly informace v huffile.c o Huffeader.

462
00:39:26,910 --> 00:39:33,430
Víme, že každý soubor Huff má Huffeader s ním spojené s kouzelným číslem

463
00:39:33,430 --> 00:39:37,240
, jakož i řada frekvencí pro každý symbol

464
00:39:37,240 --> 00:39:39,570
stejně jako kontrolní součet.

465
00:39:39,570 --> 00:39:43,180
Víme, že, ale také se nahlédnout na dump.c,

466
00:39:43,180 --> 00:39:49,120
, ve kterém bylo čtení do souboru Huff.

467
00:39:49,120 --> 00:39:53,990
A tak k tomu, že to mělo ověřit, zda skutečně byl rozzlobil, nebo ne.

468
00:39:53,990 --> 00:40:03,380
Takže možná bychom mohli použít dump.c jako struktury pro naše puff.c.

469
00:40:03,380 --> 00:40:12,680
Zpět na PSet 4, když jsme měli soubor copy.c, že ​​zkopírovali v trojicích RGB

470
00:40:12,680 --> 00:40:14,860
a my vykládat, že pro detektivka a změny velikosti,

471
00:40:14,860 --> 00:40:20,390
podobně, co byste mohli udělat, je stačí spustit příkaz jako cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
a použít některé z kódu tam.

473
00:40:23,600 --> 00:40:28,210
Nicméně, to nebude tak jednoduché procesu

474
00:40:28,210 --> 00:40:33,010
pro překládání si dump.c do puff.c,

475
00:40:33,010 --> 00:40:36,160
ale aspoň to vám dává někde začít

476
00:40:36,160 --> 00:40:40,540
o tom, jak zajistit, aby vstup je skutečně odfrkl, nebo ne

477
00:40:40,540 --> 00:40:43,240
stejně jako pár dalších věcí.

478
00:40:45,930 --> 00:40:50,250
Jsme zajistili správné použití a zajistit, aby vstup rozzlobil.

479
00:40:50,250 --> 00:40:53,570
Pokaždé, když jsme udělali, že jsme udělali naši správnou kontrolu chyb,

480
00:40:53,570 --> 00:41:01,520
tak vrací a ukončení funkce, pokud některé dojde k selhání, v případě, že je problém.

481
00:41:01,520 --> 00:41:07,170
>> Teď, co chceme udělat, je vytvořit skutečný strom.

482
00:41:08,840 --> 00:41:12,640
Podíváme-li se v lese, tam jsou 2 hlavní funkce

483
00:41:12,640 --> 00:41:15,800
že budeme chtít, aby se velmi dobře.

484
00:41:15,800 --> 00:41:23,870
Tam je booleovská funkce rostlina, která rostliny non-0 Frekvence strom v našem lese.

485
00:41:23,870 --> 00:41:29,250
A tak tam předáte ukazatel na les a ukazatel na strom.

486
00:41:32,530 --> 00:41:40,340
Rychlý dotaz: Kolik lesy budete mít, když stavíte Huffman strom?

487
00:41:44,210 --> 00:41:46,650
Naše les je jako náš plátno, ne?

488
00:41:46,650 --> 00:41:50,800
Takže jsme jen bude mít 1 les, ale budeme mít více stromů.

489
00:41:50,800 --> 00:41:57,590
Takže předtím, než zavoláte zařízení, budete pravděpodobně chtít, aby váš les.

490
00:41:57,590 --> 00:42:04,430
K dispozici je příkaz pro které, když se podíváte do forest.h o tom, jak můžete udělat les.

491
00:42:04,430 --> 00:42:09,270
Můžete zasadit strom. Víme, jak na to.

492
00:42:09,270 --> 00:42:11,590
A pak si můžete také vybrat strom z lesa,

493
00:42:11,590 --> 00:42:17,540
odstranění stromu s nejnižší váhou a dává vám ukazatel na to.

494
00:42:17,540 --> 00:42:23,090
Vzpomínal, když jsme dělali v příkladech sami,

495
00:42:23,090 --> 00:42:27,980
když jsme byli kreslení to, jsme prostě jen přidali odkazy.

496
00:42:27,980 --> 00:42:31,680
Ale tady ne jen přidávání odkazů,

497
00:42:31,680 --> 00:42:40,630
myslet na to spíš jako jste odstranění 2 těchto uzlů a pak nahrazovat ji jinou.

498
00:42:40,630 --> 00:42:44,200
Chcete-li vyjádřit, že pokud jde o sběr a pěstování,

499
00:42:44,200 --> 00:42:48,840
jste vychystávání 2 stromy a pak výsadba další strom

500
00:42:48,840 --> 00:42:54,060
že má ty 2 stromy, které jste si vybrali jako děti.

501
00:42:57,950 --> 00:43:05,280
Chcete-li vytvořit Huffman je strom, si můžete přečíst v symboly a frekvence v pořadí

502
00:43:05,280 --> 00:43:10,790
protože Huffeader dává, že na vás,

503
00:43:10,790 --> 00:43:14,250
vám dává řadu frekvencí.

504
00:43:14,250 --> 00:43:19,660
Takže můžete jít dopředu a jen tak ignorovat cokoli s 0 v něm

505
00:43:19,660 --> 00:43:23,760
protože nechceme 256 listy na konci toho.

506
00:43:23,760 --> 00:43:27,960
Chceme pouze počet listů, které jsou znaky

507
00:43:27,960 --> 00:43:31,600
, které jsou ve skutečnosti používá v souboru.

508
00:43:31,600 --> 00:43:37,590
Si můžete přečíst v těchto symbolů, a každý z těchto symbolů, které mají non-0 frekvencí,

509
00:43:37,590 --> 00:43:40,440
ty se bude stromy.

510
00:43:40,440 --> 00:43:45,990
Co můžete udělat, je pokaždé, když si přečetl v non-0 frekvence symbol,

511
00:43:45,990 --> 00:43:50,660
můžete zasadit ten strom v lese.

512
00:43:50,660 --> 00:43:56,620
Jakmile zasadit stromy v lese, můžete se připojit ty stromy jako sourozenci,

513
00:43:56,620 --> 00:44:01,130
tak vrací k výsadbě a vybírání, kde si vyberete 2 a pak závod 1,

514
00:44:01,130 --> 00:44:05,820
kde to 1, která vás rostlin je rodič na 2 děti, které si vybral.

515
00:44:05,820 --> 00:44:11,160
Takže pak se vaše konečný výsledek bude jediný strom v lese.

516
00:44:16,180 --> 00:44:18,170
To je, jak si postavit svůj strom.

517
00:44:18,170 --> 00:44:21,850
>> Existuje několik věcí, které by mohly pokazit zde

518
00:44:21,850 --> 00:44:26,580
protože máme co do činění s výrobou nových stromů a nakládání s ukazateli a podobné věci.

519
00:44:26,580 --> 00:44:30,450
Než když jsme se zabývali ukazateli,

520
00:44:30,450 --> 00:44:36,580
když jsme malloc'd jsme chtěli, aby se ujistil, že se nevrátil nám NULL ukazatel hodnotu.

521
00:44:36,580 --> 00:44:42,770
Takže na několika krocích v rámci tohoto procesu jsou bude několik případů

522
00:44:42,770 --> 00:44:45,920
kde váš program by mohl selhat.

523
00:44:45,920 --> 00:44:51,310
Co chcete udělat, je se chcete ujistit, že řešíte tyto chyby,

524
00:44:51,310 --> 00:44:54,580
a ve spec říká s nimi elegantně,

525
00:44:54,580 --> 00:45:00,280
tak jako vytisknout zprávu uživateli řekněte jim, proč musí program ukončit

526
00:45:00,280 --> 00:45:03,050
a pak rychle ukončete ji.

527
00:45:03,050 --> 00:45:09,490
Chcete-li tuto chyb, pamatujte, že chcete zkontrolovat

528
00:45:09,490 --> 00:45:12,160
pokaždé, že by mohlo být selhání.

529
00:45:12,160 --> 00:45:14,660
Pokaždé, že děláš nový ukazatel

530
00:45:14,660 --> 00:45:17,040
Chcete, aby se ujistil, že je úspěšný.

531
00:45:17,040 --> 00:45:20,320
Než to, co jsme udělat, je vytvořit nový ukazatel a malloc ji,

532
00:45:20,320 --> 00:45:22,380
a pak bychom zkontrolovat, zda je ukazatel NULL.

533
00:45:22,380 --> 00:45:25,670
Takže tam se bude některé příklady, kde můžete jen udělat to,

534
00:45:25,670 --> 00:45:28,610
ale někdy jste vlastně volání funkce

535
00:45:28,610 --> 00:45:33,100
av rámci této funkce, že je to ten, který dělá na mallocing.

536
00:45:33,100 --> 00:45:39,110
V tomto případě, pokud se podíváme zpět do některé z funkcí v kódu,

537
00:45:39,110 --> 00:45:42,260
Některé z nich jsou logické funkce.

538
00:45:42,260 --> 00:45:48,480
V abstraktní případě, pokud máme logický funkce s názvem foo,

539
00:45:48,480 --> 00:45:54,580
v podstatě, lze předpokládat, že kromě tom, co foo dělá,

540
00:45:54,580 --> 00:45:57,210
protože je to booleovská funkce, vrací true nebo false -

541
00:45:57,210 --> 00:46:01,300
true, pokud úspěšný, false v opačném případě.

542
00:46:01,300 --> 00:46:06,270
Takže chceme zjistit, zda návratová hodnota foo je true nebo false.

543
00:46:06,270 --> 00:46:10,400
Pokud je to false, což znamená, že budeme chtít vytisknout nějakou zprávu

544
00:46:10,400 --> 00:46:14,390
a pak ukončete program.

545
00:46:14,390 --> 00:46:18,530
Co chceme udělat, je zkontrolovat vrácenou hodnotu foo.

546
00:46:18,530 --> 00:46:23,310
Pokud foo vrátí false, pak víme, že jsme se setkali s nějakou chybou

547
00:46:23,310 --> 00:46:25,110
a musíme přestat náš program.

548
00:46:25,110 --> 00:46:35,600
Způsob, jak to udělat, je mít stav, kdy skutečná funkce sama o sobě je Váš zdravotní stav.

549
00:46:35,600 --> 00:46:39,320
Řekněme, že foo bere v x.

550
00:46:39,320 --> 00:46:43,390
Můžeme mít jako podmínku if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
V podstatě to znamená, že pokud na konci provádění foo vrací pravda,

552
00:46:50,900 --> 00:46:57,390
pak můžeme udělat, protože funkce musí vyhodnotit foo

553
00:46:57,390 --> 00:47:00,500
aby bylo možno vyhodnotit celý stav.

554
00:47:00,500 --> 00:47:06,500
Takže je to, jak můžete něco udělat, pokud funkce vrací hodnotu true a je úspěšný.

555
00:47:06,500 --> 00:47:11,800
Ale když jste kontrolu chyb, si jen chcete ukončit, pokud je vaše funkce vrátí false.

556
00:47:11,800 --> 00:47:16,090
Co můžete udělat, je jen přidat == false, nebo jen přidat třesku před ním

557
00:47:16,090 --> 00:47:21,010
a pak máte if (! foo).

558
00:47:21,010 --> 00:47:29,540
V rámci tohoto orgánu tohoto stavu byste mít všechny chyb,

559
00:47:29,540 --> 00:47:36,940
tak jako, "Nepodařilo se vytvořit tento strom" a pak se vrátit 1, nebo něco takového.

560
00:47:36,940 --> 00:47:43,340
Co to dělá, když je to, že i když foo vrátil false -

561
00:47:43,340 --> 00:47:46,980
Řekněme, že foo vrací hodnotu true.

562
00:47:46,980 --> 00:47:51,060
Pak nemusíte volat foo znovu. To je mylná představa,.

563
00:47:51,060 --> 00:47:54,730
Vzhledem k tomu, že byl ve svém stavu, je to již vyhodnocen,

564
00:47:54,730 --> 00:47:59,430
takže už máte výsledek, pokud používáte, aby strom nebo něco takového

565
00:47:59,430 --> 00:48:01,840
nebo zařízení nebo pick, nebo tak něco.

566
00:48:01,840 --> 00:48:07,460
To už má tuto hodnotu. Je to již proveden.

567
00:48:07,460 --> 00:48:10,730
Takže je to vhodné použít booleovské funkce jako podmínku

568
00:48:10,730 --> 00:48:13,890
protože ať už jste či nejste skutečně spustit tělo smyčky,

569
00:48:13,890 --> 00:48:18,030
spustí funkci stejně.

570
00:48:22,070 --> 00:48:27,330
>> Náš druhý na poslední krok je psaní zprávy do souboru.

571
00:48:27,330 --> 00:48:33,070
Jakmile budeme budovat Huffman strom, pak psaní zprávy do souboru je velice jednoduché.

572
00:48:33,070 --> 00:48:39,260
Je to docela jednoduché nyní stačí následovat 0s a 1s.

573
00:48:39,260 --> 00:48:45,480
A tak podle konvence víme, že na stromě Huffman uveďte opustil 0s

574
00:48:45,480 --> 00:48:48,360
a 1s uvést pravdu.

575
00:48:48,360 --> 00:48:53,540
Takže pokud budete číst v kousek po kousku, pokaždé, když dostanete 0

576
00:48:53,540 --> 00:48:59,100
budete sledovat levá větev, a pak pokaždé, když si přečetl v 1

577
00:48:59,100 --> 00:49:02,100
budete následovat správnou větev.

578
00:49:02,100 --> 00:49:07,570
A pak budete pokračovat, dokud nenarazíte na list

579
00:49:07,570 --> 00:49:11,550
protože listy se bude na konci větví.

580
00:49:11,550 --> 00:49:16,870
Jak můžeme zjistit, zda jsme hit list nebo ne?

581
00:49:19,800 --> 00:49:21,690
Řekli jsme, že to předtím.

582
00:49:21,690 --> 00:49:24,040
[Student] Pokud ukazatele jsou NULL. Jo >>.

583
00:49:24,040 --> 00:49:32,220
Můžeme říct, jestli jsme hit list v případě, že ukazatele na obou levý a pravý stromy jsou NULL.

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

585
00:49:34,110 --> 00:49:40,320
Víme, že chceme číst v kousek po kousku do našeho souboru Huff.

586
00:49:43,870 --> 00:49:51,220
Jak jsme viděli dříve v dump.c, co udělali, je, že si v kousek po kousku do souboru Huff

587
00:49:51,220 --> 00:49:54,560
a jen vytisknout to, co ty kousky byly.

588
00:49:54,560 --> 00:49:58,430
Nebudeme se s tím. Budeme dělat něco, co je trochu složitější.

589
00:49:58,430 --> 00:50:03,620
Ale co můžeme udělat, je, že jsme si vzít ten kousek kódu, který čte do bitu.

590
00:50:03,620 --> 00:50:10,250
Zde máme integer bit představující aktuální bit, který jsme na.

591
00:50:10,250 --> 00:50:15,520
To se stará o iterací všechny bity v souboru, dokud nenarazíte na konec souboru.

592
00:50:15,520 --> 00:50:21,270
Na základě toho, pak budete chtít mít nějaký iterátoru

593
00:50:21,270 --> 00:50:26,760
přejít na strom.

594
00:50:26,760 --> 00:50:31,460
A pak na základě toho, zda je bit 0 nebo 1,

595
00:50:31,460 --> 00:50:36,920
budete chtít, aby buď přesunout tento iterátor vlevo nebo ji přesunout doprava

596
00:50:36,920 --> 00:50:44,080
celou cestu, dokud nenarazíte na list, takže celá cesta až do tohoto uzlu, který jste na

597
00:50:44,080 --> 00:50:48,260
neukazuje na nic víc uzlů.

598
00:50:48,260 --> 00:50:54,300
Proč můžeme udělat se souborem Huffman, ale ne Morse kódu?

599
00:50:54,300 --> 00:50:56,610
Vzhledem k tomu, v Morseově abecedě je tu trochu dvojznačnosti.

600
00:50:56,610 --> 00:51:04,440
Mohli bychom být jako, oh čekat, jsme hit dopis na cestě, takže možná to je naše dopis,

601
00:51:04,440 --> 00:51:08,150
vzhledem k tomu, jestli jsme pokračovali jen trochu déle, pak bychom zasáhli další dopis.

602
00:51:08,150 --> 00:51:13,110
Ale to se nestane v kódování Huffman,

603
00:51:13,110 --> 00:51:17,540
takže můžeme být jisti, že jediný způsob, jak budeme hit charakter

604
00:51:17,540 --> 00:51:23,480
Je-li tento uzel je levá a pravá děti jsou NULL.

605
00:51:28,280 --> 00:51:32,350
>> Konečně, chceme osvobodit všechny naše paměť.

606
00:51:32,350 --> 00:51:37,420
Chceme, aby i konci souboru Huff, že jsme se zabýváme

607
00:51:37,420 --> 00:51:41,940
stejně jako odstranění všech stromů v našem lese.

608
00:51:41,940 --> 00:51:46,470
Na základě vaší implementaci, budete pravděpodobně chtít volat odstranit les

609
00:51:46,470 --> 00:51:49,780
místo skutečně prochází všechny stromy sami.

610
00:51:49,780 --> 00:51:53,430
Ale pokud jste provedli nějaké dočasné stromy, budete chtít uvolnit, že.

611
00:51:53,430 --> 00:51:59,060
Víš svůj kód nejlépe, takže víte, kde jste přidělování paměti.

612
00:51:59,060 --> 00:52:04,330
A tak pokud jdete do, začněte tím, dokonce kontrolu F'ing pro malloc,

613
00:52:04,330 --> 00:52:08,330
vidět kdykoliv malloc a ujistěte se, že jste uvolnit všechno

614
00:52:08,330 --> 00:52:10,190
ale pak právě prochází kódu,

615
00:52:10,190 --> 00:52:14,260
porozumění, kde jste mohli přidělena paměť.

616
00:52:14,260 --> 00:52:21,340
Obvykle můžete jen říct, "Na konci souboru Já jsem prostě jít na odstranění les na mém lese,"

617
00:52:21,340 --> 00:52:23,850
takže v podstatě jasné, že paměť, zdarma, které,

618
00:52:23,850 --> 00:52:28,310
"A pak jsem také chystá zavřete soubor a potom můj program bude přestat."

619
00:52:28,310 --> 00:52:33,810
Ale je to jediný čas, který váš program ukončí?

620
00:52:33,810 --> 00:52:37,880
Ne, protože někdy tam mohlo být chyba, co se stalo.

621
00:52:37,880 --> 00:52:42,080
Možná jsme nemohli otevřít soubor nebo my jsme nemohli provést další strom

622
00:52:42,080 --> 00:52:49,340
nebo nějaký druh chyby se stalo v procesu přidělení paměti, a tak se vrátil NULL.

623
00:52:49,340 --> 00:52:56,710
Došlo k chybě, a pak jsme se vrátili a ukončete.

624
00:52:56,710 --> 00:53:02,040
Takže chcete, aby se ujistil, že případná čas, že váš program může přestat kouřit,

625
00:53:02,040 --> 00:53:06,980
Chcete-li uvolnit všechny své paměti tam.

626
00:53:06,980 --> 00:53:13,370
Není to jen tak na samém konci hlavní funkce, které ukončete kód.

627
00:53:13,370 --> 00:53:20,780
Chceš se podívat zpět na každém stupni, že váš kód potenciálně mohl vrátit předčasně

628
00:53:20,780 --> 00:53:25,070
a pak zdarma bez ohledu na paměti smysl.

629
00:53:25,070 --> 00:53:30,830
Řekněte, že jste zavolal, aby les a že se vrátil false.

630
00:53:30,830 --> 00:53:34,230
Pak jste pravděpodobně nebudete potřebovat odstranit svůj les

631
00:53:34,230 --> 00:53:37,080
protože nemáte lesa dosud.

632
00:53:37,080 --> 00:53:42,130
Ale v každém bodě v kódu, kde může vrátit předčasně

633
00:53:42,130 --> 00:53:46,160
chcete, aby se ujistil, že jste uvolnit případné paměť.

634
00:53:46,160 --> 00:53:50,020
>> Takže když máme co do činění s uvolněním paměti a mají potenciální úniky,

635
00:53:50,020 --> 00:53:55,440
chceme využívat nejen náš úsudek a naše logika

636
00:53:55,440 --> 00:54:01,850
ale také použít Valgrind k určení, zda máme uvolněna veškerá naší paměti správně, nebo ne.

637
00:54:01,850 --> 00:54:09,460
Můžete buď spustit Valgrind na Puff a pak se budete muset také předat jej

638
00:54:09,460 --> 00:54:14,020
správný počet argumentů příkazového řádku pro Valgrind.

639
00:54:14,020 --> 00:54:18,100
Můžete spustit, ale výstup je trochu mystický.

640
00:54:18,100 --> 00:54:21,630
Dostali jsme se trochu na to zvyklí u Speller, ale stále potřebujeme trochu více pomoci,

641
00:54:21,630 --> 00:54:26,450
takže pak běží to s několika dalšími příznaky, jako je únik-check = full,

642
00:54:26,450 --> 00:54:32,040
které budou pravděpodobně nám nějaké další užitečné výstup na Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Pak další užitečné tip, když jste ladění je příkaz diff.

644
00:54:39,040 --> 00:54:48,520
Můžete přistupovat k pracovníkům za provádění Huff, spusťte, že na textový soubor,

645
00:54:48,520 --> 00:54:55,400
a pak výstup do binárního souboru, binární soubor Huff, být konkrétní.

646
00:54:55,400 --> 00:54:59,440
Pak, pokud se dostanete svůj vlastní obláček na tomto binární soubor,

647
00:54:59,440 --> 00:55:03,950
pak v ideálním případě, vaše výstup textový soubor bude totožný

648
00:55:03,950 --> 00:55:08,200
k původní, který prošel dovnitř

649
00:55:08,200 --> 00:55:15,150
Zde jsem pomocí hth.txt jako příklad, a to je ten mluvil o ve vašem spec.

650
00:55:15,150 --> 00:55:21,040
To je doslova HTH a pak nový řádek.

651
00:55:21,040 --> 00:55:30,970
Ale rozhodně neváhejte a jste určitě doporučujeme používat delší příklady

652
00:55:30,970 --> 00:55:32,620
pro textovém souboru.

653
00:55:32,620 --> 00:55:38,110
>> Můžete si dokonce vzít si na mušku možná kompresi a dekompresi pak

654
00:55:38,110 --> 00:55:41,600
některé ze souborů, které jste použili v Speller jako Vojna a mír

655
00:55:41,600 --> 00:55:46,710
nebo Jane Austen, nebo něco takového - to by bylo docela fajn - nebo Austin Powers,

656
00:55:46,710 --> 00:55:51,880
druh jednání s většími soubory, protože bychom přišli na věc

657
00:55:51,880 --> 00:55:55,590
pokud jsme použili na další nástroj zde, ls-l.

658
00:55:55,590 --> 00:56:01,150
Jsme zvyklí na ls, která v podstatě uvádí všechny obsah v našem aktuálním adresáři.

659
00:56:01,150 --> 00:56:07,860
Předávání v vlajky-l skutečně zobrazuje velikost těchto souborů.

660
00:56:07,860 --> 00:56:12,690
Pokud projdete spec PSet, to vlastně vás provede vytvořením binární soubor,

661
00:56:12,690 --> 00:56:16,590
ze dne rozzlobí ho, a uvidíte, že pro velmi malé soubory

662
00:56:16,590 --> 00:56:23,910
prostor náklady na kompresi, a překládat všechny tyto informace

663
00:56:23,910 --> 00:56:26,980
všech frekvencí a podobné věci, které převáží skutečné výhody

664
00:56:26,980 --> 00:56:30,000
kompresi souboru na prvním místě.

665
00:56:30,000 --> 00:56:37,450
Ale pokud se dostanete na některých delších textových souborů, pak byste měli vidět, že začnete se dostat nějaký prospěch

666
00:56:37,450 --> 00:56:40,930
v kompresi těchto souborů.

667
00:56:40,930 --> 00:56:46,210
>> A pak konečně, máme starý kamarád GDB, který je určitě přijde vhod také.

668
00:56:48,360 --> 00:56:55,320
>> Ještě budeme mít nějaké otázky, na stromech Huff nebo procesu snad dělat stromy

669
00:56:55,320 --> 00:56:58,590
nebo jakékoli jiné otázky týkající se Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Dobře. Zůstanu asi na chvíli.

671
00:57:02,570 --> 00:57:06,570
>> Díky, všichni. To bylo Návod 6. A hodně štěstí.

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