[Powered by Google Translate] [Walkthrough - Probleem Set 6] [Zamyla Chan - Harvard University] [Dit is CS50. - CS50.TV] 

Hallo, iedereen, en welkom bij Walkthrough 6: Huff'n Puff. In Huff'n Puff wat we doen gaat te maken met een Huffman gecomprimeerd bestand en dan puffen het back-up, dus decomprimeren, zodat wij kunnen vertalen van de 0s en 1s dat de gebruiker stuurt ons en het omzetten terug in de oorspronkelijke tekst. Pset 6 gaat worden wel cool, want je gaat een aantal van de gereedschappen te zien die u hebt gebruikt in PSET 4 en PSET 5 en soort van ze te combineren in een vrij netjes begrip wanneer kom je over na te denken. 

Ook, misschien wel, PSET 4 en 5 waren de meest uitdagende psets die we te bieden had. Dus vanaf nu, we hebben dit nog 1 PSET in C, en dan na dat we op naar web programmeren. Dus feliciteren jezelf voor het krijgen van meer dan de zwaarste bult in CS50. 

Moving on voor Huff'n Puff, zijn onze toolbox voor deze PSET gaat worden Huffman bomen, dus begrijpen niet alleen hoe binaire bomen werken, maar ook specifiek Huffman bomen, hoe ze gebouwd. En dan gaan we een heleboel verdeelsleutel hebben in deze PSET, en we komen om dat daadwerkelijk te zien een aantal van de code we misschien niet in staat zijn om volledig te begrijpen nog, en dus die zal de. c bestanden, maar dan is hun bijbehorende. h-bestanden geeft ons genoeg begrip dat we nodig hebben, zodat we weten hoe deze functies werken of in ieder geval wat ze moeten doen - hun in-en uitgangen - zelfs als we niet weten wat er gebeurt in de zwarte doos of niet begrijpen wat er gebeurt in de zwarte doos binnen. En dan tot slot, zoals gewoonlijk, hebben we te maken met nieuwe data structuren, specifieke soorten knooppunten die wijzen op bepaalde dingen, en dus even met een pen en papier, niet alleen voor het ontwerp-proces en als je probeert te achterhalen hoe je PSET zou moeten werken maar ook tijdens debuggen. U kunt GDB naast uw pen en papier terwijl u op wat de waarden zijn, waar je pijltjes wijzen, en dat soort dingen. 

Laten we eerst eens kijken naar Huffman bomen. Huffman bomen zijn binaire bomen, wat betekent dat elke node slechts 2 kinderen heeft. In Huffman bomen het kenmerk is dat de meest voorkomende waarden worden vertegenwoordigd door de minst bits. We zagen in collegezaal voorbeelden van Morse-code, wat voor soort geconsolideerde sommige brieven. Als je probeert om een ​​A of een E, bijvoorbeeld vertalen, je die vaak vertalen, dus in plaats van het hebben van de volledige set van bits te gebruiken toegewezen voor die gebruikelijke data type, dat u comprimeren tot minder, en dan die brieven die worden vertegenwoordigd minder vaak worden weergegeven met een langere stukjes want je kunt veroorloven dat wanneer je weegt de frequenties die die brieven verschijnen. We hebben hetzelfde idee hier in Huffman bomen waar we het maken van een ketting, een soort pad om naar de bepaalde tekens. En dan de personages die het meest frequentie zullen worden weergegeven met de minste bits. 

De manier waarop u een Huffman boom te construeren is door het plaatsen van alle tekens die worden weergegeven in de tekst en het berekenen van de frequentie, hoe vaak ze verschijnen. Dit kan ofwel een telling van het aantal keren dat die brieven verschijnen of misschien een percentage van alle tekens hoeveel elk weergegeven. En dus wat je doet is als je eenmaal dat alles in kaart gebracht hebben, dan kijk je voor de 2 laagste frequenties en vervolgens hen te voegen als broers en zussen waarbij dan het ouderknooppunt een frequentie die de som is van de twee kinderen. En dan moet je volgens afspraak zeggen dat de linker knooppunt, volg je dat door het volgen van de 0 tak, en dan de meest rechtse knooppunt is de 1 tak. Zoals we zagen in Morse-code, de een gotcha was dat als je had gewoon een pieptoon en de pieptoon het was dubbelzinnig. Het kan ofwel een letter of het kan een sequentie van twee letters. En dus wat Huffman bomen doet is omdat door de aard van de personages of onze laatste feitelijke tekens als laatste knopen op de tak - we verwijzen naar die als bladeren - op grond van dat er geen sprake zijn van dubbelzinnigheid in termen van welke letter die u zoekt coderen met de reeks van bits want nergens langs de bits die 1 letter vertegenwoordigen komt u nog een hele brief, en er zal niet er enige verwarring. Maar we zullen ingaan op voorbeelden die jullie daadwerkelijk kan zien dat in plaats van ons alleen maar te vertellen dat dat waar is. 

Laten we eens kijken naar een eenvoudig voorbeeld van een Huffman boom. Ik heb een string hier dat is 12 tekens lang zijn. Ik heb 4 Zoals, 6 B's, en 2 Cs. Mijn eerste stap zou zijn om te tellen. Hoe vaak doet A verschijnen? Het verschijnt 4 keer in de string. B verschijnt 6 keer, en C 2 maal verschijnt. Natuurlijk, ik ga zeggen dat ik B met behulp van het meest, dus ik wil B vertegenwoordigen met het minste aantal bits, het laagste aantal van 0s en 1s. En dan ga ik ook gaan verwachten C om de meest bedrag van 0s en 1s nodig ook. Eerste wat ik hier heb is dat ik plaatste ze in oplopende volgorde in termen van frequentie. We zien dat de C en de A, dat zijn onze 2 laagste frequenties. We creëren een parent node, en die ouder knooppunt niet over een brief die ermee verbonden zijn, maar wel een frequentie, die de som is. De som wordt 2 + 4, op 6. Daarna volgen we de linker tak. Als we op dat 6 knooppunt, dan zouden we volgen op 0 om C en dan 1 om naar A. Dus nu hebben we 2 knopen. Wij hebben de waarde 6 en dan hebben we ook een ander knooppunt met de waarde 6. Enz. die 2 niet alleen de laagste twee maar alleen de 2 die links, dus we sluiten die door een andere ouder, waarbij de som wordt 12. Hier hebben we dus onze Huffman boom waar te krijgen naar B, dan zou dat wel eens de bit 1 en dan om naar A zouden we 01 en vervolgens C met 00. Dus hier zien we dat in feite dat we deze chars die met 1 of 2 bits waarbij de B, zoals voorspeld, de minste. En dan we hadden verwacht C om het meeste hebben, maar omdat het zo'n klein Huffman boom, vervolgens de A eveneens door 2 bits tegenover ergens in het midden. 

Gewoon om te gaan over een ander eenvoudig voorbeeld van de Huffman boom, zeggen dat je de string "Hallo." Wat je doet is eerst je zou zeggen hoe vaak heeft H verschijnt in dit? H verschijnt een keer en dan e verschijnt een keer en dan hebben we l verschijnen twee keer en o verschijnen keer. En zo is dan we verwachten welke letter te laten vertegenwoordigen door de minst aantal bits? [Student] l. >> L. Ja. l is gelijk. We verwachten l worden vertegenwoordigd door het minste aantal bits omdat ik het meest gebruikt in de string "Hallo." Wat ik nu ga doen is trekken uit deze knooppunten. Ik heb 1, dat H, en dan nog 1, dat e en een 1, dat o - nu ben ik ze in volgorde - en dan 2, dat is l. Dan zeg ik de manier waarop ik een Huffman boom te bouwen is het vinden van de 2 nodes met de minste frequenties en maken ze broers en zussen door een bovenliggende node. Hier hebben we 3 knopen met de laagste frequentie. Ze zijn allemaal 1. Dus hier zijn we kiezen welke we gaan eerst koppelen. Laten we zeggen dat ik de H en de e. De som van 1 + 1 is 2, maar dit knooppunt geen brief gekoppeld. Het houdt alleen de waarde. Nu gaan we kijken naar de volgende 2 laagste frequenties. Dat is 2 en 1. Dat zou een van deze twee zijn, maar ik ga dit een te kiezen. De som is 3. En dan tot slot, ik heb maar 2 links, dus dan dat wordt 5. Dan hier, zoals verwacht, als ik vul de codering voor, 1s zijn altijd de juiste tak en 0s zijn de linker. Dan hebben we l vertegenwoordigd door slechts 1 bit en vervolgens de o met 2 en de e met 2 en de H valt tot 3 bits. Dus u kan overbrengen dit bericht "Hello" in plaats van het daadwerkelijk gebruik van de tekens door gewoon 0s en 1s. Vergeet echter niet dat in een aantal gevallen hebben we banden met onze frequentie had. We konden beide hebben zich aangesloten bij de H en de o eerste misschien. Of later op toen we de l vertegenwoordigd door 2 en de samengevoegde dat voorgesteld door 2, kan ofwel een we hebben verbonden. 

En dus, wanneer u een van de 0s en 1s, die eigenlijk geen garantie dat de ontvanger kan uw bericht volledig te lezen recht uit de vleermuis omdat ze misschien niet weten welke beslissing je hebt gemaakt. Dus als we te maken hebben met Huffman compressie, een of andere manier moeten we de ontvanger van onze boodschap hoe we besloten te vertellen - Ze moeten een soort van extra informatie te kennen Naast de gecomprimeerde bericht. Ze moeten begrijpen wat de boom er daadwerkelijk uitziet, hoe we eigenlijk gemaakt die beslissingen. 

Hier werden we gewoon doen voorbeelden gebaseerd op de werkelijke telling, maar soms kun je ook een Huffman boom op basis van de frequentie waarmee letters verschijnen, en het is precies hetzelfde proces. Hier ben ik het uit te drukken in termen van percentages en een fractie, en dus even precies hetzelfde. Ik vind de 2 laagste, vatten ze de volgende 2 laagste, vatten ze, tot ik een volle boom. Ook al konden we het doen hoe dan ook, als we te maken hebben met percentages, dat betekent dat we dingen te delen en het omgaan met decimalen of liever drijft als we denken over datastructuren van een hoofd. Wat weten we over praalwagens? Wat is een veelvoorkomend probleem wanneer we te maken hebben met praalwagens? [Student] Onduidelijke rekenen. >> Ja. Onnauwkeurigheid. Door floating point onnauwkeurigheid, want dit PSET, zodat we er zeker van dat we geen waarden te verliezen, dan zijn we echt gaan te maken hebben met de telling. Dus als je te denken van een Huffman knoop, als je kijkt naar de structuur hier, als je kijkt naar de groene heeft een frequentie die ermee verbonden zijn en wijst op een knooppunt aan de linkerkant en een knooppunt aan de rechterkant. En dan de rode is er ook een karakter met hen verbonden. We gaan niet te scheiden's te maken voor de ouders en dan de laatste knopen, die we aanduiden als de bladeren, maar die zullen alleen maar NULL-waarden. Voor elke node hebben we een karakter, het symbool dat dat knooppunt vertegenwoordigt, dan een frequentie en een verwijzing naar de linker kind en de rechter kind. De bladeren, die helemaal onderaan, zou ook knooppunt pointers om hun linker-en aan de rechterkant, maar aangezien deze waarden niet verwijzen naar de werkelijke knooppunten, wat zou de waarde zijn? >> [Student] NULL. >> NULL. Precies. Hier is een voorbeeld van hoe u de frequentie te vertegenwoordigen in vlotters, maar we gaan maken te hebben met het met gehele getallen, dus alles wat ik deed is er het gegevenstype. 

Laten we verder gaan naar een beetje meer van een complex voorbeeld. Maar nu dat we de eenvoudige soorten gedaan, het is gewoon hetzelfde proces. U vindt de 2 laagste frequenties, de som van de frequenties en dat is de nieuwe frequentie van uw parent node, die wijst vervolgens aan de linkerkant met de 0 tak en rechts met de 1 tak. Als we de string "Dit is CS50," dan gaan we tellen hoe vaak wordt T genoemd, h genoemd, i, s, c, 5, 0. Maar wat ik hier heb gedaan is met de rode knopen ik net geplant, Ik zei dat ik ga uiteindelijk deze tekens aan de onderkant van mijn boom. Die zullen worden alle van de bladeren. Dan wat ik deed is dat ik ze gesorteerd op frequentie in oplopende volgorde, en dit is eigenlijk de manier waarop de PSET code het doet is het sorteert het door de frequentie en vervolgens alfabetisch. Dus het heeft de nummers en vervolgens alfabetisch op de frequentie. Dan wat ik zou doen is dat ik zou vinden van de 2 laagste. Dat is 0 en 5. Ik zou samenvatten hen, en dat is 2. Dan zou ik blijven, vinden de volgende 2 laagste. Dat zijn de twee 1s en die worden 2 en. Nu weet ik dat mijn volgende stap gaat worden de toetreding tot de laagste nummer, die de T, de 1 en met een van de knooppunten 2 heeft de frequentie. Hier hebben we dus 3 opties. Wat ik ga doen voor de dia is gewoon visueel herschikken ze voor u zodat u kunt zien hoe ik het opbouwen. Wat de code en je distributie code gaat doen zou toetreden tot de T een met de 0 en 5 node. Dus dan die bedragen tot en met 3, en dan hebben we het proces voort te zetten. De 2 en de 2 nu de laagste, dus dan die som tot 4. Iedereen volgt tot nu toe? Oke. Dan na dat we de 3 en de 3 die moeten worden opgeteld, dus nogmaals, ik ben gewoon te schakelen, zodat je kunt visueel zo zien dat het niet al te rommelig. Dan hebben we een 6, en dan is onze laatste stap is nu dat we slechts 2 nodes hebben we de som die aan de wortel van onze boom, dat is 10 te maken. En het getal 10 is logisch, want elk knooppunt vertegenwoordigd, hun waarde, hun frequentie-nummer, was hoe vaak ze verscheen in de reeks, en dan hebben we 5 karakters hebben in onze reeks, dus dat maakt zin. Als we kijken omhoog naar hoe we zouden eigenlijk coderen, zoals verwacht, de i en s, die verschijnen de meest worden voorgesteld door de kleinste aantal bits. 

Wees hier voorzichtig. In Huffman bomen het geval van belang eigenlijk. Een hoofdletter S is anders dan een kleine letter s. Als we "Dit is CS50" met hoofdletters, dan is de kleine letter s zou slechts twee keer verschijnen, zou een knooppunt met 2 als waarde en hoofdletters S slechts eenmaal worden. Dus dan is uw boom zou veranderen structuren, omdat je eigenlijk een extra blaadje hier. Maar de som zou nog steeds 10. Dat is wat we eigenlijk gaan worden aanroepen van de checksum, de toevoeging van alle tellingen. 

Nu we Huffman bomen bedekt, kunnen we een duik nemen in Huff'n Puff, de PSET. We gaan beginnen met een deel van de vragen, en dit gaat om je vertrouwd met binaire bomen en de bediening rond die: tekenen knooppunten, het creëren van uw eigen typedef struct voor een knooppunt, en te zien hoe u in te voegen in een binaire boom, een die gesorteerd, doorkruisen, en dat soort dingen. Die kennis is zeker gaan om u te helpen wanneer u een duik in de Huff'n Puff gedeelte de PSET. In de standaard editie van de PSET, uw taak is het implementeren van Puff, en in de hacker-versie uw taak is het implementeren van Huff. Wat Huff doet is het duurt tekst en dan vertaalt deze in de 0s en 1s, zodat het proces dat we hierboven hebben waar we telden de frequenties en maakte vervolgens de boom en zei toen: "Hoe krijg ik T? ' T wordt vertegenwoordigd door 100, dat soort dingen, en dan Huff zou de tekst en dan output die binair. Maar ook omdat we weten dat we willen onze ontvanger van het bericht kan om te recreëren exact dezelfde boom, maar bevat ook informatie over de frequentie telt. Dan met Puff krijgen we een binair bestand van 0s en 1s en ook gezien de informatie over de frequenties. Wij vertalen al die 0s en 1s terug in het oorspronkelijke bericht dat was, dus we decomprimeren dat. Als je doet de standaard editie, hoeft u niet te Huff implementeren, dus dan kun je gewoon gebruik maken van de medewerkers uitvoering van Huff. Er zijn aanwijzingen in de spec over hoe dat te doen. U kunt de medewerkers uitvoering van Huff op een bepaald tekstbestand en gebruik die uitgang als uw opmerkingen toe aan Puff. 

Zoals ik al eerder vermeld, hebben we veel van de distributie-code voor deze. Ik ga om te beginnen gaan doorheen. Ik ga het grootste deel van de tijd doorbrengen op de. H-bestanden omdat in de. c bestanden, want we hebben het. h en dat geeft ons de prototypes van de functies, we niet volledig nodig om precies te begrijpen - Als je niet begrijpt wat er gaande is in de. C bestanden, kies dan niet te veel zorgen, maar zeker proberen om een ​​kijkje te nemen, want het zou kunnen geven enkele hints en het is handig om te wennen aan het lezen van andere mensen de code. 

Kijkend naar huffile.h, in de opmerkingen die zij verklaart een laag van abstractie voor Huffman-gecodeerde bestanden. Als we naar beneden gaan, dan zien we dat er een maximum van 256 symbolen die we misschien codes voor nodig hebt. Dit omvat alle letters van het alfabet - hoofdletters en kleine letters - en symbolen en nummers, etc. Dan hebben we hier een magisch nummer ter identificatie van een Huffman-gecodeerde bestand. Binnen een Huffman code ze gaan om een ​​bepaald magisch getal hebben verband met de header. Dit kan eruit zien als een willekeurig magisch getal, maar als je echt te vertalen naar ASCII, dan is het spreuken eigenlijk uit HUFF. Hier hebben we een struct voor een Huffman-gecodeerd bestand. Er is al deze kenmerken die geassocieerd worden met een Huff bestand. Dan hier beneden hebben we de header voor een Huff bestand, dus we noemen het Huffeader in plaats van het toevoegen van de extra h want het klinkt toch hetzelfde. Cute. We hebben een magisch nummer gekoppeld. Als het een echte Huff bestand, het gaat om het aantal te boven, deze magische een. En dan zal een array. Dus voor elk symbool, waarvan er 256, het gaat naar wat de frequentie van die symbolen zijn in het Huff bestand. En dan tot slot hebben we een checksum voor de frequenties, die moet de som van de frequenties. Dus dat is wat een Huffeader is. Dan hebben we een aantal functies die de volgende bit terug te keren in de Huff-bestand alsmede schrijft een beetje aan het Huff bestand en deze functie hier,, hfclose die sluit eigenlijk de Huff-bestand. Voorheen werden we te maken met rechte net fclose, maar als je een Huff bestand hebben, in plaats van fclosing het wat je eigenlijk gaan doen, is hfclose en hfopen het. Dat zijn specifieke functies om de Huff bestanden die we gaan te maken hebben. Dan hier lezen we in de header en schrijf dan de header. 

Gewoon door het lezen van de. H-bestand kunnen we soort van een gevoel van wat een Huff bestand zou kunnen zijn, Welke kenmerken heeft het, zonder daadwerkelijk te gaan op de huffile.c, die, als we duiken in, gaat een beetje complexer. Het heeft alle van het bestand I / O hier te maken met pointers. Hier zien we dat wanneer we hfread noemen, bijvoorbeeld, is het nog te maken heeft fread. We zijn niet het wegwerken van deze functies volledig, maar we sturen de te nemen maatregelen zorgen in het Huff bestand in plaats van het doen van al het zelf. U kunt gerust te scannen door middel van deze als je nieuwsgierig bent en gaan en schil de laag terug een beetje. 

Het volgende bestand dat we gaan kijken is tree.h. Voordat in de Walkthrough schuift we zeiden verwachten wij een Huffman knooppunt en we maakten een typedef struct node. We verwachten dat het een symbool, een frequentie, en dan 2 knooppunt sterren hebben. In dit geval wat we doen is dit is in wezen hetzelfde behalve in plaats van knooppunt gaan we noemen ze bomen. We hebben de functie dat wanneer u belt maakt boom geeft hij je een boom pointer. Terug naar Speller, toen je een nieuw knooppunt te maken je zei dat knooppunt * nieuw woord = malloc (sizeof) en dat soort dingen. In principe is mktree zal te maken hebben met dat voor u. Ook wanneer u een boom te verwijderen, dus dat is in wezen het bevrijden van de boom als je klaar bent met het, in plaats van expliciet te bellen gratis op dat, je bent eigenlijk alleen maar gaat om de functie te gebruiken rmtree waar u doorgeeft in de pointer naar die boom en dan ontbrekend zal zorgen dat voor u. 

We kijken naar tree.c. We verwachten dat dezelfde functies, behalve om de uitvoering, maar ook zien. Zoals we verwacht hadden, als je mktree noemen mallocs de grootte van een boom in een pointer, initialiseert alle waarden van de NULL waarde, zodat 0s of nullen, en keert dan terug de pointer naar die boom die je net hebt malloc'd voor jou. Hier als u belt verwijderen boom het maakt eerste zeker van dat je niet dubbel te bevrijden. Het zorgt ervoor dat je eigenlijk een boom die u wilt verwijderen te hebben. Is, omdat de boom ook de kinderen Wat dit doet is het noemt recursief te verwijderen boom aan de linkerkant knooppunt van de boom en rechts node. Voordat het bevrijdt de ouder, die het nodig heeft om de kinderen vrij te maken ook. Parent is ook uitwisselbaar met wortel. De allereerste ouder, dus net als de over-over-over-over-grootvader of grootmoeder boom, eerst moeten we bevrijden beneden de niveaus eerste. Dus doorkruisen naar de bodem, vrij die, en dan weer terug komen, gratis die, enz. Dus dat is boom. 

Nu kijken we naar het bos. Bos plaatst u al uw Huffman bomen. Het is te zeggen dat we gaan iets hebben genoemd een perceel dat bevat een pointer naar een boom en een pointer naar een plot genaamd volgende. Welke structuur doet dit soort eruit? Het soort van zegt dat het daar. Deze kant op. Een gelinkte lijst. We zien dat als we een perceel hebben het is als een gelinkte lijst van percelen. Een bos wordt gedefinieerd als een gelinkte lijst van percelen, en dus de structuur van het bos is dat we gaan gewoon met een pointer moeten onze eerste perceel en dat perceel heeft een boom in zich of liever wijst op een boom en wijst naar de volgende plot, enzovoort, enzovoort. Om een ​​bos te maken noemen we mkforest. Dan hebben we een aantal mooie handige functies hier. We hebben halen waar je langs in een bos en dan de return waarde is een boom *, een pointer naar een boom. Wat pick zal doen, is het zal gaan in het bos dat je te wijzen op verwijder vervolgens een boom met de laagste frequentie van dat bos en geven u de aanwijzer naar die boom. Zodra u belt plukken, zal de boom niet meer bestaat in het bos, maar de return waarde is de aanwijzer naar die boom. Dan heb je plant. Op voorwaarde dat u doorgeeft in een pointer naar een boom die een niet-0 frequentie heeft, welke plant zal doen, is het zal het bos te nemen, neem de boom en plant die boom in het bos. Hier hebben we rmforest. Net als boom, die in feite al onze bomen vrijgemaakt voor ons te verwijderen, Verwijder bos zal gratis alles in dat bos. 

Als we kijken naar forest.c, dan verwachten we minstens 1 rmtree commando zie daar, want om geheugen vrij te in het bos als een bos heeft bomen in het, dan uiteindelijk je gaat te hebben om te verwijderen die bomen. Als we kijken naar forest.c, hebben we onze mkforest, dat is zoals we verwachten. We malloc dingen. We initialiseren het eerste perceel in het bos als NULL omdat het leeg om te beginnen, dan zien we pick, dat de boom terug met het laagste gewicht, de laagste frequentie, en dan krijgt ontdoen van die bepaalde node die verwijst naar die boom en de volgende, dus het duurt dat van de gekoppelde lijst van het bos. En dan hebben we hier plant, die voegt een boom in de gekoppelde lijst. Wat bos doet is het mooi houdt het gesorteerd voor ons. En tenslotte hebben we rmforest en zoals verwacht hebben we rmtree daar genoemd. 

Als we kijken naar de verdeling code tot nu toe, huffile.c was waarschijnlijk veruit de moeilijkste om te begrijpen, terwijl de andere bestanden zelf waren vrij eenvoudig te volgen. Met onze kennis van pointers en gelinkte lijsten en dergelijke, konden we vrij goed te volgen. Maar alles wat we nodig om echt ervoor te zorgen dat we volledig begrijpen is het. H-bestanden want je moet worden bellen die functies, het omgaan met deze terugkeer waarden, dus zorg ervoor dat u volledig begrijpt welke actie zal worden uitgevoerd wanneer je een van die functies aan te roepen. Maar eigenlijk begrijpen binnenkant van het is niet helemaal nodig omdat wij die hebben. H-bestanden. We hebben 2 meer bestanden links in onze distributie-code. 

Laten we eens kijken naar dump. Hier dumpen door haar reactie neemt een Huffman-gecomprimeerd bestand en dan vertaalt en dumpt al zijn inhoud uit. Hier zien we dat het is hfopen belt. Dit is een beetje spiegelen aan * input file = fopen, en dan passeert u in de informatie. Het is bijna identiek, behalve in plaats van een bestand * je voorbij in een Huffile; in plaats van fopen je voorbij in hfopen. Hier lezen we in de header eerste, dat is een beetje vergelijkbaar met de manier waarop we lezen in de header voor een bitmap-bestand. Wat we hier doen is het controleren om te zien of de header informatie bevat de juiste magische getal dat aangeeft dat het een echte Huff bestand, dan al deze controles om ervoor te zorgen dat het bestand dat we geopend is een echte hufde bestand of niet. Wat dit doet is voordat het de frequenties van alle symbolen die we kunnen zien bij een terminal in een grafische tabel. Dit deel zal nuttig zijn. Het heeft een beetje en leest beetje bij beetje in de variabele beetje en dan drukt het uit. Dus als ik dump een beroep doen op hth.bin, die het gevolg is van hijgend een bestand met behulp van het personeel oplossing, zou ik dit. Het is het uitvoeren van al deze personages en dan zetten de frequentie waarin ze voorkomen. Kijken we meeste zijn 0s behalve voor: H, die tweemaal verschijnt en dan T, die ooit verschijnt. En dan hebben we hier de werkelijke boodschap in 0s en 1s. Als we kijken naar hth.txt, dat is vermoedelijk het oorspronkelijke bericht dat werd hufde, verwachten we een aantal Hs en Ts zien daar. In het bijzonder, verwachten we slechts 1 T en 2 Hs zien. Hier zijn we in hth.txt. Het heeft inderdaad HTH. Inbegrepen in daar, hoewel we niet kunnen zien, is een nieuwe regel karakter. De Huff bestand hth.bin is ook dat codeert voor het newline karakter. Hier omdat we weten dat de bestelling is HTH en dan newline, kunnen we dat waarschijnlijk de H wordt vertegenwoordigd zien door slechts een enkele 1 en de T waarschijnlijk 01 en de volgende H is 1 en en dan hebben we een nieuwe regel aangegeven met twee 0s. Cool. 

En dan tot slot, omdat we te maken hebben met meerdere. C en. H-bestanden, we gaan een mooi complex argument moet de compiler, en dus hier hebben we een Makefile die dump voor je maakt. Maar eigenlijk, je moet gaan over het maken van uw eigen puff.c bestand. De Makefile doet eigenlijk niet bezig met het maken van puff.c voor u. We vertrekken dat het aan jou om de Makefile bewerken. Wanneer u een opdracht als make alle betreden, bijvoorbeeld, zal het allemaal voor u. Voel je vrij om bij de voorbeelden van Makefile kijken uit het verleden PSET alsmede gaan uit van deze om te zien hoe je zou kunnen uw Puff bestand maken door het bewerken van deze Makefile. Dat is het zowat voor onze distributie-code. 

Zodra we hebben gekregen door dat, dan is hier gewoon een herinnering van hoe we te maken te hebben met de Huffman knooppunten. We gaan niet te bellen ze knopen meer, we gaan te bellen ze bomen waar we naartoe gaan worden die hun symbool met een char, de frequentie, het aantal gebeurtenissen, een integer. We gebruiken dat omdat het nauwkeuriger dan een vlotter. En dan nog een pointer naar links kind als het rechter kind. Een woud, zoals we zagen, is slechts een gelinkte lijst van bomen. Uiteindelijk, als we de opbouw van onze Huff-bestand, we willen dat onze bossen naar slechts 1 boom bevatten - 1 boom, 1 wortel met meerdere kinderen. Eerder toen we alleen het maken van onze Huffman bomen, We zijn begonnen met het plaatsen van alle knooppunten op ons scherm en zeggen we gaan deze knooppunten hebben, uiteindelijk ze gaan zijn de bladeren, en dit is hun symbool, dit is hun frequentie. In onze bossen als we alleen maar 3 letters, dat is een bos van 3 bomen. En dan als we verder gaan, als we de eerste ouder toegevoegd, hebben we een bos van 2 bomen. Wij verwijderd 2 van die kinderen van onze bossen en daarna vervangen door een parent node dat had die 2 knopen als kinderen. En dan tot slot, onze laatste stap bij het maken van ons voorbeeld met de As, B, en C's zou de uiteindelijke bovenliggende maken, en zo dan zou dat brengen onze totale telling van de bomen in het bos op 1. Heeft iedereen zien hoe je begint met meerdere bomen in je bos en eindigen met 1? Oke. Cool. 

Wat hebben we nodig om te doen voor Puff? Wat we moeten doen is ervoor te zorgen dat, zoals altijd, zij geven ons het juiste type van de input zodat we daadwerkelijk kunnen uitvoeren van het programma. In dit geval gaan ze te geven van ons na hun eerste opdrachtregelargument 2 meer: ​​het bestand dat we willen decomprimeren en de uitgang van de gedecomprimeerde bestand. Maar zodra wij zorgen ervoor dat ze ons pas in de juiste hoeveelheid waarden, We willen ervoor zorgen dat de invoer een Huff bestand of niet. En dan als we garanderen dat het een Huff bestand, dan willen we onze boom te bouwen, de opbouw van de boom zodanig dat zij de boom die de persoon die het bericht heeft gestuurd gebouwd past. Dan na bouwen we de boom, dan kunnen we omgaan met de 0s en 1s dat ze voorbij in, volgen die langs onze boom, want het is identiek, en schrijf dan die boodschap uit, terug de interpretatie van de bits in tekens. En dan aan het einde, omdat we te maken hebben met pointers hier, willen we ervoor zorgen dat we geen geheugenlekken hebben en dat we gratis alles. 

Zorgen voor het juiste gebruik is oude koek voor ons nu. We nemen in een input, die gaat naar de naam van het bestand te blazen zijn, en dan specificeren we een uitgang, zodat de naam van het bestand voor het gepofte output, die de tekstbestanden. Dat is gebruik. En nu willen we ervoor zorgen dat de ingang snoof of niet. Terugdenkend, was er iets in de verdeelsleutel die ons kunnen helpen met het begrijpen van de vraag of er een bestand is hufde of niet? Er was informatie in huffile.c over de Huffeader. We weten dat elke Huff bestand een Huffeader verbonden aan een magisch getal is alsmede een reeks van frequenties voor elk symbool en een checksum. We weten dat, maar we namen ook een kijkje op dump.c, waarin het aan het lezen was in een Huff bestand. En dus om dat te doen, moest om te controleren of het echt was snoof of niet. Dus misschien kunnen we dump.c als een structuur te gebruiken voor onze puff.c. Terug naar PSET 4 wanneer we het bestand copy.c die gekopieerd in RGB triples hadden en we uitgelegd dat voor Whodunit en Resize, evenzo is wat je zou kunnen doen gewoon de commando als cp dump.c puff.c en gebruik een aantal van de code daar. Echter, het is niet van plan om zo eenvoudig van een proces voor het vertalen van uw dump.c in puff.c, maar in ieder geval het geeft je ergens beginnen om hoe dat de ingang daadwerkelijk hufde of niet evenals een paar andere dingen. Wij hebben ervoor gezorgd juiste gebruik en ervoor gezorgd dat de ingang wordt hufde. Elke keer dat we hebben gedaan dat we onze goede foutcontrole gedaan, zo terug te keren en het verlaten van de functie als sommige optreedt, wanneer er een probleem is. 

Wat we nu willen doen is bouwen van de eigenlijke boom. Als we kijken in Vorst, zijn er 2 belangrijke functies dat we gaan willen heel vertrouwd te raken met. Er is de Booleaanse functie plant die planten een niet-0-frequentie boom in ons bos. En zo zijn er passeert u in een pointer naar een bos en een pointer naar een boom. Snelle vraag: Hoeveel bossen zult u wanneer u het bouwen van een Huffman boom? Ons bos is als onze canvas, toch? Dus we alleen maar een bos, maar we gaan om meerdere bomen. Dus voordat je plant noemen, je waarschijnlijk gaat te willen om uw bos te maken. Er is een commando voor dat als je kijkt naar forest.h over hoe je kunt een bos te maken. U kunt de plant een boom. We weten hoe dat te doen. En dan kun je ook kiezen een boom uit het bos, het verwijderen van een boom met het laagste gewicht en geven u de aanwijzer naar dat. Terugdenkend aan toen we aan het doen waren de voorbeelden zelf, toen we het tekenen, we simpelweg toegevoegd de links. Maar hier in plaats van alleen het toevoegen van de links, denk aan het meer als je 2 van die knooppunten te verwijderen en daarna te vervangen door een andere. Om dat uit te drukken in termen van het plukken en planten, je plukken 2 bomen en planten een andere boom dat heeft die 2 bomen dat u heeft geselecteerd als kinderen. Om Huffman's boom op te bouwen, kunt u lezen in de symbolen en frequenties op te omdat de Huffeader geeft dat aan u, geeft u een array van de frequenties. U kunt dus gaan en gewoon alles negeren met de 0 in het omdat we niet willen dat 256 blaadjes aan het eind van het. We willen alleen het aantal bladeren die tekens die werkelijk worden gebruikt in het bestand. Leest u in deze symbolen, en elk van deze symbolen niet-0 frequenties, deze zullen worden bomen. Wat je kunt doen is elke keer dat je leest in een niet-0-frequentie symbool, U kunt de plant die boom in het bos. Zodra u de bomen te planten in het bos, kunt u deelnemen aan die bomen als broers en zussen, dus terug te gaan naar het planten en plukken waar je plukken 2 en vervolgens plant 1, waar dat 1 die u plant is de ouder van de 2 kinderen dat u heeft geselecteerd. Dus dan is uw eindresultaat gaat om een ​​enkele boom in uw bos. Zo bouw je je boom. 

Er zijn verschillende dingen die hier mis kan gaan omdat we te maken hebben met het maken van nieuwe bomen en het omgaan met pointers en dat soort dingen. Toen we te maken hadden met pointers, wanneer we malloc'd we wilden er zeker van dat het niet terug ons een NULL pointer waarde. Dus op een aantal stappen in dit proces zijn er gaan worden een aantal gevallen waar uw programma zou kunnen mislukken. Wat u wilt doen is wilt u ervoor zorgen dat u deze fouten af ​​te handelen, en in de spec staat om gracieus mee om te gaan, zo graag afdrukken van een bericht aan de gebruiker hen te vertellen waarom het programma te stoppen en begeef u direct stoppen met het. Om dit te foutafhandeling doen, bedenk dan dat je wilt om het te controleren elke keer dat er een mislukking. Elke keer dat je een nieuwe pointer maken wilt u ervoor zorgen dat dat succesvol is. Voor wat we vroeger doen is een nieuwe aanwijzer en malloc te maken, en dan zouden we kijken of dat pointer NULL is. Dus er zullen zijn sommige gevallen waar je kunt gewoon doen, maar soms moet je je eigenlijk het aanroepen van een functie en binnen die functie, dat is degene die doet het mallocing. In dat geval, als we kijken naar een aantal functies in de code, sommige van hen zijn Booleaanse functies. In de abstracte geval als we een Booleaanse functie genaamd foo, in principe, kunnen we aannemen dat in aanvulling op doen wat foo doet, want het is een Booleaanse functie, het geeft true of false - waar indien succesvol, false als niet. Dus we willen controleren of de return waarde van foo waar of onwaar is. Als het valse, dat betekent dat we gaan willen een soort boodschap af te drukken en sluit het programma. Wat wij willen doen is controleren de return waarde van foo. Als foo false retourneren, dan weten we dat we een soort van fout is opgetreden en we moeten ons programma af te sluiten. Een manier om dit te doen is een aandoening waarbij de eigenlijke functie zelf is uw conditie. Zeg foo neemt in x. We kunnen als voorwaarde if (foo (x)). In principe, dat betekent dat als aan het einde van het uitvoeren van foo het true retourneert, dan kunnen we dit doen omdat de functie te evalueren foo om de gehele toestand te evalueren. Zo dan dat is hoe je iets kunt doen als de functie true teruggeeft en is succesvol. Maar als je foutcontrole, u alleen wilt stoppen als uw functie false retourneert. Wat je zou kunnen doen is gewoon voeg een == false of voeg gewoon een knal in de voorkant van het en dan heb je if (! foo). Binnen dat lichaam van die voorwaarde zou je alle foutafhandeling, zo graag, "Kan deze boom te creëren" en dan terug 1 of iets dergelijks. Wat dat doet, is echter dat, hoewel foo vals terug - Zeg foo true retourneert. Dan hoeft u niet opnieuw te bellen foo. Dat is een veel voorkomende misvatting. Omdat het in uw toestand, het is al geëvalueerd, zodat u al het resultaat als je het gebruik van make boom of iets dergelijks of plant of pick of zoiets. Het heeft al die waarde. Het is al uitgevoerd. Dus het is handig om Booleaanse functies te gebruiken als de conditie want of u daadwerkelijk uitvoeren van de body van de lus, het voert de functie toch. 

Onze voorlaatste stap is het schrijven van het bericht naar het bestand. Zodra we bouwen de Huffman boom, dan het schrijven van het bericht naar het bestand is vrij eenvoudig. Het is vrij eenvoudig nu volg gewoon de 0s en 1s. En dus volgens afspraak weten we dat in een Huffman boom de 0s wijzen links en 1s dan rechts. Dus dan kun je het lezen in beetje bij beetje, elke keer dat u een 0 krijgt volg je de linker tak, en dan elke keer dat u leest in een 1 je gaat naar de juiste vestiging te volgen. En dan ga je verder tot je een blad omdat de bladeren gaan aan het einde van de takken. Hoe kunnen we zeggen of we slaan een blad of niet? We zeiden het al eerder. [Student] Als de wijzers NULL zijn. >> Ja. We kunnen zien of we slaan een blad als de verwijzingen naar zowel links en rechts bomen zijn NULL. Perfect. We weten dat we willen in wat te lezen bij beetje in onze Huff bestand. Zoals we eerder zagen in dump.c, wat zij deden is dat ze in bit gelezen door boor in het Huff bestand en gewoon uitgeprint wat die stukjes waren. We gaan niet te doen. We gaan iets doen dat is een beetje complexer. Maar wat we kunnen doen is kunnen we dat stukje code die leest in de bit. Hier hebben we de integer bit die de huidige bit dat we op. Dit zorgt itereren alle bits in het bestand tot je het einde van het bestand. Op basis van dat, dan zul je wilt een soort van iterator hebben om uw boom te steken. En afhankelijk van of de bit 0 of 1 is, je gaat te willen dat iterator ofwel naar links of naar rechts te verplaatsen helemaal tot je een blad, zodat de hele weg tot dat knooppunt dat je op niet wijzen op enig meer knooppunten. Waarom kunnen we dit doen met een Huffman-bestand, maar niet Morse code? Omdat in morse is er een beetje van dubbelzinnigheid. We kunnen zijn als, oh wacht, we hebben een brief langs de weg raken, dus misschien is dit onze brief, terwijl als we verder gewoon een beetje langer, dan zouden we hebben geraakt een andere brief. Maar dat gaat niet gebeuren in Huffman codering, dus we kunnen er zeker van zijn dat de enige manier dat we gaan om een ​​teken te raken is als dat knooppunt links en rechts kinderen zijn NULL. 

Tot slot willen we alle van ons geheugen vrij te maken. We willen beide in de buurt van de Huff bestand dat we hebben te maken met alsmede verwijder alle van de bomen in onze bossen. Op basis van uw implementatie, ben je waarschijnlijk gaat te willen bellen bos te verwijderen in plaats van het daadwerkelijk gaan door alle bomen zelf. Maar als je geen tijdelijke bomen, wil je bevrijden dat. U kent uw code beste, zodat je weet waar je het toewijzen van geheugen. En dus als je in, begin met zelfs Controle F'ing voor malloc, zien wanneer u malloc en ervoor te zorgen dat je dat allemaal vrij maar dan gewoon door uw code, begrijpen waar u zou kunnen hebben toegewezen geheugen. Meestal kun je net zeggen: "Aan het einde van een bestand Ik ga naar het bos te verwijderen op mijn bos," dus in principe duidelijk dat geheugen, vrij dat, "En dan ga ik ook naar het bestand te sluiten en mijn programma gaat om te stoppen." Maar is dat de enige keer dat het programma wordt afgesloten? Nee, want soms zijn er misschien wel een fout is gebeurd. Misschien kunnen we een bestand niet openen of we konden geen andere boom of een soort van fout is opgetreden in het geheugen toewijzing en dus het terug NULL. Er is een fout gebeurd en dan zijn we terug en stoppen. Dus dan wilt u ervoor zorgen dat eventuele tijd die uw programma kunnen stoppen, je wilt er bevrijden van al uw geheugen. Het is niet alleen zal zijn aan het einde van de belangrijkste functie die u uw code af te sluiten. Wil je terug kijken naar elke instantie dat uw code mogelijk voortijdig zou terugkeren en dan vrij wat geheugen zinvol. Stel dat je had gebeld om bos en dat geretourneerd valse. Dan zal je waarschijnlijk niet nodig hebt om uw bos te verwijderen omdat u nog niet over een bos. Maar op elk punt in de code waar u misschien voortijdig terug te keren wilt u ervoor zorgen dat u eventuele geheugen vrij te maken. 

Dus als we te maken hebben met het vrijmaken van geheugen en het hebben van mogelijke lekken, we willen niet alleen gebruik maken van ons oordeel en onze logica maar ook gebruik maken van Valgrind om te bepalen of we hebben allemaal van ons geheugen vrijgemaakt behoorlijk of niet. U kunt lopen Valgrind op Puff en dan moet je ook doorgeven het juiste aantal command-line argumenten Valgrind. U kunt dat, maar de output is een beetje cryptisch. We hebben gekregen een beetje aan gewend met Speller, maar we moeten nog steeds een beetje meer hulp, dus dan loopt het met een paar vlaggen, zoals de lek-check = vol, die waarschijnlijk zal ons wat meer nuttige output op Valgrind. 

Dan nog een handige tip als je debuggen is het diff commando. U kunt de medewerkers uitvoering van Huff, lopen dat op een tekstbestand, en dan uitvoeren naar een binair bestand, een binair bestand Huff, om precies te zijn. Dan als je je eigen bladerdeeg op die binair bestand, dan ideaal, wordt uw uitgestuurde tekstbestand zal identiek zijn naar de oorspronkelijke degene die je voorbij inch Hier ben ik met behulp van hth.txt als voorbeeld, en dat is degene over gesproken in uw spec. Dat is letterlijk HTH en dan een nieuwe regel. Maar zeker voel je vrij en bent u zeker aangemoedigd om langer voorbeelden te gebruiken voor uw tekst bestand. 

U kunt zelfs een schot op misschien het comprimeren en decomprimeren dan een aantal van de bestanden die u gebruikt in Speller, zoals Oorlog en Vrede of Jane Austen of zoiets - dat zou wel cool zijn - of Austin Powers, soort van omgaan met grotere bestanden, omdat we niet naar beneden komen om het Als we de volgende gereedschap hier, ls-l. We zijn gewend aan ls, die in feite alle inhoud geeft in onze huidige directory. Het passeren van de vlag-l eigenlijk wordt de grootte van deze bestanden. Als je door de PSET spec, het loopt eigenlijk u bij het maken van de binaire bestand, van hijgend, en zie je dat voor zeer kleine bestanden de ruimte kosten comprimeren en vertalen al die informatie van alle frequenties en dat soort dingen opweegt tegen het werkelijke voordeel comprimeren van het bestand in de eerste plaats. Maar als je het op een aantal langere tekstbestanden, dan kun je misschien zien dat je begint om wat voordeel te krijgen comprimeren in deze bestanden. 

En dan tot slot, hebben we onze oude vriend GDB, die zeker zal te pas komen. 

Hebben we misschien nog vragen over Huff bomen of het proces van het maken van de bomen of andere vragen over Huff'n Puff? Oke. Ik zal rond blijven voor een beetje. 

Bedankt, iedereen. Dit was Walkthrough 6. En veel geluk. 

[CS50.TV]