[Powered by Google Translate] [Walkthrough - Problem Set 6] [Zamyla Chan - Harvard University] [Dette er CS50. - CS50.TV] 

Hej, alle sammen, og velkommen til Walkthrough 6: Huff'n Puff. I Huff'n Puff hvad vi gør vil være at gøre med en Huffman komprimeret fil og derefter puster den op igen, så dekomprimering det, så vi kan oversætte fra den 0'er og 1-taller, at brugeren sender os og konvertere den tilbage til den oprindelige tekst. Pset 6 vil være temmelig cool, fordi du kommer til at se nogle af de værktøjer som du brugte i Pset 4 og Pset 5 og art kombinere dem i 1 temmelig pæn koncept når du kommer til at tænke over det. 

Også, velsagtens var Pset 4 og 5 de mest udfordrende psets som vi måtte tilbyde. Så fra nu, har vi denne 1 mere Pset i C, og derefter efter at vi er på til webprogrammering. Så lykønske jer til at komme over den hårdeste hump i CS50. 

Bevæger sig på for Huff'n Puff, er vores værktøjskasse for denne Pset bliver Huffman træer, så forstå ikke kun hvordan binære træer arbejde, men også specifikt Huffman træer, hvordan de er opbygget. Og så vil vi have en masse fordeling kode i denne Pset, og vi vil komme til at se, at der faktisk noget af koden vi måske ikke være i stand til fuldt ud at forstå endnu, og så dem vil være de. C-filer, men så deres ledsagende. H-filer vil give os nok forståelse for, at vi har brug for, så vi ved, hvordan disse funktioner virker eller i det mindste, hvad de skal gøre - deres input og output - selv om vi ikke ved, hvad der sker i den sorte boks eller ikke forstår, hvad der sker i den sorte boks indeni. Og så til sidst, som sædvanligt, har vi at gøre med nye datastrukturer, specifikke typer af knuder, der peger på visse ting, og så her har en pen og papir, ikke kun for designprocessen og når du forsøger at finde ud af hvordan din Pset skal arbejde men også under debugging. Du kan have GDB sammen med din pen og papir, mens du tager ned, hvad værdierne er, hvor dine pile peger, og sådan noget. 

Først lad os se på Huffman træer. Huffman træer er binære træer, hvilket betyder, at hvert knudepunkt kun har 2 børn. I Huffman træer den karakteristiske er, at de hyppigst forekommende værdier er repræsenteret ved de færreste bits. Vi så i forelæsning eksempler på morsekode, hvilken form for konsolideret nogle breve. Hvis du forsøger at oversætte en A eller en E, for eksempel, du oversætte det ofte, så i stedet for at skulle bruge det fulde sæt af bits tildeles for den pågældende sædvanlig datatype, du komprimere det ned til færre, og derefter disse skrivelser, der er repræsenteret sjældnere er repræsenteret med længere bits fordi du har råd til, at når du vejer de frekvenser, som disse bogstaver vises. Vi har den samme idé her i Huffman træer hvor vi gør en kæde, en slags sti for at komme til de bestemte tegn. Og så de tegn, der har mest frekvens vil være repræsenteret med færrest bits. 

Den måde, du konstruere en Huffman træ er ved at placere alle de tegn, der vises i teksten og beregne deres hyppighed, hvor ofte de forekommer. Dette kan enten være en optælling af, hvor mange gange disse bogstaver, vises eller måske en procentdel af ud af alle de tegn, hvor mange hver enkelt vises. Og så hvad du skal gøre er, når du har alt det kortlagt, så du kigge efter de 2 laveste frekvenser, og derefter slutte sig til dem som søskende hvor derefter den forælder node har en frekvens, der er summen af ​​sine 2 børn. Og så skal du ved konvention siger, at den venstre knude, du følger, at ved at følge 0 gren, og derefter længst til højre knudepunkt er en gren. Som vi så i morsekode, var den gotcha at hvis du havde bare et bip, og bip det var tvetydig. Det kunne enten være 1 bogstav eller det kunne være en sekvens af to bogstaver. Og hvad så Huffman træer gør, er på grund af arten af ​​de tegn eller vores endelige faktiske tegn er de sidste noder på gren - vi henvise til dem som blade - i kraft af, at der ikke kan være nogen tvetydighed i form af hvilket bogstav du forsøger at indkode med den række af bits fordi intetsteds langs de bits, der repræsenterer 1 bogstav vil du støde på en anden hele brev, og der vil ikke være nogen forvirring der. Men vi vil gå ind i eksempler på, at du fyre rent faktisk kan se, at i stedet for os bare at fortælle dig, at det er sandt. 

Lad os se på et simpelt eksempel på en Huffman træ. Jeg har en streng her, er 12 tegn lang. Jeg har 4 Som, 6 Bs, og 2 Cs. Mit første skridt ville være at tælle. Hvor mange gange har A vises? Det ser 4 gange i strengen. B viser 6 gange, og C vises to gange. Naturligvis vil jeg sige Jeg bruger B oftest, så jeg ønsker at repræsentere B med færrest antal bits, det færrest antal 0'er og 1'ere. Og så er jeg også kommer til at forvente, C for at kræve de mest mængden af ​​0'er og 1-taller så godt. Først hvad jeg gjorde her er jeg placeret dem i stigende rækkefølge med hensyn til hyppighed. Vi ser, at C og A, det er vores 2 laveste frekvenser. Vi skaber en forælder node, og at denne forælder node ikke har et brev forbundet med det, men det har en frekvens, som er summen. Summen bliver 2 + 4, der er 6. Derefter følger vi den venstre gren. Hvis vi var på at 6 node, så vi ville følge 0 for at komme til C og derefter 1 for at komme til A. Så nu har vi 2 noder. Vi har værdien 6 og derefter har vi også en anden node med værdien 6. Og så dem 2 er ikke kun de 2 laveste men også bare de 2 der er tilbage, så vi slutte sig til dem af en anden forælder, med det beløb bliver 12. Så her har vi vores Huffman træ hvor man kommer til B, ville det bare være den bit 1 og derefter at komme til A ville vi have 01 og derefter C med 00. Så her kan vi se, at stort set vi repræsenterer disse chars med enten 1 eller 2 bits hvor B, som forudsagt, har den mindste. Og så vi havde forventet C for at få mest, men da det er sådan en lille Huffman træ, derefter A er også repræsenteret ved 2 bit i modsætning til et sted i midten. 

Blot at gå over en anden simpelt eksempel på Huffman træet, sige, at du har strengen "Hello". Hvad du skal gøre er først du ville sige, hvor mange gange har H vises i denne? H vises én gang og derefter e vises én gang og så har vi l optræder to gange og o vises én gang. Og så så vi forventer som brev, der skal repræsenteres af mindst antallet af bits? [Studerende] l. >> L. Yeah. l er rigtigt. Vi forventer l at være repræsenteret ved den mindste antal bit fordi jeg bruges mest i strengen "Hello". Hvad jeg har tænkt mig at gøre nu, er trække ud disse knudepunkter. Jeg har 1, som er H, og derefter en anden 1, som er e, og derefter en 1, som er o - lige nu er jeg sætte dem i orden - og så 2, som er l. Så siger jeg den måde, at jeg bygge en Huffman træ er at finde de 2 noder med de mindst frekvenser og gøre dem søskende ved at oprette en forælder node. Her har vi 3 noder med den laveste frekvens. De er alle 1. Så her har vi vælge hvilken en vi vil linke først. Lad os sige, at jeg vælger H og e. Summen af ​​1 + 1 er 2, men dette knudepunkt har ikke et brev forbundet med det. Det bare holder værdien. Nu skal vi se på de næste 2 laveste frekvenser. Det er 2 og 1. Det kunne enten være af disse 2, men jeg har tænkt mig at vælge denne. Summen er 3. Og så til sidst, jeg har kun 2 tilbage, ja så der bliver 5. Så her, som forventet, hvis jeg udfylder kodning for det, 1s er altid den højre gren og 0'er er den venstre. Så har vi l repræsenteret ved kun 1 bit og derefter o med 2 og derefter e med 2 og derefter H falder ned på 3 bit. Så du kan sende denne besked "Hello" i stedet for rent faktisk at bruge de tegn ved bare 0'er og 1'ere. Men husk, at i flere tilfælde havde vi bånd med vores frekvens. Vi kunne enten have tilsluttet sig H og o Første måske. Eller så senere, når vi havde l repræsenteret ved 2 samt den sammenføjede on med 2, kunne vi have bundet enten en. 

Og så når du sender 0'er og 1-taller, der faktisk ikke garanterer at modtageren fuldt ud kan læse din besked ret off the bat fordi de ikke kunne vide, hvilken beslutning du har lavet. Så når vi har at gøre med Huffman komprimering, eller anden måde vi nødt til at fortælle modtageren af ​​vores budskab, hvordan vi besluttet - De har brug for at vide en slags ekstra information ud over den komprimerede meddelelsen. De har brug for at forstå, hvad træet faktisk ser ud, hvordan vi faktisk gjort disse beslutninger. 

Her blev vi bare gør eksempler baseret på det faktiske antal, men nogle gange kan du også have en Huffman træ baseret på den frekvens, hvor bogstaver forekommer, og det er nøjagtig samme proces. Her er jeg udtrykke det i form af procenter eller en fraktion, og så her præcis de samme ting. Jeg finder de 2 lavest, summerer dem, de næste 2 lavest, summerer dem, indtil jeg har en fuld træ. Selvom vi kunne gøre det begge veje, når vi har at gøre med procenter, der betyder, at vi deler ting og beskæftiger sig med decimaler eller snarere flyder hvis vi tænker på datastrukturer i et hoved. Hvad ved vi om flåd? Hvad er et almindeligt problem, når vi har at gøre med flåd? [Studerende] Upræcis aritmetik. >> Yeah. Unøjagtighed. På grund af floating point unøjagtighed, således at der for denne Pset vi sørge at vi ikke mister nogen værdier, så er vi faktisk kommer til at beskæftige sig med greven. Så hvis du skulle tænke på en Huffman node, hvis man ser tilbage til strukturen her, hvis man ser på de grønne har en frekvens forbundet med det såvel som den peger til et knudepunkt til venstre og et knudepunkt til sin ret. Og så de røde der også har en karakter forbundet med dem. Vi kommer ikke til at lave særskilte dem for forældrene og derefter de endelige knudepunkter, som vi refererer til som blade, men om dem vil bare have NULL-værdier. For hver knude vi vil have en karakter, det symbol, denne knude repræsenterer, derefter en frekvens samt en pointer til venstre barn samt dens højre barn. Bladene, der er i bunden, ville også have node pointers til deres venstre og til deres ret, men da disse værdier ikke pege på konkrete knudepunkter, hvad ville deres værdi være? >> [Studerende] NULL. >> NULL. Præcis. Her er et eksempel på, hvordan du kan repræsentere frekvensen i flåd, men vi vil beskæftige sig med det med heltal, så alt hvad jeg gjorde, er ændre datatypen der. 

Lad os gå videre til en lille smule mere af en kompleks eksempel. Men nu, hvor vi har gjort de mest simple, det er bare den samme proces. Du finder de 2 laveste frekvenser, opsummere de frekvenser og det er den nye frekvens af dine forældre node, som derefter peger til venstre med 0 gren og retten med en gren. Hvis vi har strengen "Dette er CS50," så vi tælle hvor mange gange der er T nævnt, h nævnte, i, s, c, 5, 0. Så hvad jeg gjorde her er med de røde knuder jeg lige plantet, Jeg sagde, at jeg har tænkt mig at have disse tegn til sidst i bunden af ​​mit træ. De, der vil være alle bladene. Så hvad jeg gjorde, er jeg sorterede dem efter frekvens i stigende rækkefølge, og det er faktisk den måde, at Pset kode gør det er den sorterer det efter frekvens og derefter alfabetisk. Så det har numrene først og derefter alfabetisk efter frekvensen. Så hvad jeg ville gøre, er jeg ville finde de 2 laveste. Det er 0 og 5. Jeg vil opsummere dem, og det er 2. Så jeg ville fortsætte, finde den næste 2 lavest. Det er de to 1s, og derefter dem bliver 2 så godt. Nu ved jeg, at mit næste skridt vil være at tilslutte sig det laveste antal, som er T, 1 og derefter at vælge en af ​​knudepunkter, der har 2 som frekvensen. Så her har vi 3 muligheder. Hvad jeg har tænkt mig at gøre for slæden er bare visuelt omarrangere dem for dig så du kan se, hvordan jeg bygger det op. Hvad koden og din distribution kode vil gøre ville være medlem af T en med 0 og 5 node. Så det beløb til 3 og derefter vi fortsætte processen. De 2 og 2 nu er den laveste, så så dem sum til 4. Alle efter indtil videre? Okay. Så efter at vi har 3 og 3, som skal lægges sammen, så igen er jeg bare skifte den, så du kan se visuelt, så det ikke bliver for rodet. Så har vi en 6, og derefter vores sidste skridt er nu, at vi kun har 2 knuder vi opsummere dem at gøre roden af ​​vores træ, som er 10. Og tallet 10 giver mening, fordi hver node er repræsenteret, deres værdi, deres hyppighed nummer, var, hvor mange gange de optrådte i strengen, og så har vi 5 tegn i vores streng, så det giver mening. Hvis vi kigger op på, hvordan vi rent faktisk ville indkode det, som forventet, i og s, som synes det oftest er repræsenteret ved det færreste antal bit. 

Vær forsigtig her. I Huffman træer sagen faktisk betyder noget. Et stort S er anderledes end en lille s. Hvis vi havde "Dette er CS50" med store bogstaver, så det lille s ville kun vises to gange, ville være en node med 2 som dens værdi, og så stort S ville kun være en gang. Så dit træ ville ændre strukturer, fordi du rent faktisk har en ekstra blad her. Men beløbet ville stadig være 10. Det er, hvad vi egentlig vil være at kalde checksum, tilsætning af alle tællinger. 

Nu da vi har dækket Huffman træer, kan vi dykke ned i Huff'n Puff, den Pset. Vi vil starte med en del spørgsmål, og dette vil få dig vant med binære træer og hvordan man betjener omkring at: tegning noder, oprette din egen typedef struct for en knude, og se, hvordan du kan indsætte i et binært træ, en, der er sorteret, tilbagelæggelse det, og sådan noget. Denne viden er helt sikkert vil hjælpe dig, når du dykker ned i den Huff'n Puff portion af Pset. I standardudgaven af ​​den Pset er det din opgave at implementere Puff, og i hacker-version, din opgave er at implementere Huff. Hvad Huff gør, er det tager tekst og så er det oversætter det til 0'er og 1'ere, så processen, at vi gjorde ovenfor, hvor vi talte frekvenser og derefter foretaget træet og sagde så: "Hvordan får jeg T?" T er repræsenteret med 100, sådan noget, og derefter Huff ville tage teksten og derefter output, som binær. Men også fordi vi ved, at vi ønsker at give vores modtageren af ​​beskeden at genskabe den nøjagtige samme træ, det indeholder også oplysninger om de frekvensbånd, der tæller. Så med Puff vi får en binær fil af 0'er og 1-taller og ligeledes i lyset af de oplysninger om de frekvenser. Vi oversætter alle dem 0'er og 1-taller tilbage i den oprindelige meddelelse, der var, så vi dekomprimere det. Hvis du laver den standard udgave, behøver du ikke at implementere Huff, så kan du bare bruge personale implementering af Huff. Der er instruktioner i spec om, hvordan man gør det. Du kan køre det personale implementering af Huff på en bestemt tekstfil og derefter bruge dette output som dit input til Puff. 

Som jeg nævnte før, vi har en masse af distribution kode for denne ene. Jeg har tænkt mig at begynde at gå igennem det. Jeg har tænkt mig at tilbringe det meste af tiden på. H-filer fordi de. C-filer, fordi vi har den. h og det giver os med prototyper af de funktioner, vi ikke helt nødvendigt at forstå præcis - Hvis du ikke forstår, hvad der foregår i de. C-filer, så skal du ikke bekymre dig for meget, men helt sikkert prøve at tage et kig, fordi det kan give nogle hints og det er nyttigt at vænne sig til at læse andre folks kode. 

Ser man på huffile.h, i de bemærkninger, den erklærer et lag af abstraktion for Huffman-kodede filer. Hvis vi går ned, kan vi se, at der er et maksimum på 256 symboler, som vi muligvis koder for. Dette omfatter alle bogstaverne i alfabetet - store og små - og derefter symboler og tal, osv. Så her har vi et magisk nummer, der identificerer en Huffman-kodet fil. Inden for en Huffman-kode, de kommer til at have en vis magisk tal forbundet med overskriften. Det kan se ud som blot et tilfældigt magisk tal, men hvis du rent faktisk oversætte det til ASCII, så er det faktisk præciserer Huff. Her har vi en struct for en Huffman-kodet fil. Der er alle disse egenskaber er forbundet med en Huff fil. Så hernede har vi header for en Huff fil, så kalder vi det Huffeader stedet for at tilføje det ekstra h fordi det lyder det samme alligevel. Cute. Vi har et magisk tal forbundet med det. Hvis det er et virkeligt Huff fil, går det at være nummer deroppe, dette magiske én. Og så vil det have en array. Så for hvert symbol, hvoraf der er 256, det kommer til at liste hvad hyppigheden af ​​disse symboler er inden for Huff fil. Og så til sidst har vi en checksum for de frekvenser, som bør være summen af ​​disse frekvenser. Så det er hvad en Huffeader er. Så har vi nogle funktioner, der returnerer den næste bit i Huff fil samt skriver lidt til Huff filen og derefter denne funktion her, hfclose der faktisk lukker Huff filen. Før var vi beskæftiger sig med lige netop fclose, men når du har en Huff fil, i stedet for fclosing det hvad du faktisk skal gøre, er hfclose og hfopen det. Det er specifikke funktioner til Huff filer, vi kommer til at beskæftige sig med. Så her kan vi læse i sidehovedet og derefter skrive overskriften. 

Bare ved at læse. H fil, vi kan slags få en fornemmelse af, hvad en Huff fil kan være, hvilke egenskaber det har, uden faktisk at gå ind i huffile.c, som, hvis vi dykke i, kommer til at være en smule mere kompliceret. Det har alle den fil I / O her beskæftiger sig med pegepinde. Her ser vi, at når vi kalder hfread, for eksempel, er det stadig beskæftiger sig med fread. Vi er ikke at komme af disse funktioner helt, men vi sender dem, der skal tages hånd om inde i Huff filen i stedet for at gøre det hele selv. Du kan føle dig fri til at scanne igennem dette, hvis du er nysgerrig og gå og skræl laget tilbage en lille smule. 

Den næste fil, vi vil se på, er tree.h. Før i Walkthrough glider vi sagde vi forventer en Huffman node og vi lavede en typedef struct node. Vi forventer, at det at have et symbol, en frekvens, og derefter 2 node stjerner. I dette tilfælde, hvad vi laver, er det er stort set den samme undtagen i stedet for node vi vil kalde dem træer. Vi har en funktion, når du kalder gøre træ den returnerer dig et træ pointer. Back to Speller, da du lavede en ny knude du sagde node * nyt ord = malloc (sizeof) og sådan noget. Dybest set, er mktree vil beskæftige sig med det for dig. Tilsvarende, når du ønsker at fjerne et træ, så det er væsentligt at frigøre træet, når du er færdig med det, i stedet for eksplicit at kalde fri på det, er du faktisk bare bruge funktionen rmtree hvor du passerer på markøren til det træ, og derefter tree.c vil tage sig af det for dig. 

Vi ser på tree.c. Vi forventer de samme funktioner, undtagen til at se såvel gennemførelsen. Som vi forventede, når du ringer mktree det mallocs på størrelse med et træ i en pegepind, initialiserer alle værdierne for nulværdi, så 0'er eller nuller, og derefter returnerer markøren til det træ, som du lige har malloc'd til dig. Her når du kalder fjerne træet først sørger for, at du ikke er dobbelt frigøre. Det sikrer, at du rent faktisk har et træ, som du vil fjerne. Her, fordi et træ også sine børn, hvad den gør, er det rekursivt kalder fjerne træet på venstre node af træet og højre node. Før det frigør den forælder, er det nødvendigt at befri børnene så godt. Forældre er også udskiftes med root. Den første nogensinde forælder, så ligesom den tip-tip-tip-oldefar eller bedstemor træ, vi først nødt til at befri ned niveauerne først. Så krydse til bunden, fri dem, og så komme op igen, fri dem, osv. Så det er træ. 

Nu ser vi på skov. Skov er, hvor du placerer alle dine Huffman træer. Det er at sige, at vi vil have noget, der hedder et plot som indeholder en pointer til et træ samt en pointer til et plot kaldet næste. Hvilken struktur gør denne form for se ud? Det slags siger det derovre. Lige herovre. En sammenkædet liste. Vi ser, at når vi har et plot det er ligesom en sammenkædet liste over parceller. En skov er defineret som en linket liste af grunde, og så strukturen af ​​skoven er vi bare skal have en pegepind til vores første plot og at grunden har et træ i det eller snarere peger på et træ og peger på den næste plot, så videre og så videre. For at gøre en skov, vi kalder mkforest. Så har vi nogle ret brugbare funktioner her. Vi har pluk hvor du passerer i en skov og så returværdien er en Tree *, en pointer til et træ. Hvilken pick vil gøre, er det vil gå ind i skoven, som du peger på derefter fjerne et træ med den laveste frekvens af denne skov og derefter give dig markøren til det træ. Når du ringer vælge, vil træet ikke findes i skoven længere, men returværdien er markøren til det træ. Så har du plante. Forudsat at du sender en pegepind til et træ, der har en ikke-0 frekvens, hvilken plante vil gøre, er det vil tage i skoven, tage træet og plante det træ inde i skoven. Her har vi rmforest. Svarende til fjerne træ, som dybest set befriet alle vores træer for os, fjerne skov vil fri alt indeholdt i denne skov. 

Hvis vi ser på forest.c, vil vi forvente at se mindst 1 rmtree kommando derinde, fordi at frigøre hukommelse i skoven, hvis en skov har træer i det, så til sidst du er nødt til at fjerne disse træer også. Hvis vi ser på forest.c, vi har vores mkforest, der er, som vi forventer. Vi malloc ting. Vi initialisere første plot i skoven som NULL, fordi det er tom til at begynde med, så må vi se pick, som returnerer træet med den laveste vægt, den laveste frekvens, og derefter slipper af denne særlige knude, der peger på det træ, og den næste, så det tager, at ud af den linkede liste af skoven. Og så har vi her plante, som indsætter et træ i den linkede liste. Hvilken skov gør, er det pænt holder det sorteres for os. Og så endelig har vi rmforest og som forventet har vi rmtree kaldes der. 

Ser man på fordelingen kode hidtil, huffile.c var sandsynligvis langt den sværeste at forstå, mens de andre filer selv var temmelig enkel at følge. Med vores viden om pointere og hægtede lister og sådan, vi var i stand til at følge ret godt. Men alt er vi nødt til virkelig sørge for, at vi fuldt ud forstår, er de. H-filer fordi du skal være at kalde disse funktioner, der beskæftiger sig med disse returværdier, så sørg for at du fuldt ud forstår, hvad handling vil blive udført når du kalder en af ​​disse funktioner. Men faktisk forståelse inde i det er ikke helt nødvendigt, fordi vi har dem. H-filer. Vi har 2 flere filer tilbage i vores distribution kode. 

Lad os se på dump. Dump ved sin kommentar her tager en Huffman-komprimeret fil og derefter oversætter og lossepladser hele dens indhold ud. Her ser vi, at det kalder hfopen. Det er en slags spejling til fil * input = fopen, og derefter du passerer i oplysningerne. Det er næsten ens, bortset fra i stedet for en fil * du passerer i en Huffile; i stedet for fopen du passerer i hfopen. Her læser vi i headeren første, som er slags ligner hvordan vi læser i overskriften for en bitmap-fil. Hvad vi laver her er at kontrollere at se, om header information indeholder den rigtige magiske tal, der angiver, at det er et virkeligt Huff fil, så alle disse kontroller for at sikre, at den fil, vi åbne, er et virkeligt huffed fil eller ej. Hvad dette gør, er det output frekvensen af ​​alle de symboler, vi kan se inden for en terminal til et grafisk tabel. Denne del vil være nyttig. Det har en lidt og læser lidt efter lidt ind i den variable bit og derefter udskriver det. Så hvis jeg skulle kalde dump den hth.bin, som er resultatet af huffing en fil med hjælp fra personalet løsning, ville jeg få det. Det udsende alle disse tegn og derefter sætte den frekvens, hvor de forekommer. Hvis vi ser, de fleste af dem er 0s bortset fra denne: H, der optræder to gange, og T, som forekommer en gang. Og så har vi her den egentlige budskab i 0'er og 1'ere. Hvis vi ser på hth.txt, hvilket formentlig den oprindelige meddelelse, der blev huffed, Vi forventer at se nogle Hs og Ts derinde. Konkret forventer vi at se kun 1 T og 2 HS. Her er vi i hth.txt. Det faktisk har HTH. Inkluderet i der, selv om vi ikke kan se det, er en ny linje. The Huff fil hth.bin også koder for newline karakter så godt. Her, fordi vi ved, at ordren er HTH og derefter newline, kan vi se, at formentlig H er repræsenteret ved blot en enkelt 1 og derefter T er formentlig 01 og derefter den næste H er 1, og og så har vi en ny linje angivet ved to 0'erne. Cool. 

Og så endelig, fordi vi arbejder med flere. C og. H-filer, vi skal have en temmelig kompleks argument til compileren, og så har vi her en Makefile, der gør dump for dig. Men faktisk, er du nødt til at gå om at gøre din egen puff.c fil. Den Makefile faktisk beskæftiger sig ikke med at gøre puff.c for dig. Vi forlader det op til dig at redigere Makefile. Når du indtaster en kommando som gør alle, for eksempel, vil det gøre dem alle for dig. Du er velkommen til at se på de eksempler på Makefile fra fortiden Pset samt at gå ud af denne ene for at se, hvordan du kan være i stand til at gøre din Puff fil ved at redigere denne Makefile. Det er om det for vores distribution kode. 

Når vi har fået igennem det, så her er bare endnu en påmindelse af, hvordan vi kommer til at beskæftige sig med de Huffman noder. Vi vil ikke være at kalde dem knuder længere, vi kommer til at kalde dem træer hvor vi kommer til at repræsentere deres symbol med en char, deres frekvens, antallet af forekomster, med et heltal. Vi bruger det, fordi det er mere præcis end en svømmer. Og så har vi en anden markøren til venstre barnet samt den rigtige barn. En skov, som vi så, er blot en sammenkædet liste over træer. I sidste ende, når vi opbygge vores Huff fil, Vi ønsker, at vores skov til at indeholde kun 1 træ - 1 træ, 1 rod med flere børn. Tidligere på, når vi var bare at gøre vores Huffman træer, vi startede ud ved at placere alle knuder på vores skærm og siger, at vi bliver nødt til disse knudepunkter, til sidst de vil være bladene, og dette er deres symbol, det er deres frekvens. I vores skov, hvis vi bare har 3 bogstaver, det er en skov på 3 træer. Og så da vi går videre, da vi tilføjet den første forælder, lavede vi en skov af 2 træer. Vi fjernede 2 af disse børn fra vores skov, og derefter erstattet den med en forælder node der havde disse 2 knudepunkter som børn. Og så endelig, vores sidste skridt med at gøre vores eksempel med As, Bs, og Cs ville være at foretage den endelige forælder, og så derefter at ville bringe vores samlede optælling af træer i skoven til 1. Skal alle se, hvordan du starter ud med flere træer i din skov og ender med 1? Okay. Cool. 

Hvad skal vi gøre for Puff? Hvad vi skal gøre, er at sikre, at, som altid, de giver os den rigtige type input således at vi rent faktisk kan køre programmet. I dette tilfælde de kommer til at give os efter deres første kommando-line argument 2 mere: den fil, vi ønsker at dekomprimere og outputtet af dekomprimerede fil. Men når vi sørge for, at de passerer os i den rigtige mængde af værdier, vi ønsker at sikre, at indgangen er en Huff fil eller ej. Og så når vi garantere, at det er en Huff fil, så vi ønsker at bygge vores træ, opbygge træet, således at den passer til træet, at den person, der sendte beskeden bygget. Så efter vi bygger træet, så vi kan behandle den 0'er og 1-taller, at de gik i, følge dem langs vores træ, fordi det er ens, og derefter skrive dette budskab ud, fortolke bits tilbage i tegn. Og så i slutningen, fordi vi har at gøre med pointere her, Vi ønsker at sikre, at vi ikke har nogen memory leaks og at vi fri alt. 

Sikring af korrekt brug er gammel hat for os nu. Vi tager i et input, som er kommer til at være navnet på den fil, der sug, og så må vi specificere et output, så navnet på filen for det puffede output, som bliver tekstfilen. Det er skik. Og nu ønsker vi at sikre, at input huffed eller ej. Tænker tilbage, var der noget i fordelingen kode, der kan hjælpe os med at forstå, om en fil er huffed eller ej? Der var information i huffile.c om Huffeader. Vi ved, at hver Huff fil har et Huffeader forbundet med det med et magisk tal samt et array af frekvenserne for hvert symbol samt en checksum. Vi ved det, men vi tog også et kig på dump.c, hvor det blev læst ind i en Huff fil. Og så at gøre det, det havde til at kontrollere, om det virkelig var huffed eller ej. Så måske vi kunne bruge dump.c som en struktur for vores puff.c. Tilbage til Pset 4, når vi havde den fil copy.c der kopieres i RGB tripler og vi fortolket for krimi og størrelse, ligeledes, hvad du kan gøre bare køre kommandoen ligesom cp dump.c puff.c og bruge nogle af koden der. Dog er det ikke kommer til at være så ligetil for en proces for at oversætte din dump.c i puff.c, men i det mindste giver dig et sted at starte om, hvordan man sikrer, at input faktisk huffed eller ikke samt et par andre ting. Vi har sikret god skik og sikret, at indgangen er huffed. Hver gang, at vi har gjort, at vi har gjort vores ordentlig fejlkontrol, så vender tilbage og afslutning af funktion, hvis nogle fejl opstår, hvis der er et problem. 

Nu, hvad vi ønsker at gøre, er at bygge selve træet. Hvis vi ser på Forest, der er 2 hovedfunktioner at vi kommer til at ønske at blive meget fortrolig med. Der er den Boolsk funktion plante, planter en ikke-0 frekvens træ inde i vores skov. Og så der du passere i en pegepind til en skov og en pointer til et træ. Hurtigt spørgsmål: Hvor mange skove vil du have, når du bygger en Huffman træ? Vores skov er ligesom vores lærred, right? Så vi kun vil have 1 skov, men vi vil have flere træer. Så før du ringer plante, du formentlig lyst til at gøre din skov. Der er en kommando til at hvis du kigger ind forest.h om hvordan du kan lave en skov. Du kan plante et træ. Vi ved, hvordan man gør det. Og så kan du også vælge et træ fra skoven, fjerne et træ med den laveste vægt og giver dig markøren til det. Tænker tilbage til, når vi var i gang med de eksempler, selv, når vi var tegning det ud, vi simpelthen bare tilføjede links. Men her i stedet for bare at tilføje de links, tænk på det mere som du fjerner 2 i disse knudepunkter og derefter erstatte den med en anden. For at udtrykke det i form af at plukke og plantemateriale, du er picking 2 træer og derefter plante et andet træ der har disse 2 træer, som du plukket som børn. At bygge Huffman s træ, kan du læse i de symboler og frekvenser for fordi Huffeader giver det dig giver dig en række af de frekvenser. Så du kan gå videre og bare ignorere noget med 0 i det fordi vi ikke ønsker 256 blade i slutningen af ​​det. Vi ønsker kun det antal blade, der er tegn der faktisk anvendes i filen. Man kan læse i disse symboler, og hver af disse symboler, der har ikke-0 frekvenser, dem vil være træer. Hvad du kan gøre er hver gang du læser i en ikke-0 frekvens symbol, du kan plante det træ i skoven. Når du plante træer i skoven, kan du tilmelde dig de træer som søskende, så gå tilbage til plantning og plukke hvor du vælger 2 og derefter plante-1, hvor at 1 at du planter er moderselskab for de 2 børn, du plukket. Så din slutresultatet vil være et enkelt træ i din skov. Det er, hvordan du opbygger dit træ. 

Der er flere ting, der kunne gå galt her fordi vi har at gøre med at gøre nye træer og beskæftiger sig med pegepinde og den slags. Før da vi havde at gøre med pegepinde, når vi malloc'd vi ønskede at sikre, at det ikke vendte tilbage til os en NULL pointer værdi. Så på flere trin i denne proces er der vil være flere sager hvor dit program kunne fejle. Hvad du ønsker at gøre, er du vil være sikker på, at du håndterer disse fejl, og i spec den siger at håndtere dem yndefuldt, så gerne udskrive en besked til brugeren at fortælle dem, hvorfor programmet har at holde op og derefter straks holde op det. For at gøre dette fejlhåndtering, så husk at du ønsker at kontrollere det hver eneste gang, at der kunne være en fiasko. Hver eneste gang du laver en ny pointer du vil være sikker på, at det er en succes. Før hvad vi plejede at gøre, er at lave en ny pointer og malloc det, og så ville vi kontrollere, om denne pegepind er NULL. Så der vil være nogle tilfælde, hvor du kan bare gøre det, men nogle gange du faktisk kalde en funktion og inden for denne funktion, er det den, der laver den mallocing. I så fald, hvis vi ser tilbage til nogle af funktionerne i koden nogle af dem er Boolske funktioner. I det abstrakte tilfælde, hvis vi har en boolesk funktion kaldet foo, dybest set, kan vi antage, at ud over at gøre hvad Foo gør, da det er en boolesk funktion, den returnerer sand eller falsk - tilfældet, hvis det lykkes, falsk hvis ikke. Så vi ønsker at kontrollere, om returværdien af ​​foo er sand eller falsk. Hvis det er falsk, det betyder, at vi kommer til at ønsker at udskrive en slags besked og derefter afslutte programmet. Hvad vi ønsker at gøre, er at kontrollere returværdien af ​​foo. Hvis Foo returnerer falsk, så ved vi, at vi stødte på en form for fejl og vi er nødt til at forlade vores program. En måde at gøre dette er at have en tilstand, hvor den faktiske funktion i sig selv er din tilstand. Sig Foo tager i x. Vi kan have som betingelse if (foo (x)). Dybest set, det betyder, hvis slutningen af ​​fuldbyrdelsesstaten Foo det returnerer sandt, så vi kan gøre dette, fordi funktionen har til at evaluere Foo for at vurdere den samlede tilstand. Så det er, hvordan du kan gøre noget, hvis funktionen returnerer true og bliver en succes. Men når du er fejlkontrol, du kun ønsker at holde op, hvis din funktion returnerer falsk. Hvad du kan gøre er bare at tilføje en == falsk eller bare tilføje et brag foran det og så har du if (! foo). Inden for dette organ af denne betingelse ville du have alle de fejlhåndtering, så gerne, "Kunne ikke oprette dette træ" og derefter returnere 1 eller sådan noget. Hvad det gør, er dog, at selvom Foo returneret falsk - Sig Foo returnerer sandt. Så du behøver ikke at kalde Foo igen. Det er en almindelig misforståelse. Fordi det var i din tilstand, er det allerede evalueret, så har du allerede det resultat, hvis du bruger lave træ eller noget i den retning eller plante eller pick eller noget. Det har allerede denne værdi. Det er allerede henrettet. Så det er nyttigt at bruge booleske funktioner som betingelse fordi, hvorvidt du rent faktisk udfører kroppen af ​​løkken, det udfører funktionen alligevel. 

Vores andet til sidste trin er at skrive beskeden til filen. Når vi bygger Huffman træ, så at skrive beskeden til filen er temmelig ligetil. Det er temmelig ligetil nu bare følge 0'er og 1'ere. Og så efter sædvane ved vi, at i en Huffman træet de 0'er angiver venstre og 1s angiver højre. Så hvis du læser i lidt efter lidt, hver gang du får et 0 vil du følge den venstre gren, og derefter hver gang du læser i en 1 du kommer til at følge den rette gren. Og så er du kommer til at fortsætte, indtil du rammer et blad fordi bladene vil være for enden af ​​grenene. Hvordan kan vi vide, om vi har ramt et blad eller ej? Vi sagde det før. [Studerende] Hvis markørerne er NULL. >> Yeah. Vi kan fortælle, hvis vi har ramt et blad, hvis de henvisninger til både venstre og højre træer er NULL. Perfekt. Vi ved, at vi ønsker at læse i lidt efter lidt ind i vores Huff fil. Som vi så før i dump.c, hvad de gjorde, er de læser i lidt efter lidt ind i Huff fil og lige udskrives hvad disse bit var. Vi kommer ikke til at gøre det. Vi vil gøre noget, der er en smule mere kompliceret. Men hvad vi kan gøre, er at vi kan tage den smule kode, som læser i til biddet. Her har vi den heltal bit svarende til den aktuelle bit at vi er på. Det tager sig af iteration alle bits i filen indtil du rammer slutningen af ​​filen. Baseret på det, du derefter vil ønske at have en form for iterator til at krydse dit træ. Og derefter baseret på, hvorvidt bitten er 0 eller 1, du vil ønsker at enten flytte det iterator til venstre eller flytte den til højre hele vejen, indtil du rammer et blad, så hele vejen indtil denne node, du er på ikke pege på nogen flere noder. Hvorfor kan vi gøre dette med en Huffman-fil, men ikke morsekode? Fordi i morsekode der er lidt af tvetydighed. Vi kunne være ligesom, oh vente, har vi ramt et brev undervejs, så måske det er vores brev, hvorimod hvis vi fortsatte bare lidt længere tid, så ville vi have ramt et andet brev. Men det kommer ikke til at ske i Huffman kodning, så vi kan være forvisset om, at den eneste måde, at vi kommer til at ramme en karakter er, hvis nodens venstre og højre børn er NULL. 

Endelig ønsker vi at befri alle vores hukommelse. Vi ønsker at både tæt på Huff fil, som vi har været der beskæftiger sig med samt fjerne alle træerne i vores skov. Baseret på din implementering, er du sandsynligvis vil ønsker at kalde fjerne skov i stedet for rent faktisk at gå gennem alle træerne selv. Men hvis du har lavet nogle midlertidige træer, vil du ønsker at frigøre det. Du kender din kode bedst, så du ved, hvor du allokering af hukommelse. Og så hvis du går i, starte med selv Kontrol F'ing for malloc, se, når du malloc og sikre, at du frigøre alt dette men så bare gå gennem din kode, forstå, hvor du måske har allokeret hukommelse. Normalt kan du bare sige: "I slutningen af ​​en fil, jeg vil bare fjerne skov på min skov," så dybest set klart, at hukommelse, fri, at "Og så er jeg også kommer til at lukke filen og derefter mit program kommer til at holde op." Men er det den eneste gang, at dit program afsluttes? Nej, fordi nogle gange er der måske have været en fejl, der skete. Måske kunne vi ikke åbne en fil eller vi kunne ikke gøre andet træ eller anden form for fejl skete i hukommelsen tildelingsprocessen og så det returnerede NULL. En fejl skete, og så vi vendte tilbage og sagde op. Så du vil være sikker på, at enhver mulig tid, at dit program kan holde op, du vil frigøre alle dine hukommelse der. Det er ikke bare at være i slutningen af ​​den vigtigste funktion, at du afslutter din kode. Du ønsker at se tilbage på alle tilfælde at din kode potentielt kan vende tilbage i utide og derefter fri uanset hukommelse giver mening. Sig du havde kaldt lave skov og det returneres falsk. Så har du sandsynligvis ikke brug for at fjerne din skov fordi du ikke har en skov endnu. Men på ethvert punkt i koden, hvor du kan returnere tidligt du vil være sikker på, at du frigøre eventuel hukommelse. 

Så når vi har at gøre med at frigøre hukommelse og har potentielle lækager, Vi vil ikke kun bruge vores dømmekraft og vores logik men også bruge Valgrind til at afgøre, om vi har befriet alle vores hukommelse korrekt eller ej. Du kan enten køre Valgrind på Puff og så er du nødt til også at give det det rigtige antal kommandolinjeargumenter til Valgrind. Du kan køre det, men produktionen er en smule kryptisk. Vi har fået lidt vant til det med Speller, men vi har stadig brug for lidt mere hjælp, så derefter kører det med et par flere flag som den læk-check = fuld, der sandsynligvis vil give os nogle mere nyttigt udgang på Valgrind. 

Så en anden nyttig tip, når du debugging er kommandoen diff. Du kan få adgang personalets implementering af Huff, køre det på en tekstfil, og derefter sende den til en binær fil, en binær Huff fil, for at være specifik. Så hvis du kører din egen puff på denne binære fil, så ideelt, din udlæste tekstfil vil være identisk til den oprindelige at du har bestået i. Her Jeg bruger hth.txt som eksempel, og det er den, der talte om i din spec. Det er bogstavelig talt lige HTH og derefter en ny linje. Men absolut velkommen og du helt sikkert tilskyndes til at bruge længere eksempler til din tekst-fil. 

Du kan endda tage et skud på måske at komprimere og derefter dekomprimere nogle af de filer, du har brugt i Speller som krig og fred eller Jane Austen eller noget i den retning - det ville være lidt cool - eller Austin Powers, slags beskæftiger sig med større filer, fordi vi ikke ville komme ned til det hvis vi brugte det næste værktøj her, ls-l. Vi er vant til ls, som dybest set viser hele indholdet i vores nuværende bibliotek. Passing i flaget-l faktisk viser størrelsen af ​​disse filer. Hvis du går gennem Pset spec, det faktisk hjælper dig gennem oprettelse af den binære fil, af huffing det, og du kan se, at for meget små filer rummet omkostninger komprimere det og oversætte al denne information af alle frekvenser og sådan noget opvejer den faktiske fordele at komprimere filen i første omgang. Men hvis du kører det på nogle længere tekstfiler, så skal du måske se, at du begynder at få nogle fordele med til at komprimere disse filer. 

Og så endelig har vi vores gamle ven GDB, der er helt sikkert vil komme i handy også. 

Har vi spørgsmål om Huff træer eller processen måske for at gøre træerne eller andre spørgsmål om Huff'n Puff? Okay. Jeg bliver rundt til en smule. 

Tak, alle sammen. Dette var Walkthrough 6. Og held og lykke. 

[CS50.TV]