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

Hei, alle sammen, og velkommen til Walkthrough 6: Huff'n Puff. I Huff'n Puff hva vi gjør kommer til å bli håndtere en Huffman komprimert fil og deretter puffing opp igjen, så decompressing det, slik at vi kan oversette fra 0'er og 1'ere som brukeren sender oss og konvertere den tilbake til den opprinnelige teksten. Pset 6 kommer til å være ganske kult fordi du kommer til å se noen av verktøyene du brukte i pset 4 og pset 5 og type kombinere dem i en ganske godt konsept når du kommer til å tenke på det. 

Også, uten tvil, var pset 4 og 5 de mest utfordrende psets at vi hadde å tilby. Så fra nå, har vi denne en mer pset i C, og deretter etter at vi er på til web-programmering. Så gratulere dere for å komme over den tøffeste humpen i CS50. 

Flytte på for Huff'n Puff, er vår verktøykasse for denne pset kommer til å være Huffman trær, så forståelse ikke bare hvordan binære trær arbeid, men også spesielt Huffman trær, hvordan de er konstruert. Og så skal vi ha mye distribusjon koden i dette pset, og vi vil komme til å se at faktisk noen av koden Vi kan ikke være i stand til å fullt ut forstå ennå, og slik at de vil være. c-filer, men da deres tilhørende. h-filer vil gi oss nok forståelse for at vi trenger slik at vi vet hvordan disse funksjonene fungerer eller i det minste hva de skal gjøre - deres innganger og utganger - selv om vi ikke vet hva som skjer i den svarte boksen eller ikke forstår hva som skjer i den svarte boksen innenfor. Og så til slutt, som vanlig, har vi å gjøre med nye datastrukturer, bestemte typer noder som peker til visse ting, og så her har en penn og papir, ikke bare for designprosessen og når du prøver å finne ut hvordan din pset skal fungere men også under debugging. Du kan ha GDB sammen med din penn og papir mens du tar ned hva verdiene er, hvor pilene peker, og ting som det. 

Først la oss se på Huffman trær. Huffman trær er binære trær, noe som betyr at hver node har bare 2 barn. I Huffman trær den karakteristiske er at de mest hyppige verdier er representert ved færrest biter. Vi så i undervisningsrom eksempler på morse, som slags konsolidert noen bokstaver. Hvis du prøver å oversette en A eller en E, for eksempel, du oversette den ofte, så i stedet for å måtte bruke hele settet av biter allokert for at vanlige datatype, komprimerer du det ned til færre, og disse bokstavene som er representert sjeldnere er representert med lengre biter fordi du har råd til det når du veier ut frekvenser som de bokstavene står. Vi har den samme ideen her i Huffman trær hvor vi gjør en kjede, en slags vei for å komme til visse tegn. Og så tegnene som har mest frekvens kommer til å være representert med færrest biter. 

Måten du konstruere en Huffman tre er ved å plassere alle de tegnene som vises i teksten og beregning av deres frekvens, hvor ofte de vises. Dette kan enten være en telling av hvor mange ganger disse bokstavene, vises eller kanskje en prosentandel av ut av alle tegnene hvor mange hver enkelt vises. Og så hva du gjør er når du har alt det kartlagt, så du ser for 2 laveste frekvensene og deretter bli med dem som søsken der deretter foreldrenoden har en frekvens som er summen av de 2 barn. Og så du etter konvensjonen sier at venstre node, du følger at ved å følge 0 gren, og deretter helt til høyre node er en gren. Som vi så i morse, var den fikser at hvis du hadde bare et pip og pip det var tvetydig. Det kan enten være en bokstav eller det kan være en sekvens av to bokstaver. Og så hva Huffman trær gjør er fordi av natur av tegnene eller våre endelige faktiske tegn å være den siste noder på grenen - vi refererer til dem som løv - i kraft av at det ikke kan være noen tvetydighet i form av hvilken bokstav du prøver å kode med serien biter fordi intet langs biter som representerer en bokstav vil du møte en annen hele brevet, og det vil ikke være noen misforståelser der. Men vi vil gå inn i eksempler som dere kan faktisk se at i stedet for oss bare å fortelle deg at det er sant. 

La oss se på et enkelt eksempel på en Huffman treet. Jeg har en streng her som er 12 tegn lang. Jeg har 4 As, 6 B, og to Cs. Min første skritt vil være å telle. Hvor mange ganger ser A? Det vises 4 ganger i strengen. B vises 6 ganger, og C vises to ganger. Naturligvis, jeg kommer til å si jeg bruker B oftest, så jeg ønsker å representere B med færrest antall biter, færrest 0'er og 1'ere. Og da er jeg også kommer til å forvente C til å kreve at mest mulig av 0'er og 1'ere også. Først hva jeg gjorde her er jeg plassert dem i stigende rekkefølge i forhold til frekvensen. Vi ser at C og A, de er våre to laveste frekvenser. Vi skape en foreldrenoden, og at foreldrenoden ikke har en bokstav forbundet med det, men det har en frekvens, som er summen. Summen blir 2 + 4, som er 6. Deretter følger vi den venstre grenen. Hvis vi var på den seks node, så vi vil følge 0 for å få til C og deretter 1 for å få til A. Så nå har vi to noder. Vi har verdien 6, og deretter har vi også en annen node med verdien 6. Og så de to er ikke bare to laveste, men også bare 2 som er igjen, så vi bli med dem av en annen forelder, med summen blir 12. Så her har vi vår Huffman tre der for å få til B, ville det bare være litt en og deretter å komme til A vi ville ha 01 og deretter C har 00. Så her ser vi at utgangspunktet vi representerer disse tegn med enten 1 eller 2 biter der B, som forutsagt, har minst. Og da vi hadde forventet C å ha mest, men siden det er en så liten Huffman tre, deretter A er også representert ved to biter i motsetning til et sted i midten. 

Bare for å gå over en annen enkelt eksempel på Huffman treet, si at du har strengen "Hello". Hva du gjør er første du ville si hvor mange ganger vises H i dette? H vises en gang og deretter e vises en gang og da har vi l vises to ganger og o vises én gang. Og så så vi forventer hvilken bokstav å bli representert av det minste antall biter? [Student] l. >> L. Ja. l er rett. Vi forventer l å være representert ved det minste antall biter fordi jeg er mest brukt i strengen "Hello". Hva jeg skal gjøre nå er å trekke ut disse nodene. Jeg har 1, som er H, og deretter en annen 1, som er e, og deretter en 1, som er o - akkurat nå er jeg å sette dem i rekkefølge - og deretter 2, som er l. Så sier jeg slik at jeg bygger en Huffman treet er å finne de to noder med minst frekvenser og gjøre dem søsken ved å opprette en overordnet node. Her har vi tre noder med lavest frekvens. De er alle en. Så her vi velger hvilken som vi kommer til å knytte først. La oss si at jeg velger H og e. Summen av 1 + 1 er 2, men denne noden har ikke et brev forbundet med det. Det holder bare verdien. Nå ser vi på de neste to laveste frekvensene. Det er 2 og 1. Det kan være en av de 2, men jeg kommer til å velge denne. Summen er tre. Og så til slutt, jeg har bare to igjen, så da blir 5. Så her, som forventet, hvis jeg fyller i koding for det, 1s er alltid det riktige gren og 0s er den venstre. Da har vi l representert ved bare 1 bit og deretter o med 2 og deretter e med 2 og deretter H faller ned til 3 biter. Så du kan overføre denne meldingen "Hei" i stedet for å faktisk bruke tegnene ved bare 0'er og 1'ere. Men husk at i flere tilfeller hadde vi bånd med frekvens vår. Vi kunne ha enten sluttet seg til H og o første kanskje. Eller så senere når vi hadde l representert ved to samt sluttet en representert ved 2, kunne vi ha knyttet enten en. 

Og så når du sender 0'er og 1'ere, som faktisk ikke garantere at mottakeren kan fullt lese meldingen rett utenfor balltre fordi de ikke kunne vite hvilket vedtak du har gjort. Så når vi har å gjøre med Huffman komprimering, noe vi må fortelle mottakeren av meldingen vår hvor vi bestemte oss - De trenger å vite noen form for ekstra informasjon i tillegg til det komprimerte meldingen. De trenger å forstå hva treet faktisk ser ut, hvordan vi faktisk gjort disse beslutningene. 

Her ble vi bare gjøre eksempler basert på den faktiske teller, men noen ganger kan du også ha en Huffman tre basert på hvor ofte bokstaver vises, og det er nøyaktig samme prosess. Her jeg uttrykke det i form av prosenter eller en brøkdel, og så her akkurat det samme. Jeg finner to laveste, legger dem sammen, de neste 2 laveste, legger dem sammen, før jeg har en full tre. Selv om vi kunne gjøre det uansett, når vi har å gjøre med prosenter, det betyr at vi dele ting og håndtere desimaler eller snarere flyter hvis vi tenker datastrukturer av et hode. Hva vet vi om flyter? Hva er et vanlig problem når vi har å gjøre med flottører? [Student] Upresise aritmetikk. >> Ja. Unøyaktighet. På grunn av flyttall unøyaktighet, for dette pset slik at vi sørger for at at vi ikke mister noen verdier, så vi faktisk skal håndtere med tellingen. Så hvis du skulle tenke på en Huffman node, hvis du ser tilbake til strukturen her, hvis man ser på de grønne den har en frekvens tilknyttet så vel som det peker til en node til venstre sin samt en node til sin rett. Og så de røde det også har en karakter forbundet med dem. Vi kommer ikke til å gjøre separate seg for foreldre og deretter den endelige noder, som vi refererer til som blader, men heller de vil bare ha nullverdier. For hver node vil vi ha en karakter, symbolet som den noden representerer, deretter en frekvens så vel som en peker til dens venstre barn samt sin rett barn. Bladene, som er helt nederst, ville også ha node pekere til venstre for dem, og til høyre, men siden disse verdiene er ikke peker til faktiske noder, hva ville verdien være? >> [Student] NULL. >> NULL. Akkurat. Her er et eksempel på hvordan du kan representere frekvensen i flåter, men vi kommer til å håndtere det med heltall, så alt jeg gjorde er endre datatypen der. 

La oss gå videre til en litt mer av en kompleks eksempel. Men nå som vi har gjort de enkle enere, er det bare den samme prosessen. Du finner de to laveste frekvensene, summere frekvensene og det er den nye frekvensen av dine foreldre node, som peker deretter til venstre sin med 0 gren og høyre med en gren. Hvis vi har strengen "Dette er CS50", da vi telle hvor mange ganger er T nevnt, h nevnt, i, s, c, 5, 0. Så det jeg gjorde her er med de røde noder jeg bare plantet, Jeg sa jeg kommer til å ha disse tegnene til slutt på bunnen av treet mitt. De kommer til å være alle bladene. Så det jeg gjorde er jeg sortert dem etter frekvens i stigende rekkefølge, og dette er faktisk den måten at pset koden gjør det er det sorterer etter frekvens og deretter alfabetisk. Så det har tallene først og deretter alfabetisk etter frekvens. Så hva jeg ville gjøre er jeg ville finne to laveste. Det er 0 og 5. Jeg vil oppsummere dem, og det er to. Da ville jeg fortsette, finne neste to laveste. De er de to 1s, og deretter de blitt 2 også. Nå vet jeg at min neste skritt skal bli med det laveste antallet, som er T, 1, og deretter velge en av nodene som har 2 som frekvens. Så her har vi tre alternativer. Hva jeg skal gjøre for lysbildet er bare visuelt omorganisere dem for deg slik at du kan se hvordan jeg bygger den opp. Hva koden og distribusjon koden kommer til å gjøre ville være med på T en med 0 og 5 node. Så da at summene til 3, og deretter fortsetter vi prosessen. Den 2 og 2 nå er den laveste, så da de summen til 4. Alle følger så langt? Okay. Så etter at vi har 3 og 3 som må legges opp, så igjen jeg bare slå den slik at du kan se visuelt slik at det ikke blir for rotete. Da har vi en 6, og deretter det endelige steget nå er at vi bare har to noder vi oppsummere disse til å lage roten av vår treet, som er 10 år. Og tallet 10 er fornuftig fordi hver node representert, deres verdi, deres frekvens nummer, var hvor mange ganger de dukket opp i strengen, og da har vi 5 tegn i strengen vår, så det er fornuftig. Hvis vi ser opp på hvordan vi ville faktisk kode den, som forventet, på i-og s, som vises oftest representeres av færrest antall bits. 

Være forsiktig her. I Huffman trær saken saker faktisk. En stor S er annerledes enn en liten s.. Hvis vi hadde "Dette er CS50" med store bokstaver, så små s ville bare vises to ganger, ville være en node med 2 som sin verdi, og deretter store S ville bare være en gang. Så da treet ditt ville endre strukturene, fordi du faktisk har en ekstra blad her. Men summen vil fortsatt være 10 år. Det er hva vi faktisk kommer til å kalle sjekksummen, tilsetning av alle tellinger. 

Nå som vi har dekket Huffman trær, kan vi dykke inn Huff'n Puff, the pset. Vi kommer til å starte med en del spørsmål, og dette kommer til å få deg vant med binære trær og hvordan å operere rundt at: tegning noder, lage din egen typedef struct for en node, og se hvordan du kan sette inn i en binær tre, en som er sortert, traversing det, og ting som det. Denne kunnskapen er definitivt kommer til å hjelpe deg når du dykker inn i Huff'n Puff delen av pset. I standardversjonen av pset, er din oppgave å gjennomføre Puff, og i hacker-versjonen din oppgave er å gjennomføre Huff. Hva Huff gjør er det tar teksten og deretter det oversettes den til 0'er og 1'ere, slik at prosessen som vi gjorde ovenfor der vi telles frekvensene og deretter gjort treet og sa: "Hvordan får jeg T?" T er representert med 100, ting som det, og deretter Huff ville ta teksten og utgang som binære. Men også fordi vi vet at vi ønsker å tillate vår mottakeren av meldingen å gjenskape nøyaktig samme treet, det inkluderer også informasjon om frekvens teller. Så med Puff vi får en binær fil av 0'er og 1'ere og gitt også informasjonen om frekvensene. Vi oversetter alle de 0'er og 1'ere tilbake til den opprinnelige meldingen som var, så vi decompressing det. Hvis du gjør standardutgaven, trenger du ikke å gjennomføre Huff, så da kan du bare bruke de ansatte implementering av Huff. Det er instruksjoner i spec om hvordan du gjør det. Du kan kjøre de ansatte implementering av Huff på en viss tekstfil og deretter bruke denne produksjonen som innspill til Puff. 

Som jeg nevnte tidligere, har vi mye av distribusjon kode for denne. Jeg kommer til å begynne å gå gjennom den. Jeg kommer til å tilbringe mesteparten av tiden på. H-filer fordi i. c filer, fordi vi har. h og som gir oss med prototyper av funksjonene, Vi har ikke full trenger å forstå nøyaktig - Hvis du ikke forstår hva som skjer i de. C-filene, så ikke bekymre deg for mye, men definitivt prøve å ta en titt, fordi det kan gi noen hint og det er nyttig å bli vant til å lese andre folks kode. 

Ser på huffile.h i kommentarfeltet erklærer det et lag av abstraksjon for Huffman-kodet filer. Hvis vi går ned, ser vi at det er maksimalt 256 symboler som vi kanskje trenger koder for. Dette inkluderer alle bokstavene i alfabetet - store og små - og deretter symboler og tall, osv. Så her har vi et magisk tall som identifiserer en Huffman-kodet fil. Innenfor en Huffman kode de kommer til å ha en viss magi nummer assosiert med overskriften. Dette kan se ut som bare en tilfeldig magisk tall, men hvis du faktisk oversette det til ASCII, så det staver faktisk ut HUFF. Her har vi en struct for en Huffman-kodet fil. Det er alle disse egenskapene forbundet med en Huff fil. Deretter ned her har vi overskriften for en Huff fil, så vi kaller det Huffeader stedet for å legge den ekstra h fordi det høres det samme uansett. Søt. Vi har et magisk tall knyttet til den. Hvis det er en faktisk Huff fil, kommer det til å være nummer opp ovenfor, denne magiske ett. Og så vil det ha en matrise. Så for hvert symbol, som det er 256, det kommer til å liste opp hva frekvensen av disse symbolene er innenfor Huff filen. Og så til slutt har vi en kontrollsum for frekvensene, som bør være summen av disse frekvensene. Så det er hva en Huffeader er. Så har vi noen funksjoner som returnerer neste bit i Huff fil samt skriver litt til Huff filen, og deretter denne funksjonen her,, hfclose som lukker faktisk Huff filen. Før, var vi arbeider med rett bare fclose, men når du har en Huff fil, i stedet for fclosing det hva du faktisk kommer til å gjøre er å hfclose og hfopen det. De er spesifikke funksjoner til Huff filer som vi kommer til å være med å gjøre. Så her leser vi i overskriften og deretter skrive overskriften. 

Bare ved å lese. H-filen kan vi på en måte få en følelse av hva en Huff Filen kan være, hvilke egenskaper det har, uten å faktisk gå inn i huffile.c, som, hvis vi dykke i, kommer til å være litt mer komplisert. Den har alle de fil I / O her håndtere pekere. Her ser vi at når vi kaller hfread, for eksempel, er det fortsatt arbeider med fread. Vi er ikke å bli kvitt disse funksjonene helt, men vi sender dem å bli tatt vare på inne i Huff fil i stedet for å gjøre alt det selv. Du kan gjerne søke gjennom dette hvis du er nysgjerrig og gå og skrelle laget tilbake litt. 

Den neste fil som vi kommer til å se på er tree.h. Før i Walkthrough glir vi sa vi forventer en Huffman node og vi har gjort en typedef struct node. Vi forventer at det skal ha et symbol, en frekvens, og deretter 2 node stjerner. I dette tilfellet hva vi gjør er at dette er i hovedsak de samme unntatt i stedet for node skal vi kalle dem trær. Vi har en funksjon som når du ringer gjør treet den returnerer du et tre pekeren. Tilbake til Speller, når du var å lage en ny node du sa node * nytt ord = malloc (sizeof) og sånne ting. I utgangspunktet er mktree skal håndtere det for deg. Dessuten, når du ønsker å fjerne et tre, så det er egentlig frigjøre tre når du er ferdig med det, i stedet for eksplisitt kalle gratis på det, du er faktisk bare kommer til å bruke funksjonen rmtree hvor du passerer i pekeren til at treet og deretter tree.c vil ta seg av det for deg. 

Vi ser inn tree.c. Vi forventer de samme funksjonene bortsett fra å se gjennomføringen også. Som vi forventet, når du kaller mktree det mallocs størrelsen på et tre i en peker, initialiserer alle verdiene til NULL verdi, så 0s eller nullverdier, og returnerer deretter pekeren til det treet som du nettopp har malloc'd til deg. Her når du kaller fjerne treet det gjør første sikker på at du ikke er dobbelt befriende. Det gjør at du faktisk har et tre som du vil fjerne. Her fordi et tre har også sine barn, hva dette betyr er det kaller rekursivt fjerne treet til venstre node av treet samt høyre noden. Før det frigjør foreldre, må det frigjøre barna også. Forelder er også byttes ut med roten. Den første foreldre, så som tipp-tipp-tipp-tipp-oldefar eller bestemor treet, først må vi frigjøre ned nivåene først. Så traversere til bunnen, gratis dem, og deretter komme tilbake opp, gratis dem, etc. Så det er tre. 

Nå ser vi på skogen. Skog er der du plasserer alle dine Huffman trær. Det er å si at vi kommer til å ha noe som kalles en tomt som inneholder en peker til et tre, så vel som en peker til et plott kalt neste. Hva strukturen gjør denne typen ut? Den slags sier det der borte. Rett over her. En lenket liste. Vi ser at når vi har en tomt det er som en lenket liste av tomter. En skog er definert som en lenket liste av tomter, og så strukturen i skogen er vi bare nødt til en peker til vår første tomten og at tomten har et tre i den eller snarere peker til et tre og peker deretter til neste tomten, så videre og så videre. For å gjøre en skog vi kaller mkforest. Så har vi noen ganske nyttige funksjoner her. Vi har velge hvor du passerer i en skog, og deretter returverdien er a Tree *, en peker til et tre. Hva plukke vil gjøre det vil gå inn i skogen at du peker til deretter fjerne et tre med lavest frekvens fra den skogen og deretter gi deg pekeren til det treet. Når du ringer plukke, vil treet ikke eksisterer i skogen lenger, men returverdien er pekeren til det treet. Da har du plante. Forutsatt at du passerer i en peker til et tre som har en ikke-0 frekvens, hva anlegget vil gjøre det vil ta skogen, ta treet, og plante det treet inne i skogen. Her har vi rmforest. I likhet med fjerne treet, som i utgangspunktet frigjort alle våre trær for oss, fjerne skog vil frigjøre alt som finnes i denne skogen. 

Hvis vi ser inn forest.c, vil vi forvente å se minst en rmtree kommandoen i det, fordi å frigjøre minne i skogen hvis en skog har trær i den, så til slutt du nødt til å fjerne disse trærne også. Hvis vi ser inn forest.c, har vi vår mkforest, som er som vi forventer. Vi malloc ting. Vi initialiserer den første tomten i skogen som NULL fordi det er tomt for å begynne med, så ser vi hakke, som returnerer tre med lavest vekt, den laveste frekvensen, og deretter blir kvitt den aktuelle noden som peker til det treet og den neste, så det tar det ut av lenket liste av skogen. Og så her har vi plante, som setter et tre inn i lenket liste. Hva skogen gjør er det pent holder det sortert for oss. Og så til slutt har vi rmforest og som forventet, vi har rmtree kalt der. 

Ser på fordelingen koden så langt, var huffile.c trolig langt det vanskeligste å forstå, mens de andre filene selv var ganske enkel å følge. Med vår kunnskap pekere og koblede lister og slikt, vi var i stand til å følge ganske godt. Men alt vi trenger for å virkelig sørge for at vi fullt ut forstår er. H-filene fordi du må ringe disse funksjonene, som arbeider med disse returverdier, så sørg for at du fullt ut forstår hva som kommer til å skje når du ringe en av disse funksjonene. Men faktisk forstå innsiden av den er ikke helt nødvendig fordi vi har de. H-filer. Vi har 2 flere filer igjen i vår distribusjon kode. 

La oss se på fylling. Dumpe med kommentar sin her tar en Huffman-komprimert fil og deretter oversetter og dumper alle av innholdet ut. Her ser vi at det er ringer hfopen. Dette er slags speiling til fil * input = fopen, og deretter passere i informasjonen. Det er nesten identisk bortsett fra i stedet for en fil * du passerer i en Huffile; i stedet for fopen du passerer i hfopen. Her leser vi i overskriften først, som er slags ligner på hvordan vi leser i overskriften for en bitmap fil. Hva vi gjør her er å sjekke for å se om hodeinformasjon inneholder riktig magiske tallet som indikerer at det er en faktisk Huff fil, så alle disse kontrollene for å sikre at filen vi åpne er en faktisk huffed fil eller ikke. Hva dette er det utganger frekvensene av alle de symbolene som vi kan se innenfor en terminal i en grafisk tabell. Denne delen kommer til å være nyttig. Den har en litt og leser litt etter litt inn i variabel bit og deretter skrives det ut. Så hvis jeg skulle ringe dump hth.bin, som er et resultat av huffing en fil bruker de ansatte løsning, ville jeg få dette. Den sender alle disse tegnene og deretter sette den frekvensen som de dukker opp. Hvis vi ser, de fleste av dem er 0s bortsett fra dette: H, som vises to ganger, og deretter T, som vises når. Og så her har vi faktisk melding i 0'er og 1'ere. Hvis vi ser på hth.txt, som er antagelig den opprinnelige meldingen som ble huffed, Vi forventer å se noen Hs og Ts der. Konkret forventer vi å se bare en T og 2 Hs. Her er vi i hth.txt. Det har faktisk HTH. Inkludert i det, selv om vi ikke kan se det, er et linjeskift. Den Huff fil hth.bin også koding linjeskiftet også. Her fordi vi visste at ordren er HTH og deretter linjeskift, Vi kan se at trolig H er representert med bare en enkelt en og deretter T er trolig 01 og deretter den neste H er 1 så vel og så har vi et linjeskift angitt med to 0s. Cool. 

Og så til slutt, fordi vi arbeider med flere. C og. H-filer, vi kommer til å ha en ganske kompleks argument til kompilatoren, og så her har vi en Makefile som gjør dump for deg. Men faktisk, må du gå om å lage din egen puff.c fil. Makefile faktisk ikke håndtere gjør puff.c for deg. Vi drar det opp til deg å redigere Makefile. Når du går inn en kommando som gjør alt, for eksempel, vil det gjøre dem alle for deg. Føl deg fri til å se på eksempler på Makefile fra fortiden pset så vel som går ut av denne for å se hvordan du kan være i stand til å gjøre Puff fil ved å endre denne Makefile. Det er om det for vår distribusjon kode. 

Når vi har fått gjennom det, så her er bare en påminnelse av hvordan vi skal håndtere med Huffman noder. Vi kommer ikke til å kalle dem noder lenger, vi kommer til å kalle dem trær hvor vi kommer til å representere sitt symbol med en røye, deres frekvens, antall forekomster, med et heltall. Vi bruker det fordi det er mer presis enn en flåte. Og så har vi en annen pekeren til venstre barnet så vel som retten barnet. En skog, som vi så, er bare en lenket liste av trær. Til syvende og sist, når vi bygger opp vår Huff fil, Vi ønsker at våre skogen for å inneholde bare 1 tree - 1 tre, en rot med flere barn. Tidligere når vi var bare å gjøre våre Huffman trær, Vi startet med å plassere alle nodene på skjermen vår og sier vi kommer til å ha disse nodene, til slutt de kommer til å være bladene, og dette er deres symbol, dette er deres frekvens. I skogen vår hvis vi bare har 3 bokstaver, det er en skog av tre trær. Og deretter som vi går på, når vi lagt til den første forelder, vi har gjort en skog av to trær. Vi fjernet to av disse barna fra skogen vår og deretter erstattet den med en forelder node som hadde de to noder som barn. Og så til slutt, vår siste trinnet med å gjøre vårt eksempel med As, Bs, og Cs ville være å gjøre den endelige forelder, og så da at ville bringe vår samlede antallet trær i skogen til 1. Ser alle hvor du starter ut med flere trær i skogen din og ender opp med en? Okay. Cool. 

Hva trenger vi å gjøre for Puff? Hva vi trenger å gjøre er å sørge for at, som alltid, de gir oss den rette type innspill slik at vi faktisk kan kjøre programmet. I dette tilfellet de kommer til å være å gi oss etter deres første kommandolinjeargument 2 mer: filen som vi ønsker å dekomprimere og produksjonen av komprimerte filen. Men når vi sørge for at de passerer oss i riktig mengde av verdier, Vi ønsker å sikre at inngangen er en Huff fil eller ikke. Og så når vi garantere at det er en Huff fil, så vi ønsker å bygge vår treet, bygge opp treet slik at det samsvarer med treet som den personen som sendte meldingen bygget. Så etter at vi bygger treet, så kan vi avtale med 0'er og 1'ere at de gikk i, følg dem sammen treet vårt fordi det er identisk, og deretter skrive det budskapet ut, tolke biter tilbake i tegn. Og så på slutten fordi vi har å gjøre med pekere her, vi ønsker å sørge for at vi ikke har noen minnelekkasjer og at vi gratis alt. 

Sikre riktig bruk er gammelt hat for oss nå. Vi tar i en inngang, som er tenkt å være navnet på filen til å blåse, og da vi angir en utgang, så navnet på filen for oppblåst utgang, som vil være tekstfilen. Det er bruk. Og nå ønsker vi å sikre at inngangen er huffed eller ikke. Tenker tilbake, var det noe i fordelingen kode som kan hjelpe oss med å forstå om en fil er huffed eller ikke? Det var informasjon i huffile.c om Huffeader. Vi vet at hver Huff filen har en Huffeader forbundet med det med et magisk tall samt en matrise av frekvenser for hvert symbol så vel som en kontrollsum. Vi vet det, men vi tok også en titt på dump.c, der ble det lesing i en Huff fil. Og så å gjøre det, hadde det for å sjekke om det virkelig var huffed eller ikke. Så kanskje vi kunne bruke dump.c som en struktur for puff.c. vår Tilbake til pset 4 når vi hadde filen copy.c som kopieres i RGB tripler og vi tolket som for whodunit og størrelse, Tilsvarende er hva du kan gjøre bare kjøre kommandoen som cp dump.c puff.c og bruke noen av koden der. Men det er ikke til å være så enkelt på en prosess for å oversette ditt dump.c inn puff.c, men minst det gir deg et sted å starte på hvordan man skal sikre at inngangen er faktisk huffed eller ikke samt et par andre ting. Vi har sikret riktig bruk og sørget for at inngangen er huffed. Hver gang vi har gjort det vi har gjort våre riktig feilkontroll, så tilbake og avslutte funksjonen hvis noen oppstår, hvis det er et problem. 

Nå hva vi ønsker å gjøre er å bygge selve treet. Hvis vi ser på Forest, det er 2 hovedfunksjoner at vi kommer til å ønske å bli veldig godt kjent med. Det er den boolske funksjonen plante som planter en ikke-0 frekvens tre inne skogen vår. Og så det du passerer i en peker til en skog og en peker til et tre. Rask spørsmål: Hvor mange skog vil du ha når du bygger et Huffman tre? Skogen vår er som lerret vår, ikke sant? Så vi skal bare ha 1 skog, men vi kommer til å ha flere trær. Så før du ringer plante, er du antagelig kommer til å ønske å gjøre ditt skogen. Det er en kommando for at hvis du ser inn forest.h på hvordan du kan lage en skog. Du kan plante et tre. Vi vet hvordan du gjør det. Og så kan du også velge et tre fra skogen, fjerne et tre med lavest vekt og gir deg pekeren til det. Tenker tilbake til da vi gjorde eksemplene selv, når vi var å tegne den ut, vi rett og slett bare lagt koblingene. Men her i stedet for bare å legge til lenker, tenke på det mer som du fjerner 2 av disse nodene og deretter sette den ved en annen. For å uttrykke det i form av å plukke og plante, du plukke to trær og deretter plante et annet tre som har de 2 trær som du plukket som barn. Å bygge Huffman er tre, kan du lese i symboler og frekvenser for fordi Huffeader gir den til deg, gir deg en rekke av frekvensene. Så du kan gå videre og bare ignorere noe med 0 i det fordi vi ikke ønsker 256 blader på slutten av den. Vi ønsker bare antall blader som er tegn som faktisk blir brukt i filen. Du kan lese i disse symbolene, og hver av disse symbolene som har ikke-0 frekvenser, de kommer til å være trær. Hva du kan gjøre er hver gang du leser i en ikke-0 frekvens symbol, du kan plante det treet i skogen. Når du planter trærne i skogen, kan du bli med disse trærne som søsken, så kommer tilbake til planting og plukke der du plukker 2 og deretter plante 1, hvor det en som du planter er forelder til de to barna som du plukket. Så da sluttresultatet kommer til å være et enkelt tre i skogen din. Det er hvordan du bygger din treet. 

Det er flere ting som kan gå galt her fordi vi har å gjøre med å lage nye trær og håndtere pekere og sånt. Før når vi arbeider med pekere, når vi malloc'd vi ønsket å sørge for at det ikke returnerte oss en NULL-peker verdi. Så på flere trinn i denne prosessen kommer det til å være flere tilfeller hvor programmet kan mislykkes. Hva du ønsker å gjøre er du vil være sikker på at du håndterer disse feilene, og i spec sier det å håndtere dem grasiøst, så liker skrive ut en melding til brukeren som forteller dem hvorfor programmet har å slutte og deretter straks avslutte det. For å gjøre dette feilhåndtering, husk at du ønsker å sjekke det hver eneste gang at det kunne være en fiasko. Hver eneste gang du gjør en ny peker du vil være sikker på at det er vellykket. Før det vi pleide å gjøre er å lage en ny pekeren og malloc det, og da vi skulle sjekke om det pekeren er NULL. Så det kommer til å være noen tilfeller der du bare kan gjøre det, men noen ganger du faktisk ringer en funksjon og innen den funksjonen, er at den som gjør det mallocing. I så fall, hvis vi ser tilbake til noen av funksjonene i koden, noen av dem er boolske funksjoner. I den abstrakte tilfelle hvis vi har en boolsk funksjon som heter foo, utgangspunktet, kan vi anta at i tillegg til å gjøre hva Foo gjør, siden det er en boolsk funksjon, returnerer det sant eller usant - sant hvis det lykkes, false hvis ikke. Så vi ønsker å sjekke om returverdien av foo er sant eller usant. Hvis det er falsk, betyr det at vi kommer til å ønske å skrive ut noen form for melding og deretter avslutte programmet. Hva vi ønsker å gjøre er å sjekke returverdien av foo. Hvis foo returnerer false, da vet vi at vi har møtt noen form for feil og vi trenger å avslutte programmet vårt. En måte å gjøre dette er å ha en tilstand der selve funksjonen selv er din tilstand. Si foo tar i x. Vi kan ha som en tilstand hvis (foo (x)). Utgangspunktet betyr at hvis på slutten av utførende Foo returnerer det sant, så kan vi gjøre dette fordi funksjonen må vurdere Foo for å evaluere hele tilstand. Så da det er hvordan du kan gjøre noe hvis funksjonen returnerer sann og er vellykket. Men når du er feilkontroll, du bare ønsker å avslutte hvis funksjonen returnerer false. Hva du kan gjøre er å legge bare en == false eller bare legge en smell foran den og da har du if (! foo). Innenfor denne kroppen av at tilstanden ville du ha alle feilhåndtering, så som, "Kunne ikke opprette dette treet" og deretter tilbake 1 eller noe sånt. Hva som gjør det, skjønt, er at selv om Foo returnert falsk - Si foo returnerer true. Så du trenger ikke å ringe Foo igjen. Det er en vanlig misforståelse. Fordi det var i din tilstand, er det allerede vurdert, så du allerede har resultatet hvis du bruker gjør tre eller noe sånt eller plante eller pick eller noe. Det har allerede denne verdien. Det er allerede utført. Så det er nyttig å bruke boolske funksjoner som tilstanden fordi hvorvidt du faktisk utføre legemet av sløyfen, den utfører funksjon uansett. 

Vår nest siste trinnet er å skrive meldingen til filen. Når vi bygge Huffman treet, deretter skrive meldingen til filen er ganske grei. Det er ganske grei nå å bare følge 0'er og 1'ere. Og så etter konvensjonen vet vi at i en Huffman treet de 0s tyder igjen og 1s indikerer høyre. Så hvis du leser i litt etter litt, hver gang du får en 0 du vil følge den venstre grenen, og deretter hver gang du leser i en 1 du kommer til å følge den rette grenen. Og så kommer du til å fortsette til du treffer et blad fordi bladene kommer til å være ved slutten av grenene. Hvordan kan vi vite om vi har truffet et blad eller ikke? Vi har sagt det før. [Student] Hvis pekere er NULL. >> Ja. Vi kan fortelle om vi har truffet et blad hvis pekere til både venstre og høyre trær er NULL. Perfekt. Vi vet at vi ønsker å lese i litt etter litt inn i vår Huff fil. Som vi har sett før i dump.c, er hva de gjorde de leser i litt etter litt til Huff filen og bare skrives ut hva de bitene var. Vi kommer ikke til å være å gjøre det. Vi kommer til å gjøre noe som er litt mer komplisert. Men hva vi kan gjøre er at vi kan ta det litt med kode som leser inn til bit. Her har vi heltall bit representerer den nåværende litt at vi er på. Denne tar seg av iterating alle bitene i filen før du treffer slutten av filen. Basert på det, så du kommer til å ønske å ha noen form for iterator å passere tre. Og avhengig av hvorvidt den biten er 0 eller 1, du kommer til å ønske å enten flytte det iterator til venstre eller flytte den til høyre helt til du treffer et blad, så hele veien inntil den noden som du er på peker ikke på noen flere noder. Hvorfor kan vi gjøre dette med en Huffman fil, men ikke morse? Fordi i morse det er litt av tvetydighet. Vi kunne være like, oh vent, har vi traff et brev underveis, så kanskje dette er vårt brev, mens hvis vi fortsatte bare litt lenger, så vi ville ha truffet en annen bokstav. Men det kommer ikke til å skje i Huffman koding, slik at vi kan være trygg på at den eneste måten vi kommer til å treffe en karakter er hvis det nodens venstre og høyre barn er NULL. 

Til slutt ønsker vi å frigjøre alle hukommelsen vår. Vi ønsker å både lukke Huff filen vi har vært håndtere samt fjerne alle trærne i skogen vår. Basert på implementeringen, er du sannsynligvis kommer til å ønske å ringe fjerne skog i stedet for faktisk å gå gjennom alle trærne selv. Men hvis du har gjort noen midlertidige trær, vil du ønsker å frigjøre det. Du kjenner din kode best, slik at du vet hvor du tildele minne. Og så hvis du går i, starte med selv kontroll F'ing for malloc, se når du malloc og sørge for at du frigjøre alle som men da bare gå gjennom koden din, forstå hvor du kan ha allokert minne. Vanligvis kan du bare si: "På slutten av en fil jeg bare kommer til å fjerne skog på min skog," så i utgangspunktet klart at minnet, gratis som, "Og da er jeg også kommer til å lukke filen og deretter mitt program kommer til å slutte." Men er det den eneste gangen at programmet avsluttes? Nei, fordi noen ganger det kan ha vært en feil som har skjedd. Kanskje vi ikke kunne åpne en fil eller vi kunne ikke gjøre annet tre eller annen form for feil som skjedde i minnetildeling prosessen og så den returnerte NULL. En feil skjedde, og da vi returnerte og sluttet. Så da du vil være sikker på at eventuelle tid at programmet kan avslutte, du vil frigjøre hele minnet der. Det er ikke bare kommer til å være helt på slutten av den viktigste funksjonen at du avslutter koden. Du ønsker å se tilbake til hvert tilfelle at koden potensielt kan returnere tidlig og deretter gratis uansett minne er fornuftig. Si at du hadde kalt lage skog og som returnerte falsk. Så har du sannsynligvis ikke trenger å fjerne skog fordi du ikke har en skog ennå. Men på hvert punkt i koden der du kan gå tilbake for tidlig du vil være sikker på at du frigjøre eventuelle minne. 

Så når vi har å gjøre med å frigjøre minne og ha potensielle lekkasjer, vi ønsker å ikke bare bruke vår dømmekraft og vår logikk men også bruke Valgrind å avgjøre om vi har frigjort alle våre minnet riktig eller ikke. Du kan enten kjøre Valgrind på Puff og deretter må du også passere det riktig antall kommandolinjeargumenter å Valgrind. Du kan kjøre det, men produksjonen er litt kryptisk. Vi har fått litt vant til det med Speller, men vi trenger fortsatt litt mer hjelp, så da kjører det med noen flere flagg som lekkasje-sjekk = full, som trolig vil gi oss litt mer nyttig utgang på Valgrind. 

Så en annen nyttig tips når du debugging er diff-kommandoen. Du får tilgang til ansatte implementering av Huff, kjøre den på en tekstfil, og deretter sende den til en binær fil, en binær Huff fil, for å være spesifikk. Så hvis du kjører din egen puff på at binærfil, så ideelt, er outputted tekstfil kommer til å være identiske til den opprinnelige at du har bestått i. Her Jeg bruker hth.txt som eksempel, og det er den snakket om i spec. Det er bokstavelig talt bare HTH og deretter en ny linje. Men definitivt føle seg fri og du er definitivt oppfordres til å bruke lengre eksempler for tekstfilen. 

Du kan selv ta en sjanse på kanskje komprimere og deretter decompressing noen av filene som du brukte i Speller som Krig og fred eller Jane Austen eller noe sånt - det ville være slags kult - eller Austin Powers, slags håndtere større filer fordi vi ikke ville komme ned til det hvis vi brukte den neste verktøyet her, ls-l. Vi er vant til ls, som i utgangspunktet viser alt innholdet i vår nåværende katalog. Passerer i flagget-l viser faktisk størrelsen på disse filene. Hvis du går gjennom pset spec, går det faktisk du gjennom å skape den binære filen av huffing det, og du ser at for svært små filer plass kostnadene komprimere det og oversette all denne informasjonen av alle frekvenser og sånt oppveier den faktiske nytte å komprimere filen i første omgang. Men hvis du kjører det på noen lengre tekstfiler, så du kan se at du begynner å få noen fordel i komprimere disse filene. 

Og så til slutt har vi vår gamle kompis GDB, som definitivt kommer til å komme i hendig for. 

Har vi noen spørsmål om Huff trær eller prosessen kanskje for å gjøre trærne eller andre spørsmål om Huff'n Puff? Okay. Jeg skal holde rundt for litt. 

Takk, alle sammen. Dette var Walkthrough 6. Og lykke til. 

[CS50.TV]