[Powered by Google Translate] [Návod - Problém Set 6] [Zamyla Chan - Harvard University] [To je CS50. - CS50.TV] 

Ahoj, všichni, vítejte na Walkthrough 6: Huff'n Puff. V Puff Huff'n, co děláme se bude zabývat souboru Huffman komprimovaného a pak nafukování ji zpět nahoru, tak dekompresi to, takže můžeme přeložit z 0s a 1s, že uživatel odešle dotaz a převést jej zpět do původního textu. Pset 6 bude docela v pohodě, protože budete vidět některé z nástrojů které jste použili v PSet 4 a PSet 5 a druhu a sloučit je do 1 pěkně úhledné koncepce když přijde na to myslet. 

Také, pravděpodobně, Pset 4 a 5 byly nejnáročnější psets, které jsme měli nabídnout. Takže od teď, máme tuto 1 větší PSet v C, a pak po tom jsme na programování pro web. Takže gratuluji sebe pro překonání nejtěžší hrb v CS50. 

Pohybující se na pro Puff Huff'n, naše toolbox pro tento PSet se bude Huffman stromy, takže pochopení nejen jak binární stromy práci, ale také specificky Huffman stromy, jak to početně jsou. A pak budeme mít spoustu distribuční kódu v tomto PSet, a my přijdeme vidět, že skutečně některé z kódu bychom nebyli schopni plně pochopit ještě, a tak ti budou. c soubory, ale pak jejich doprovod. h soubory nám dá dostatek pochopení, že potřebujeme, abychom věděli, jak tyto funkce pracují nebo alespoň to, co mají dělat - jejich vstupů a výstupů - i když nevíme, co se děje v černé skříňce, nebo nechápou, co se děje v černé skříňce uvnitř. A pak konečně, jako obvykle, máme co do činění s novými datovými strukturami, specifické typy uzlů, které poukazují na některé věci, a tak zde mají tužku a papír nejen pro návrhového procesu a když se snažíte přijít na to, jak vaše Pset by měl fungovat ale i při ladění. Můžete mít GDB vedle vašeho pera a papíru, zatímco vy se stanoví, jaké hodnoty jsou, , kde se vaše šipky směřují, a podobné věci. 

Nejprve se podívejme na stromy Huffman. Huffman stromy jsou binární stromy, což znamená, že každý uzel má pouze 2 děti. V stromů Huffman charakteristika je, že nejčastější hodnoty jsou zastoupeny nejmenším počtem bitů. Viděli jsme v přednáškových příkladů Morseovy abecedy, jaký druh konsolidovaných některé dopisy. Pokud se snažíte přeložit A nebo e, například, jste překládání, že často, takže místo by bylo nutné použít kompletní sadu bitů přiděleny pro uvedené obvyklého typu dat, zkomprimovat jej do méně, a pak ty dopisy, které jsou zastoupeny méně často jsou zastoupeny s delšími bitů protože si to mohou dovolit, že když se naváží frekvence, které tyto dopisy se objeví. Máme stejný nápad tady na stromech Huffman kde jsme udělali řetěz, druh cesty se dostat do některých postav. A pak postavy, které mají největší frekvenci se bude zastoupen s nejmenším počtem bitů. 

Způsob, jakým si vytvořit Huffman strom je tím všechny znaky, které se vyskytují v textu a výpočet jejich četnost, jak často se objevují. To by mohlo být buď počet, kolikrát se tyto dopisy se objeví nebo možná procento ze všech postav, kolik každý z nich objeví. A tak to, co děláte, je, až budete mít všechny tyto zmapována, pak se podíváte na 2 nejnižších frekvencí a pak se k nim připojil jako sourozenci kde pak nadřazený uzel má frekvenci, která je suma 2 děti. A pak se podle konvence říká, že levý uzel, budete následovat, že po 0 větev, a pak se úplně vpravo uzel je 1 větev. Jak jsme viděli v Morseově abecedě, ten gotcha bylo, že pokud jste měli jen pípnutí a pípnutí to byl nejednoznačný. Mohlo by to být buď 1 písmeno nebo to mohlo být posloupnost 2 písmen. A tak to, co Huffman stromy dělá, je, protože podle povahy postav nebo naše konečné skutečné postavy jako poslední uzly na pobočce - máme na mysli ty, které jsou listy - na základě, že nemůže být jakákoliv nejednoznačnost z hlediska toho, které písmeno se snažíte enkódování s řadou bitů protože nikde podél bitů, které představují 1 písmeno setkáte další celý dopis, a tam nebudou žádné zmatek tam. Ale půjdeme do příklady, které vy můžete skutečně vidět, že místo z nás jen říkám, že je to pravda. 

Pojďme se podívat na jednoduchý příklad stromu Huffman. Mám řetězec, který je zde 12 znaků. Mám 4 As, 6 BS a 2 Čs. Můj první krok by bylo počítat. Kolikrát se objeví? Zdá se, 4 krát v řetězci. B se objeví 6 krát, a C se objeví 2 krát. Samozřejmě, budu říkat, že jsem pomocí B nejčastěji, tak chci reprezentovat B s nejmenším počtem bitů, při menším počtu 0s a 1s. A pak jsem také bude očekávat C vyžadovat největší množství 0s a 1s stejně. První, co jsem udělal je zde jsem umístil je ve vzestupném pořadí podle frekvence. Vidíme, že C a A, které jsou naše 2 nejnižších frekvencí. Máme vytvořit nadřazený uzel, a že nadřazený uzel nemá písmeno s ním spojené, ale má frekvenci, která je součtem. Součet stane 2 + 4, což je 6. Pak se vydáme po levé větev. Pokud jsme byli v té 6 uzlu, pak bychom následovat 0 dostat se do C a pak 1 se dostat do A. Takže teď máme 2 uzly. Máme hodnotu 6 a pak také další uzel s hodnotou 6. A tak ti, 2 nejsou jen 2 nejnižší, ale také jen 2, které jsou vlevo, tak jsme připojit se k těm jiným rodičem, s suma je 12. Takže tady máme Huffmanova stromu kde se dostat do B, to by bylo prostě bit 1 a pak se dostat do budeme mít 01, a pak C s 00. Takže zde vidíme, že v podstatě jsme zastupující tyto znaky s 1 nebo 2 bity kde B, jak předpovídal, má nejméně. A pak jsme očekávali C mají nejvíce, ale protože je to takový malý Huffman strom, pak je také reprezentována 2 bitů oproti někde uprostřed. 

Stačí si projít další jednoduchý příklad stromu Huffman, že máte řetězec "Hello." Co uděláte jako první byste říci, jak kolikrát se H objevit v tomto? H se objeví jednou a pak e se objeví jednou a pak jsme l objevilo dvakrát a o objevují jednou. A pak se můžeme očekávat, které písmeno bude zastoupena nejmenším počtem bitů? [Student] l. >> L. Jo. l má pravdu. Předpokládáme l být zastoupen nejmenším počtem bitů proto, že jsem se používá nejčastěji v řetězci "Hello." Co budu dělat, teď je čerpat z těchto uzlů. Mám 1, který je H, a pak ještě 1, což je e, a pak se 1, což je o - teď jsem seřízení - a pak 2, který je l. Pak jsem řekl tak, že jsem postavit Huffman strom je najít 2 uzly s nejméně frekvencí a aby jim sourozence vytvořením nadřazený uzel. Zde máme 3 uzly s nejnižší frekvencí. Všichni jsou 1. Tak tady jsme si vybrat, který z nich budeme propojit první. Řekněme, že jsem si vybrat H a E. Součet 1 + 1 = 2, ale tento uzel nemá písmeno s ním spojené. Je to jen má hodnotu. Nyní se podíváme na další 2 nejnižších frekvencí. To je 2 a 1. To by mohlo být jedním z těch 2, ale budu si vybrat tento jeden. Součet je 3. A pak konečně, mám jen 2 vlevo, tak pak to bude 5. Pak zde, jak se očekávalo, když jsem vyplnit kódování pro to, 1s se vždy ten správný obor a 0s je levá. Pak máme l reprezentovaný pouze 1 bit a pak na Õ 2 a pak e o 2 a pak H klesá na 3 bitů. Takže můžete přenášet tuto zprávu "Hello" namísto skutečně použití znaků jen o 0s a 1s. Pamatujte však, že v několika případech jsme měli vztahy s naší frekvencí. Mohli jsme buď připojil k H a o První možná. Nebo pak o něco později, když jsme měli l představované 2 , jakož i připojil které reprezentuje 2, mohli jsme spojeny buď jeden. 

A tak, když pošlete 0s a 1s, že ve skutečnosti nezaručuje že příjemce může plně číst zprávy hned bat protože nemusí vědět, kdy rozhodnutí jste udělali. Takže když máme co do činění s kompresí Huffman, nějak musíme říct příjemce našeho poselství, jak jsme se rozhodli - Potřebují vědět, nějaké další informace kromě zprávy stlačeného vzduchu. Je třeba, aby pochopili, co strom vlastně vypadá, jak jsme vlastně dělal ty rozhodnutí. 

Zde jsme dělali jen to, příklady založené na skutečné počtu, ale někdy může mít také Huffman strom na základě frekvenci, při které se objeví písmena, a to je přesně stejný postup. Tady jsem vyjádřit to v procentech nebo zlomkem a tak zde přesně to samé. Zjistil jsem, 2 nejnižší, shrnout je, další 2 nejnižší, shrnout je, až budu mít plnou strom. I když bychom mohli udělat to buď tak, když máme co do činění s procenty, to znamená, že jsme rozdělení věci a nakládání s desetinných míst, či spíše plave pokud budeme přemýšlet o datových struktur hlavy. Co víme o plováky? Co je to běžný problém, kdy máme co do činění s plováky? [Student] Nepřesné aritmetika. Jo >>. Nepřesnost. Vzhledem k tomu, v pohyblivé řádové čárce nepřesnosti, pro tento PSet tak, že se ujistit, že abychom neztratili žádné hodnoty, pak jsme vlastně bude jednat s hrabětem. Takže pokud jste měli myslet na uzlu Huffman, když se podíváte zpět do struktury zde, když se podíváte na zelených má frekvenci s ním spojené stejně jako to ukazuje na uzel na jeho levé straně, stejně jako uzel na jeho pravé straně. Potom červený ty tam také mají charakter jsou s nimi spojeny. Nebudeme dělat samostatné ty pro rodiče a pak koncových uzlů, které označujeme jako listy, ale spíše těch budou muset jen hodnoty NULL. Pro každý uzel budeme mít charakter, symbol, že uzel reprezentuje, pak frekvence, stejně jako ukazatel na jeho levé dítě, stejně jako jeho pravé dítě. Listy, které jsou na samém dně, by také mít uzlů odkazy po jejich levici a jejich práva, ale protože tyto hodnoty nejsou poukazem na skutečné uzly, co by jejich hodnota byla? >> [Student] NULL. >> NULL. Přesně tak. Zde je příklad toho, jak by se Vám mohl představovat frekvenci v plováky, ale budeme jednat s ním s celými čísly, takže vše, co udělal, je změnit datový typ tam. 

Pojďme na trochu více komplexní příklad. Ale teď, když jsme udělali jednoduché ty, je to jen stejný proces. Můžete najít 2 nejnižších kmitočtů, sečíst frekvence a to je nová frekvence vašeho nadřazeného uzlu, který pak ukazuje na jeho levé straně s 0 pobočky a právo s 1 pobočkou. Pokud máme řetězec "To je cs50," pak budeme počítat, kolikrát je T uvedeno, h zmíněno, i, s, c, 5, 0. Pak to, co jsem udělal tu je s červenými uzly jsem zasadil, Řekl jsem, že budu mít tyto znaky nakonec na dně mého stromu. Ti budou mít všechny listy. Pak to, co jsem udělal je, že jsem seřazena je podle četnosti ve vzestupném pořadí, a to je vlastně způsob, že Pset kód dělá Je to druhy to tím, že frekvence a pak podle abecedy. Tak to má čísla první a pak abecedně podle frekvence. Tak co bych udělal je, že jsem se najít 2 nejnižší. To je 0 a 5. Chtěl bych shrnout je, a to je 2. Pak bych pokračovat, najít další 2 nejnižší. To jsou dva 1s, a pak ty, se 2, jakož. Teď vím, že můj další krok bude se připojí nejnižší číslo, který je T, 1, a potom výběrem jednoho z uzlů, které má dvě jako frekvence. Takže tu máme 3 možnosti. Co budu dělat po snímku je jen vizuálně změnit jejich pořadí pro vás takže můžete vidět, jak jsem buduje. Co kód a vaše distribuce kód bude dělat by se připojit k T jeden s 0 a 5 uzlu. Takže, že částky na 3, a pak budeme pokračovat v procesu. 2 a 2 jsou nyní nejnižší, takže pak ty součet pro 4. Každý po tak daleko? Dobře. Pak po tom máme 3 a 3, které je třeba sečíst, 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á. Pak máme 6, a pak se naše poslední krok je nyní, že máme jen 2 uzly Shrneme ty, aby se kořen našeho stromu, což je 10. A číslo 10 dává smysl, protože každý uzel představuje, jejich hodnota, jejich četnost číslo, bylo kolikrát se objevily v řetězci, a pak máme 5 znaků v našem řetězci, tak to dává smysl. Podíváme-li se na to, jak se budeme skutečně zakódovat, podle očekávání, i a y, které se objevují nejčastěji jsou zastoupeny nejmenším počtem bitů. 

Buďte opatrní. V stromů Huffman případ skutečně záleží. Velká S se liší malým s. Pokud bychom měli "To je CS50" s velkými písmeny, pak malá s by se zobrazí pouze dvakrát, by uzel s 2 jako jeho hodnotu, a pak se velká S by pouze jednou. Takže váš strom by se změnily struktury, protože máte skutečně zvláštní list zde. Ale částka bude stále 10. To je to, co jsme vlastně bude volat kontrolní součet, přidání všech směrech. 

Teď, když jsme probrali Huffman stromy, můžeme se ponořit do Puff Huff'n se PSet. Budeme začít s částí otázek, a to bude vám zvyklí s binárními stromy a jak pracovat kolem toho: kreslení uzly, vytvořit si vlastní typedef struct pro uzel, a vidět, jak byste mohli vložit do binárního stromu, jeden, který je seřazena, křížení je, a podobné věci. Že znalosti se určitě pomůže, když se ponoříte do části Puff Huff'n z PSet. Ve standardním vydání PSet, vaším úkolem je realizovat Puff, a ve hacker verzi vaším úkolem je realizovat Huff. Co Huff dělá, je, že trvá textu a pak to překládá do 0s a 1s, tak proces, který jsme udělali výše, kde jsme napočítali frekvence a pak se na strom a pak řekl: "Jak se dostanu T?" T je zastoupena 100, a podobné věci, a pak Huff by se text a pak výstupní že binární. Ale také proto, že víme, že chceme, aby náš příjemce zprávy znovu přesně stejný strom, ale také obsahuje informace o frekvenčních počítá. Pak se Puff je nám dán binární soubor 0s a 1s a vzhledem k tomu i informace o frekvencích. Překládáme všechny ty 0s a 1s zpět do původní zprávy, která byla, takže jsme dekomprese, že. Pokud děláte standardní edici, nemusíte provádět Huff, takže pak stačí použít zaměstnanců provádění Huff. Tam jsou instrukce v spec o tom, jak to udělat. Můžete spustit zaměstnance provádění Huff na určité textového souboru a pak použít tento výstup jako vstup Puff. 

Jak jsem již zmínil dříve, máme spoustu distribuce kódu pro tento jeden. Chystám se začít chodit přes něj. Budu trávit většinu času na. H soubory protože v. soubory C, protože máme. H a že nám poskytuje prototypy funkcí, nemáme plně nutné přesně pochopit - Pokud nechcete pochopit, co se děje v. Soubory C, pak se nemusíte starat moc, ale rozhodně zkuste se podívat, protože by to mohlo dát nějaké rady a je užitečné si zvyknout na čtení kódu jiných lidí. 

Při pohledu na huffile.h, do komentářů, že deklaruje vrstvu abstrakce pro Huffman-kódované soubory. Pokud půjdeme dolů, vidíme, že je maximálně 256 znaků, které bychom mohli potřebovat kódy. To zahrnuje všechna písmena abecedy - velká a malá - a pak symboly a čísla, atd. Pak zde máme magic number, který stanovil Huffman kódovaný soubor. V rámci kódu Huffman, že budeš mít určitý magické číslo spojený s záhlaví. To může vypadat jako jen náhodné magické číslo, ale pokud jste skutečně přeložit do ASCII, pak to vlastně vysvětluje rozzlobit. Zde máme struct pro Huffman kódování souboru. Je tu všechny tyto charakteristiky spojené se souborem Huff. Pak tady máme hlavičku pro soubor Huff, tak říkáme, že Huffeader namísto přidání další h, protože to zní stejně tak. Cute. Máme kouzelné číslo s ním spojené. Pokud je to skutečný Huff soubor, to bude číslo nahoře, to kouzlo jeden. A pak to bude mít pole. Tak pro každý symbol, který je 256, bude to seznam toho, co četnost těchto symbolů je v souboru Huff. A pak konečně, máme kontrolní součet kmitočtů, , které by měly být součet těchto frekvencí. Tak to je to, co Huffeader je. Pak máme některé funkce, které vracejí další bit v souboru Huff stejně jako zapíše bit souboru Huff, a pak se tato funkce zde, hfclose, které skutečně zavře soubor Huff. Dříve jsme se zabývali přímo jen fclose, ale když máte soubor Huff, místo toho, aby ji fclosing co jste vlastně dělat, je hfclose a hfopen ji. To jsou specifické funkce Huffová soubory, které budeme k řešení. Pak zde čteme v záhlaví a pak psát záhlaví. 

Jen tím, že čtení. H soubor můžeme trochu získat pocit z toho, co soubor Huff může být, jaké vlastnosti má, aniž by se skutečně jít do huffile.c, které, pokud bychom ponořit, bude trochu složitější. Má všechny souboru I / O tu se zabývá ukazateli. Zde vidíme, že když voláme hfread, například, je to stále vypořádává s fread. Nejsme zbavit těchto funkcí zcela, ale posíláme, které mají být postaráno uvnitř souboru Huff místo dělá vše pro to sami. Můžete klidně prohledá to, pokud jste zvědaví, a jít a kůra vrstvě zadní trochu. 

Další obrázek, který budeme podívat se na tree.h. Předtím v Walkthrough sklouzne jsme řekli, očekáváme Huffmanova uzel a udělali jsme typedef struct uzel. Očekáváme, že mají symbol, frekvence, a pak 2 uzlů hvězdy. V tomto případě, co děláme, je to v podstatě stejný kromě namísto uzlu budeme nazývat stromy. Máme funkci, která při volání, aby strom to vrátí vám strom ukazatel. Zpět na Speller, když jste dělali nový uzel jste řekl uzel * nové slovo = malloc (sizeof) a podobné věci. V podstatě, mktree se bude zabývat, že pro vás. Podobně, pokud chcete odstranit strom, tak to je v podstatě uvolnění strom, když jste s ním udělal, místo aby byl explicitně volat zdarma na to, že jste ve skutečnosti jen tak použít funkci rmtree kde předáte ukazatel na daný strom a pak tree.c se postará o to pro vás. 

Díváme se do tree.c. Očekáváme, že stejné funkce, kromě nedočkalo realizace stejně. Jak jsme očekávali, když budete volat mktree to mallocs velikosti stromu do ukazatele, inicializuje všechny hodnoty s hodnotou NULL, takže 0s nebo hodnoty Null, a vrátí ukazatel na daný strom, který jste právě malloc'd pro vás. Zde, když zavoláte odstranit strom nejprve zajistí, že nejste double uvolnění. To zajišťuje, že budete mít ve skutečnosti strom, který chcete odebrat. Zde protože strom i své děti, Co to však je, že vyžaduje rekurzivně odstranit strom na levé uzel stromu stejně jako správné uzlu. Před tím, než se uvolní rodiče, je třeba osvobodit děti stejně. Parent je také zaměnitelný s kořenem. Vůbec první rodič, tak jako velký-velký-velký-velký-dědeček nebo babička strom, musíme nejprve uvolnit se stanoví úrovně první. Takže traverz až na dno, bez těch, a pak se vrátit nahoru, bez těch, atd. Tak to je strom. 

Nyní se podíváme na les. Forest je místo, kde můžete umístit všechny své stromy Huffman. Je to tím, že budeme mít něco jako plot , který obsahuje ukazatel na strom, stejně jako ukazatel na pozemku s názvem další. Jaká struktura se tento druh vypadat? Je to druh to říká tam. Přímo tady. Spojový seznam. Vidíme, že když máme pozemek je to jako propojeného seznamu parcel. Les je definován jako propojeného seznamu pozemků, a tak struktura lesa je, že se to jen tak, aby se ukazatel na první ploše a že pozemek má strom v něm, nebo spíše poukazuje ke stromu a pak se odkazuje na následující pozemku, tak dále a tak dále. Chcete-li les říkáme mkforest. Pak máme některé docela užitečné funkce zde. Máme vybrat, kde předáte v lese a pak návratová hodnota je strom *, ukazatel na strom. Co pick bude dělat, je, že půjde do lesa, že jste ukázal na pak odstraňte strom s nejnižším kmitočtu z toho lesa a pak vám ukazatel na ten strom. Jakmile zavoláte vybrat, bude strom neexistuje v lese už, ale návratová hodnota je ukazatel na ten strom. Pak máte rostlinu. Za předpokladu, že předáte ukazatel na strom, který má non-0 frekvenci, co rostlina bude dělat, je, že bude trvat do lesa, vezměte strom, a závod, který strom uvnitř lesa. Zde máme rmforest. Podobné odstranit strom, který v podstatě osvobodil všechny z našich stromů pro nás, odebrat les svobodná vůle vše obsažené v tomto lese. 

Podíváme-li se do forest.c, budeme očekávat, že alespoň 1 rmtree příkaz tam, protože na volné paměti v lese, pokud les má stromy v něm, pak nakonec budete muset odstranit ty stromy taky. Podíváme-li se do forest.c, máme mkforest, což je, jak jsme očekávali. My malloc věci. Jsme inicializaci první pozemek v lese jako NULL, protože je prázdná začít, pak vidíme, vybrat, které vrací strom s nejnižší váhou, nejnižší frekvence, a pak zbaví daného uzlu, který odkazuje na ten strom a ten příští, tak to trvá, že z propojeného seznamu lesa. A pak tu máme závod, který vloží stromu do propojeného seznamu. Co les dělá, je to pěkně drží to jsou seřazena pro nás. A pak konečně, máme rmforest a, jak se očekávalo, máme rmtree vzýval tam. 

Při pohledu na distribuční kód tak daleko, huffile.c byl pravděpodobně zdaleka nejtěžší pochopit, vzhledem k tomu, dalších souborů sami byli docela jednoduché následovat. Při naší znalosti ukazatelů a vzájemně provázaných seznamů a takových, jsme byli schopni sledovat docela dobře. Ale všechno, co potřebujeme opravdu ujistit, že plně chápeme je. H soubory protože je třeba, aby se volání těchto funkcí, které se zabývají těmito návratové hodnoty, takže se ujistěte, že jste plně porozuměli, jaká akce se bude provádět kdykoliv volat jednu z těchto funkcí. Ale ve skutečnosti porozumění uvnitř ní není zcela nutné, protože máme ty. H soubory. Máme 2 další soubory, které zůstaly v naší distribuční kódu. 

Pojďme se podívat na skládce. Dump jeho komentáři zde trvá Huffman-komprimovaný soubor a pak překládá a skládky všichni její obsah ven. Zde vidíme, že je to volání hfopen. To je druh zrcadlení soubor * vstup = fopen, a pak se projít v informaci. Je to téměř identické, s výjimkou místo souboru * jste procházející v Huffile; místo fopen jste mimochodem v hfopen. Zde čteme v záhlaví první, který je tak trochu podobné tomu, jak čteme v záhlaví pro bitmapový soubor. Co tady děláme je kontrola, zda informace v hlavičce obsahuje správné magické číslo, které označuje, že je to skutečný Huff soubor, pak všechny tyto kontroly, aby se ujistil, že soubor, který jsme otevřený je skutečný rozzlobil soubor, nebo ne. Co to však je, že výstupy frekvence všech symbolů, které můžeme vidět v rámci terminálu do grafického tabulky. Tato část bude užitečná. Má trochu a čte kousek po kousku do proměnné bit a pak vytiskne ji. Takže pokud bych měl zavolat skládku na hth.bin, která je výsledkem rozzlobí souboru pomocí zaměstnanců řešení, bych si to. Je to výstup všech těchto znaků a pak uvedení frekvenci, při které se objeví. Podíváme-li se, většina z nich jsou 0s kromě toho: H, který se objeví dvakrát, a pak T, která se objeví jednou. A pak tu máme skutečný zprávu 0s a 1s. Pokud se podíváme na hth.txt, což je pravděpodobně původní zprávy, která byla odfrkl, očekáváme nějaké Hs a TS tam. Konkrétně, očekáváme jen 1 T a 2 HS. Tady jsme v hth.txt. To má skutečně HTH. Zahrnuty tam, ačkoli my nemůžeme vidět, je znak nového řádku. Soubor Huff hth.bin je také kódování znaku nového řádku stejně. Zde protože víme, že řád je HTH a pak nový řádek, je vidět, že asi H je reprezentována jen jedním 1 a pak T je pravděpodobně 01 a pak další H 1, stejně a pak máme nový řádek označena dvěma 0s. Cool. 

A pak konečně, protože máme co do činění s více. C a. H soubory, budeme mít pěkně složitá argument kompilátor, a tak zde máme Makefile, které umožňuje výpis pro vás. Ale ve skutečnosti, budete muset jít o tom své vlastní puff.c soubor. Makefile vlastně neřeší dělat puff.c pro vás. Odjíždíme, že na vás upravit Makefile. Když zadáte příkaz, jako je, aby všem, například, bude to dělat všechny z nich pro vás. Neváhejte se podívat na příklady Makefile z minulého PSet stejně jako jít pryč z tohohle vidět, jak byste měli být schopni, aby se váš Puff soubor úpravou tohoto souboru Makefile. To je asi tak pro náš distribuční kódu. 

Jakmile jsme se dostali přes to, že pak je tu jen další připomínkou toho, o tom, jak budeme jednat s uzly Huffman. Nebudeme se volat je uzliny už, budeme se nazývat stromy kde budeme zastupovat jejich symbol, char, jejich frekvence, počet výskytů, s celé číslo. Používáme to, protože to je to přesnější než plováku. A pak máme další ukazatel na levé dítěte stejně jako pravé dítě. Les, jak jsme viděli, je jen provázaný seznam stromů. Nakonec, když jsme budování naší Huff soubor, chceme, aby naše lesy obsahovat pouze 1 strom - 1 strom, 1 root s více dětmi. Dříve, když jsme byli jen, že naše Huffman stromy, jsme začali tím všechny uzly na naší obrazovce a říkat budeme mít tyto uzly, nakonec se budeš listy, a to je jejich symbol, je to jejich četnost. V našem lese, kdybychom se 3 písmena, to je les 3 stromů. A pak, jak budeme pokračovat, když jsme přidali první rodiče, jsme se les 2 stromů. Odstranili jsme 2 z těchto dětí z našeho lesa a pak nahradil ji nadřazeného uzlu že měl ty 2 uzly jako děti. A pak konečně, naše poslední krok s výrobou náš příklad s As, Bs, a Cs by ke konečnému rodiče, a tak, pak by to přinést naše celkové počtu stromů v lese na 1. Má každý vidět, jak se začít s několika stromy v lese a skončit s 1? Dobře. Cool. 

Co musíme udělat pro Puff? Co musíme udělat, je zajistit, že jako vždy, nám dávají ten správný typ vstupu tak, že se může ve skutečnosti spustit program. V tomto případě jsou to bude, že nám po jejich prvním argument příkazového řádku 2 více: soubor, který chceme dekomprimovat a výstup dekomprimovaného souboru. Ale jakmile jsme se ujistili, že kolem nás ve správném množství hodnot, Chceme zajistit, aby vstup je soubor Huff, nebo ne. A pak ještě jednou vám zaručit, že je to soubor Huff, pak chceme budovat náš strom, vybudovat strom tak, že odpovídá strom, že osoba, která zaslala zprávu postavený. Pak po stavíme strom, pak se můžeme zabývat 0s a 1s, že prošel v roce, těm, které spolu náš strom, protože je to stejné, a pak napsat, že poselství, interpretovat bity zpět do znaků. A pak na konci, protože máme co do činění s ukazateli tady, Chceme se ujistit, že nemáme žádné úniky paměti a že jsme volní všechno. 

Zajištění řádného využití je starý klobouk pro nás teď. Bereme v vstup, který bude název souboru nafouknout, a pak jsme se specifikovat výstup, takže název souboru pro želírovacího výstup, který bude textový soubor. To je s nimi nakládáno. A teď chceme zajistit, že vstup je rozzlobil, nebo ne. Když vzpomínám, bylo něco, co v distribuční kódu, který nám může pomoci s pochopením, zda je soubor rozzlobil, nebo ne? Tam byly informace v huffile.c o Huffeader. Víme, že každý soubor Huff má Huffeader s ním spojené s kouzelným číslem , jakož i řada frekvencí pro každý symbol stejně jako kontrolní součet. Víme, že, ale také se nahlédnout na dump.c, , ve kterém bylo čtení do souboru Huff. A tak k tomu, že to mělo ověřit, zda skutečně byl rozzlobil, nebo ne. Takže možná bychom mohli použít dump.c jako struktury pro naše puff.c. Zpět na PSet 4, když jsme měli soubor copy.c, že ​​zkopírovali v trojicích RGB a my vykládat, že pro detektivka a změny velikosti, podobně, co byste mohli udělat, je stačí spustit příkaz jako cp dump.c puff.c a použít některé z kódu tam. Nicméně, to nebude tak jednoduché procesu pro překládání si dump.c do puff.c, ale aspoň to vám dává někde začít o tom, jak zajistit, aby vstup je skutečně odfrkl, nebo ne stejně jako pár dalších věcí. Jsme zajistili správné použití a zajistit, aby vstup rozzlobil. Pokaždé, když jsme udělali, že jsme udělali naši správnou kontrolu chyb, tak vrací a ukončení funkce, pokud některé dojde k selhání, v případě, že je problém. 

Teď, co chceme udělat, je vytvořit skutečný strom. Podíváme-li se v lese, tam jsou 2 hlavní funkce že budeme chtít, aby se velmi dobře. Tam je booleovská funkce rostlina, která rostliny non-0 Frekvence strom v našem lese. A tak tam předáte ukazatel na les a ukazatel na strom. Rychlý dotaz: Kolik lesy budete mít, když stavíte Huffman strom? Naše les je jako náš plátno, ne? Takže jsme jen bude mít 1 les, ale budeme mít více stromů. Takže předtím, než zavoláte zařízení, budete pravděpodobně chtít, aby váš les. K dispozici je příkaz pro které, když se podíváte do forest.h o tom, jak můžete udělat les. Můžete zasadit strom. Víme, jak na to. A pak si můžete také vybrat strom z lesa, odstranění stromu s nejnižší váhou a dává vám ukazatel na to. Vzpomínal, když jsme dělali v příkladech sami, když jsme byli kreslení to, jsme prostě jen přidali odkazy. Ale tady ne jen přidávání odkazů, myslet na to spíš jako jste odstranění 2 těchto uzlů a pak nahrazovat ji jinou. Chcete-li vyjádřit, že pokud jde o sběr a pěstování, jste vychystávání 2 stromy a pak výsadba další strom že má ty 2 stromy, které jste si vybrali jako děti. Chcete-li vytvořit Huffman je strom, si můžete přečíst v symboly a frekvence v pořadí protože Huffeader dává, že na vás, vám dává řadu frekvencí. Takže můžete jít dopředu a jen tak ignorovat cokoli s 0 v něm protože nechceme 256 listy na konci toho. Chceme pouze počet listů, které jsou znaky , které jsou ve skutečnosti používá v souboru. Si můžete přečíst v těchto symbolů, a každý z těchto symbolů, které mají non-0 frekvencí, ty se bude stromy. Co můžete udělat, je pokaždé, když si přečetl v non-0 frekvence symbol, můžete zasadit ten strom v lese. Jakmile zasadit stromy v lese, můžete se připojit ty stromy jako sourozenci, tak vrací k výsadbě a vybírání, kde si vyberete 2 a pak závod 1, kde to 1, která vás rostlin je rodič na 2 děti, které si vybral. Takže pak se vaše konečný výsledek bude jediný strom v lese. To je, jak si postavit svůj strom. 

Existuje několik věcí, které by mohly pokazit zde protože máme co do činění s výrobou nových stromů a nakládání s ukazateli a podobné věci. Než když jsme se zabývali ukazateli, když jsme malloc'd jsme chtěli, aby se ujistil, že se nevrátil nám NULL ukazatel hodnotu. Takže na několika krocích v rámci tohoto procesu jsou bude několik případů kde váš program by mohl selhat. Co chcete udělat, je se chcete ujistit, že řešíte tyto chyby, a ve spec říká s nimi elegantně, tak jako vytisknout zprávu uživateli řekněte jim, proč musí program ukončit a pak rychle ukončete ji. Chcete-li tuto chyb, pamatujte, že chcete zkontrolovat pokaždé, že by mohlo být selhání. Pokaždé, že děláš nový ukazatel Chcete, aby se ujistil, že je úspěšný. Než to, co jsme udělat, je vytvořit nový ukazatel a malloc ji, a pak bychom zkontrolovat, zda je ukazatel NULL. Takže tam se bude některé příklady, kde můžete jen udělat to, ale někdy jste vlastně volání funkce av rámci této funkce, že je to ten, který dělá na mallocing. V tomto případě, pokud se podíváme zpět do některé z funkcí v kódu, Některé z nich jsou logické funkce. V abstraktní případě, pokud máme logický funkce s názvem foo, v podstatě, lze předpokládat, že kromě tom, co foo dělá, protože je to booleovská funkce, vrací true nebo false - true, pokud úspěšný, false v opačném případě. Takže chceme zjistit, zda návratová hodnota foo je true nebo false. Pokud je to false, což znamená, že budeme chtít vytisknout nějakou zprávu a pak ukončete program. Co chceme udělat, je zkontrolovat vrácenou hodnotu foo. Pokud foo vrátí false, pak víme, že jsme se setkali s nějakou chybou a musíme přestat náš program. Způsob, jak to udělat, je mít stav, kdy skutečná funkce sama o sobě je Váš zdravotní stav. Řekněme, že foo bere v x. Můžeme mít jako podmínku if (foo (x)). V podstatě to znamená, že pokud na konci provádění foo vrací pravda, pak můžeme udělat, protože funkce musí vyhodnotit foo aby bylo možno vyhodnotit celý stav. Takže je to, jak můžete něco udělat, pokud funkce vrací hodnotu true a je úspěšný. Ale když jste kontrolu chyb, si jen chcete ukončit, pokud je vaše funkce vrátí false. Co můžete udělat, je jen přidat == false, nebo jen přidat třesku před ním a pak máte if (! foo). V rámci tohoto orgánu tohoto stavu byste mít všechny chyb, tak jako, "Nepodařilo se vytvořit tento strom" a pak se vrátit 1, nebo něco takového. Co to dělá, když je to, že i když foo vrátil false - Řekněme, že foo vrací hodnotu true. Pak nemusíte volat foo znovu. To je mylná představa,. Vzhledem k tomu, že byl ve svém stavu, je to již vyhodnocen, takže už máte výsledek, pokud používáte, aby strom nebo něco takového nebo zařízení nebo pick, nebo tak něco. To už má tuto hodnotu. Je to již proveden. Takže je to vhodné použít booleovské funkce jako podmínku protože ať už jste či nejste skutečně spustit tělo smyčky, spustí funkci stejně. 

Náš druhý na poslední krok je psaní zprávy do souboru. Jakmile budeme budovat Huffman strom, pak psaní zprávy do souboru je velice jednoduché. Je to docela jednoduché nyní stačí následovat 0s a 1s. A tak podle konvence víme, že na stromě Huffman uveďte opustil 0s a 1s uvést pravdu. Takže pokud budete číst v kousek po kousku, pokaždé, když dostanete 0 budete sledovat levá větev, a pak pokaždé, když si přečetl v 1 budete následovat správnou větev. A pak budete pokračovat, dokud nenarazíte na list protože listy se bude na konci větví. Jak můžeme zjistit, zda jsme hit list nebo ne? Řekli jsme, že to předtím. [Student] Pokud ukazatele jsou NULL. Jo >>. Můžeme říct, jestli jsme hit list v případě, že ukazatele na obou levý a pravý stromy jsou NULL. Perfect. Víme, že chceme číst v kousek po kousku do našeho souboru Huff. Jak jsme viděli dříve v dump.c, co udělali, je, že si v kousek po kousku do souboru Huff a jen vytisknout to, co ty kousky byly. Nebudeme se s tím. Budeme dělat něco, co je trochu složitější. Ale co můžeme udělat, je, že jsme si vzít ten kousek kódu, který čte do bitu. Zde máme integer bit představující aktuální bit, který jsme na. To se stará o iterací všechny bity v souboru, dokud nenarazíte na konec souboru. Na základě toho, pak budete chtít mít nějaký iterátoru přejít na strom. A pak na základě toho, zda je bit 0 nebo 1, budete chtít, aby buď přesunout tento iterátor vlevo nebo ji přesunout doprava celou cestu, dokud nenarazíte na list, takže celá cesta až do tohoto uzlu, který jste na neukazuje na nic víc uzlů. Proč můžeme udělat se souborem Huffman, ale ne Morse kódu? Vzhledem k tomu, v Morseově abecedě je tu trochu dvojznačnosti. Mohli bychom být jako, oh čekat, jsme hit dopis na cestě, takže možná to je naše dopis, vzhledem k tomu, jestli jsme pokračovali jen trochu déle, pak bychom zasáhli další dopis. Ale to se nestane v kódování Huffman, takže můžeme být jisti, že jediný způsob, jak budeme hit charakter Je-li tento uzel je levá a pravá děti jsou NULL. 

Konečně, chceme osvobodit všechny naše paměť. Chceme, aby i konci souboru Huff, že jsme se zabýváme stejně jako odstranění všech stromů v našem lese. Na základě vaší implementaci, budete pravděpodobně chtít volat odstranit les místo skutečně prochází všechny stromy sami. Ale pokud jste provedli nějaké dočasné stromy, budete chtít uvolnit, že. Víš svůj kód nejlépe, takže víte, kde jste přidělování paměti. A tak pokud jdete do, začněte tím, dokonce kontrolu F'ing pro malloc, vidět kdykoliv malloc a ujistěte se, že jste uvolnit všechno ale pak právě prochází kódu, porozumění, kde jste mohli přidělena paměť. Obvykle můžete jen říct, "Na konci souboru Já jsem prostě jít na odstranění les na mém lese," takže v podstatě jasné, že paměť, zdarma, které, "A pak jsem také chystá zavřete soubor a potom můj program bude přestat." Ale je to jediný čas, který váš program ukončí? Ne, protože někdy tam mohlo být chyba, co se stalo. Možná jsme nemohli otevřít soubor nebo my jsme nemohli provést další strom nebo nějaký druh chyby se stalo v procesu přidělení paměti, a tak se vrátil NULL. Došlo k chybě, a pak jsme se vrátili a ukončete. Takže chcete, aby se ujistil, že případná čas, že váš program může přestat kouřit, Chcete-li uvolnit všechny své paměti tam. Není to jen tak na samém konci hlavní funkce, které ukončete kód. Chceš se podívat zpět na každém stupni, že váš kód potenciálně mohl vrátit předčasně a pak zdarma bez ohledu na paměti smysl. Řekněte, že jste zavolal, aby les a že se vrátil false. Pak jste pravděpodobně nebudete potřebovat odstranit svůj les protože nemáte lesa dosud. Ale v každém bodě v kódu, kde může vrátit předčasně chcete, aby se ujistil, že jste uvolnit případné paměť. 

Takže když máme co do činění s uvolněním paměti a mají potenciální úniky, chceme využívat nejen náš úsudek a naše logika ale také použít Valgrind k určení, zda máme uvolněna veškerá naší paměti správně, nebo ne. Můžete buď spustit Valgrind na Puff a pak se budete muset také předat jej správný počet argumentů příkazového řádku pro Valgrind. Můžete spustit, ale výstup je trochu mystický. Dostali jsme se trochu na to zvyklí u Speller, ale stále potřebujeme trochu více pomoci, takže pak běží to s několika dalšími příznaky, jako je únik-check = full, které budou pravděpodobně nám nějaké další užitečné výstup na Valgrind. 

Pak další užitečné tip, když jste ladění je příkaz diff. Můžete přistupovat k pracovníkům za provádění Huff, spusťte, že na textový soubor, a pak výstup do binárního souboru, binární soubor Huff, být konkrétní. Pak, pokud se dostanete svůj vlastní obláček na tomto binární soubor, pak v ideálním případě, vaše výstup textový soubor bude totožný k původní, který prošel dovnitř Zde jsem pomocí hth.txt jako příklad, a to je ten mluvil o ve vašem spec. To je doslova HTH a pak nový řádek. Ale rozhodně neváhejte a jste určitě doporučujeme používat delší příklady pro textovém souboru. 

Můžete si dokonce vzít si na mušku možná kompresi a dekompresi pak některé ze souborů, které jste použili v Speller jako Vojna a mír nebo Jane Austen, nebo něco takového - to by bylo docela fajn - nebo Austin Powers, druh jednání s většími soubory, protože bychom přišli na věc pokud jsme použili na další nástroj zde, ls-l. Jsme zvyklí na ls, která v podstatě uvádí všechny obsah v našem aktuálním adresáři. Předávání v vlajky-l skutečně zobrazuje velikost těchto souborů. Pokud projdete spec PSet, to vlastně vás provede vytvořením binární soubor, ze dne rozzlobí ho, a uvidíte, že pro velmi malé soubory prostor náklady na kompresi, a překládat všechny tyto informace všech frekvencí a podobné věci, které převáží skutečné výhody kompresi souboru na prvním místě. 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 v kompresi těchto souborů. 

A pak konečně, máme starý kamarád GDB, který je určitě přijde vhod také. 

Ještě budeme mít nějaké otázky, na stromech Huff nebo procesu snad dělat stromy nebo jakékoli jiné otázky týkající se Puff Huff'n? Dobře. Zůstanu asi na chvíli. 

Díky, všichni. To bylo Návod 6. A hodně štěstí. 

[CS50.TV]