[Powered by Google Translate] [Walkthrough - Problem Set 6] [Zamyla Chan - Harvarduniversitetet] [Detta är CS50. - CS50.TV] 

Hej, alla, och välkommen till Walkthrough 6: Huff'n Puff. I Huff'n Puff vad vi gör kommer att ha att göra med en Huffman komprimerad fil och sedan blåsa tillbaka upp, så dekomprimering det, så att vi kan översätta från 0 och 1 som användaren skickar oss och omvandla den tillbaka till den ursprungliga texten. Pset 6 kommer att vara ganska coolt eftersom du kommer att se några av de verktyg som du använde i pset 4 och pset 5 och typ av kombinera dem till 1 ganska snyggt koncept när du kommer att tänka på det. 

Också utan tvekan var pset 4 och 5 de mest utmanande psets som vi hade att erbjuda. Så från och med nu har vi denna 1 mer pset i C, och sedan efter att vi är på att webbprogrammering. Så gratulerar er för att få över den tuffaste puckel i CS50. 

Flytta på för Huff'n Puff är vår verktygslåda för pset kommer att vara Huffman träd, så förstå inte bara hur binära träd arbete men också specifikt Huffman träd, hur de konstrueras. Och då ska vi ha en massa utdelning kod i pset, och vi kommer att se att faktiskt en del av koden Vi kanske inte kan till fullo förstå ännu, och så de kommer att vara. C-filer, men då deras medföljande. h-filer kommer att ge oss tillräckligt med kunskap som vi behöver, så att vi vet hur dessa funktioner fungerar eller åtminstone vad de ska göra - deras in-och utgångar - även om vi inte vet vad som händer i den svarta lådan eller förstår inte vad som händer i den svarta lådan i. Och slutligen, som vanligt har vi att göra med nya datastrukturer, specifika typer av noder som pekar på vissa saker, och så här med en penna och papper, inte bara för designprocessen och när du försöker lista ut hur din pset bör arbeta men också under felsökning. Du kan ha GDB tillsammans med ditt penna och papper medan du tar ner vad värdena, där dina pilarna pekar och sådana saker. 

Först ska vi titta på Huffman träd. Huffman träd är binära träd, vilket innebär att varje nod endast har 2 barn. I Huffman träd egenskapen är att de vanligaste värdena representeras av de minsta bitarna. Vi såg i föreläsningssalar exempel på morsekod, vilken typ av koncernens några brev. Om du försöker översätta ett A eller ett E, till exempel, du översätter det ofta, så istället för att behöva använda hela uppsättningen bitar avsatts för att vanliga datatyp komprimera du ner till färre, och sedan dessa bokstäver som utgjorde mindre ofta representerade med längre bitar eftersom du har råd att när du väga de frekvenser som dessa skrivelser visas. Vi har samma idé här i Huffman träd där vi gör en kedja, en slags väg för att komma till vissa tecken. Och sedan de tecken som har mest frekvensen kommer att vara representerade med minst antal bitar. 

Det sätt som du konstruera en Huffman träd är genom att placera alla de tecken som visas i texten och beräkna deras frekvens, hur ofta de förekommer. Detta kan antingen vara en räkningen på hur många gånger dessa bokstäver visas eller kanske en procentandel av av alla tecken hur många var och en visas. Och så vad du gör är när du har allt det utstakad, då du leta efter 2 lägsta frekvenserna och sedan gå med dem som syskon där då den överordnade noden har en frekvens som är summan av dess 2 barn. Och sedan genom konventionen säger att den vänstra noden, du följer det genom att följa 0 gren, och sedan längst till höger nod är 1 gren. Som vi såg i morsekod, var en gotcha att om du bara hade en ljudsignal och pip det var tvetydigt. Det kan antingen vara 1 bokstav eller det kan vara en sekvens av 2 bokstäver. Och så vad Huffman träd gör beror av naturen av tecknen eller våra sista faktiska tecken är de sista noderna på grenen - Vi hänvisar till de som löv - på grund av att det inte kan finnas någon tvetydighet enligt vilken bokstav du försöker koda med serien av bitar eftersom ingenstans längs de bitar som representerar 1 bokstav kommer du att stöta annan hela brevet, och det kommer inte finnas någon förvirring där. Men vi ska gå in exempel som ni faktiskt kan se att istället för oss berättar just om att det är sant. 

Låt oss titta på ett enkelt exempel på en Huffman träd. Jag har en sträng här som är 12 tecken långt. Jag har 4 As, 6 B, och 2 Cs. Mitt första steg skulle vara att räkna. Hur många gånger verkar A? Det verkar 4 gånger i strängen. B visas 6 gånger, och C visas 2 gånger. Naturligtvis, jag kommer att säga att jag med B oftast, så jag vill representera B med minst antal bitar, det minsta antalet 0 och 1. Och då jag också kommer att förvänta sig C för att kräva mest mängd av 0 och 1 samt. Först vad jag gjorde här är jag placerade dem i stigande ordning i fråga om frekvens. Vi ser att C och A, de är våra 2 lägsta frekvenserna. Vi skapar en förälder nod och att överordnade noden inte har ett brev i samband med det, men det har en frekvens, som är summan. Summan blir 2 + 4, vilket är 6. Sedan följer vi den vänstra grenen. Om vi ​​på det 6 nod, då skulle vi följa 0 för att komma till C och sedan 1 för att få till A. Så nu har vi 2 noder. Vi har värdet 6 och vi har också en annan nod med värdet 6. Och så de 2 är inte bara 2 lägst men också bara 2 som är kvar, så vi går dem av en annan förälder, med summan är 12. Så här har vi vår Huffmanträd om att få till B, det skulle bara vara lite 1 och sedan komma till en vi skulle ha 01 och sedan C med 00. Så här ser vi att i princip vi representerar dessa tecken med antingen 1 eller 2 bitar där B, som förväntat, har minst. Och sedan vi hade förväntat C ha mest, men eftersom det är en så liten Huffman träd, då A är även representerad av 2 bitar i motsats till någonstans i mitten. 

Bara att gå över en annan enkelt exempel på Huffman träd, säga att du har strängen "Hej." Vad du gör är du först skulle säga hur många gånger gör H visas i detta? H visas en gång och sedan e visas en gång och sedan har vi l förekommer två gånger och o visas en gång. Och så då förväntar vi oss vilken bokstav som representeras av det minsta antalet bitar? [Studenten] L. >> L.. Ja. l är rätt. Vi förväntar jag att företrädas av det minsta antalet bitar för att jag används mest i strängen "Hello". Vad jag ska göra nu är att dra ut dessa noder. Jag har 1, vilket är H, och sedan en annan 1, som är e, och sedan en 1, som är o - just nu är jag sätta dem i ordning - och sedan 2, vilket är l. Då säger jag det sätt som jag bygger en Huffman träd är att hitta de 2 noder med de minst frekvenserna och göra dem syskon genom att skapa en förälder nod. Här har vi 3 noder med den lägsta frekvensen. De är alla 1. Så här väljer vi vilken vi ska länka först. Låt oss säga att jag väljer H och e. Summan av 1 + 1 är 2, men denna nod inte har ett brev i samband med det. Det håller bara värdet. Nu ser vi på de närmaste 2 lägsta frekvenserna. Det är 2 och 1. Det kan vara någon av dessa 2, men jag kommer att välja här. Summan är 3. Och slutligen har jag bara 2 kvar, så då blir 5. Då här, som förväntat, om jag fylla i kodning för att 1s är alltid rätt gren och 0: or är den vänstra. Då har vi L representeras av bara 1 bit och sedan o med 2 och därefter e med 2 och sedan H faller ned till 3 bitar. Så du kan skicka meddelandet "Hej" istället för att faktiskt använda tecknen genom att bara 0 och 1. Kom dock ihåg att i flera fall hade vi band med vår frekvens. Vi kunde ha antingen gått H och O 1. Kanske. Eller senare när vi hade L representeras av 2 samt gick en representeras av 2, kunde vi ha kopplat antingen en. 

Och så när du skickar 0 och 1, som faktiskt inte garanterar att mottagaren kan helt läsa ditt meddelande höger utanför bat eftersom de kanske inte vet vilket beslut du gjort. Så när vi har att göra med Huffman-komprimering, på något sätt måste vi tala om för mottagaren av vårt budskap om hur vi bestämde - De behöver veta någon form av extra information Förutom den komprimerade meddelandet. De måste förstå vad trädet egentligen ser ut, hur vi gjorde faktiskt dessa beslut. 

Här var vi bara göra exempel baserade på faktiska räkningen, men ibland kan du också ha en Huffman träd baserat på den frekvens där bokstäverna visas, och det är exakt samma process. Här jag uttrycka det i termer av procent eller en fraktion, och så här exakt samma sak. Jag tycker att 2 lägsta, summera dem, nästa 2 lägsta, summera dem, tills jag har en full träd. Även om vi kunde göra det hur som helst, när vi har att göra med procentsatser, det betyder att vi dela saker och hantera decimaler eller snarare flyter Om vi ​​tänker på datastrukturer i ett huvud. Vad vet vi om flottar? Vad är ett vanligt problem när vi har att göra med flöten? [Elev] oprecisa aritmetik. >> Ja. Inexakthet. På grund av flyttal vaghet, för pset så att vi ser till att vi inte förlorar några värden, så vi faktiskt kommer att ha att göra med räkningen. Så om du skulle tänka på en Huffman nod, om man ser tillbaka till strukturen här, om man tittar på de gröna har en frekvens i samband med det liksom det pekar på en nod till vänster samt en nod till sin rätt. Och sedan de röda det också har en karaktär i samband med dem. Vi kommer inte att göra separata dem för föräldrarna och sedan de sista noder, som vi kallar löv, utan de kommer bara att ha NULL-värden. För varje nod kommer vi att ha ett tecken, en symbol som den noden representerar, då en frekvens samt en pekare till dess vänstra underordnade och dess högra underordnade. Bladen, som är längst ner, skulle också ha nod pekare till deras vänster och till höger, men eftersom dessa värden inte pekar på faktiska noder, vad skulle deras värde vara? >> [Elev] NULL. >> NULL. Exakt. Här är ett exempel på hur du kan representera frekvensen i flottar, men vi kommer att ha att göra med det med heltal, så allt jag gjorde är att ändra datatypen där. 

Låt oss gå vidare till lite mer av en komplex exempel. Men nu när vi har gjort de enkla, det är bara samma process. Du hittar 2 lägsta frekvenserna, summera frekvenserna och det är den nya frekvensen av din förälder nod, som pekar sedan till vänster med 0 grenen och höger med 1 gren. Om vi ​​har strängen "Detta är CS50," vi räkna hur många gånger T nämns, h nämnde, i, s, c, 5, 0. Sen vad jag gjorde här är de röda noderna jag planterade, Jag sa att jag kommer att ha dessa tecken så småningom på botten av mitt träd. De kommer att vara alla av bladen. Sen vad jag gjorde är jag sorterade dem efter frekvens i stigande ordning, och detta är faktiskt det sätt som pset koden gör det är det sorterar det efter frekvens och sedan i alfabetisk ordning. Så det har siffrorna först och sedan alfabetiskt efter frekvensen. Så vad jag skulle göra är jag skulle hitta 2 lägsta. Det är 0 och 5. Jag skulle sammanfatta dem, och det är 2. Då skulle jag fortsätta söka efter nästa 2 lägst. Dessa är de två 1s, och sedan de blivit 2 också. Nu vet jag att mitt nästa steg kommer att gå det lägsta antalet, som är T, 1, och sedan välja en av de noder som har 2 som frekvensen. Så här har vi 3 alternativ. Vad jag ska göra för bilden är bara visuellt ändra dem åt dig så att du kan se hur jag bygger upp den. Vad koden och din distribution kod kommer att göra skulle gå med T en med 0 och 5 nod. Så då summor till 3 och sedan fortsätter vi processen. Den 2 och 2 är nu den lägsta, så då de belopp till 4. Alla följer hittills? Okej. Sedan efter att vi har 3 och 3 som behöver läggas upp, så igen jag bara byta den så att du kan se visuellt så att det inte blir för rörigt. Sedan har vi en 6, och sedan vår sista steget är nu att vi bara har 2 noder Vi summerar dem för att göra rot vår träd, vilket är 10. Och antalet 10 vettigt eftersom varje nod representerade, deras värde, deras frekvens nummer, var hur många gånger de dök upp i strängen, och sedan har vi 5 tecken i vår sträng, så det är vettigt. Om vi ​​tittar upp på hur vi faktiskt skulle koda det, som väntat, i-och s, som förekommer det oftast representeras av det minsta antalet bitar. 

Var försiktig här. I Huffman träd fallet betyder faktiskt. Ett versalt S är annorlunda än ett gement s.. Om vi ​​hade "Detta är CS50" med versaler, då gement enda verkar två gånger, skulle vara en nod med 2 som dess värde, och sedan versaler S skulle bara vara en gång. Så då ditt träd skulle förändra strukturer eftersom du faktiskt har ett extra blad här. Men summan fortfarande skulle vara 10. Det är vad vi faktiskt kommer att vara ringa kontrollsumma, tillsats av samtliga räknas. 

Nu när vi har täckt Huffman träd, kan vi dyka in Huff'n Puff, den pset. Vi kommer att börja med en del av frågorna, och detta kommer att få dig van med binära träd och hur du använder runt det: ritning noder, skapa din egen typedef struct för en nod, och se hur du kan infoga i ett binärt träd, en som är sorterad, korsar den och sånt. Den kunskapen kommer definitivt att hjälpa dig när du dyker i Huff'n Puff delen av pset. I standardversionen av pset, är din uppgift att genomföra Puff, och i hacker versionen din uppgift är att genomföra Huff. Vad Huff gör är det tar text och sedan översätter det till 0 och 1, så den process som vi gjorde ovan där vi räknade frekvenserna och sedan gjorde trädet och sade sedan, "Hur får jag t?" T representeras av 100, saker, och sedan Huff skulle ta texten och sedan utgång som binär. Men också för att vi vet att vi vill att vår mottagare av meddelandet att återskapa exakt samma träd, innehåller den också information om frekvensen räknas. Sedan med Puff vi får en binär fil av 0 och 1 och ges även information om frekvenserna. Vi översätter alla dessa 0 och 1 tillbaka till det ursprungliga meddelandet som var, så vi dekomprimering det. Om du gör det Standard Edition, behöver du inte genomföra Huff, så kan du bara använda den personal genomförandet av Huff. Det finns instruktioner i spec på hur man gör det. Du kan köra den personal genomförandet av Huff på en viss textfil och sedan använda denna utgång som din ingång till Puff. 

Som jag nämnde tidigare har vi en hel del utdelning kod för detta. Jag ska börja gå igenom den. Jag kommer att tillbringa större delen av tiden på. H-filer eftersom de. c-filer, eftersom vi har. h. och som ger oss med prototyper av de funktioner, vi inte helt behöver förstå exakt - Om du inte förstår vad som händer i de. C filerna ska du inte oroa dig för mycket, men definitivt försöka att ta en titt, eftersom det kan ge några tips och det är bra att vänja sig att läsa andra människors kod. 

Titta på huffile.h, i kommentarerna den förklarar ett lager av abstraktion för Huffman-kodade filer. Om vi ​​går ner, ser vi att det är högst 256 tecken som vi kanske behöver koder för. Detta inkluderar alla bokstäver i alfabetet - versaler och gemener - och sedan symboler och siffror, etc. Så här har vi ett magiskt nummer som identifierar en Huffman-kodad fil. Inom en huffmankod de ska ha ett visst magiskt tal associerad med huvudet. Detta kan se ut som bara en slumpmässig magiskt nummer, men om du verkligen översätta det till ASCII, då stavar faktiskt ut Huff. Här har vi en struct för en Huffman-kodad fil. Det finns alla dessa egenskaper som en Huff fil. Sen här nere har vi rubriken för en Huff fil, så vi kallar det Huffeader stället för att lägga den extra h eftersom det låter lika ändå. Söt. Vi har ett magiskt nummer associerade med den. Om det är en verklig Huff fil, kommer det att vara nummer upp ovan denna magiska en. Och så kommer det att ha en array. Så för varje symbol, av vilka det finns 256, det kommer att lista vad Frekvensen av dessa symboler inom Huff filen. Och slutligen har vi en kontrollsumma för frekvenserna, som bör vara summan av dessa frekvenser. Så det är vad en Huffeader är. Sedan har vi några funktioner som returnerar nästa bit i Huff filen samt skriver lite till Huff filen och sedan denna funktion här,, hfclose som stänger faktiskt Huff filen. Förut var vi att göra med rakt bara fclose, men när du har en Huff fil, i stället för att fclosing det vad du egentligen ska göra är hfclose och hfopen det. De är specifika funktioner till Huff filer som vi kommer att ha att göra med. Så här vi läser i huvudet och sedan skriva rubriken. 

Bara genom att läsa. H. filen kan vi slags få en känsla för vad en Huff fil kan vara, vilka egenskaper den har, utan att faktiskt gå in i huffile.c, som, om vi dyka i, kommer att vara lite mer komplicerat. Den har alla de I / O-här behandlar pekare. Här ser vi att när vi kallar hfread till exempel, det är fortfarande arbetar med fread. Vi ska inte bli av med dessa funktioner helt, men vi skickar dem tas om hand inuti Huff fil i stället för att göra allt det själva. Du kan gärna söka igenom detta om du är nyfiken och gå och skala lagret tillbaka lite. 

Nästa fil som vi kommer att titta på är tree.h. Tidigare i Walkthrough glider vi sagt att vi förväntar oss en Huffman nod och vi gjorde en typedef struct nod. Vi räknar med att ha en symbol, en frekvens, och sedan 2 stjärnor noden. I det här fallet vad vi gör är att detta är i stort sett samma utom i stället för nod ska vi kalla dem träd. Vi har en funktion som när du ringer gör träd returneras dig ett träd pekare. Tillbaka till Speller, när du gör en ny nod du sa nod * nytt ord = malloc (sizeof) och sådana saker. I grund och botten är mktree kommer att ha att göra med det för dig. Likaså när du vill ta bort ett träd, så som i huvudsak är att befria trädet när du är klar med det, i stället för att uttryckligen kalla fritt på det, är du faktiskt bara att använda funktionen rmtree där du passerar i pekaren till det trädet och sedan tree.c tar hand om det åt dig. 

Vi ser på tree.c. Vi förväntar oss samma funktioner förutom att se genomförandet också. Som vi väntat, när du ringer mktree det mallocs storleken av ett träd i en pekare, initierar alla värden till det NULL värde, så 0s eller nollor, och återgår sedan pekaren till det trädet som du bara har malloc'd till dig. Här när du ringer bort träd det gör först kontrollera att du inte dubbla är att befria. Det ser till att du faktiskt har ett träd som du vill ta bort. Här eftersom ett träd innefattar även dess barn, Vad detta innebär är man kallar rekursivt ta bort träd på vänster nod i trädet liksom rätt noden. Innan det frigör förälder måste det frigöra barnen också. Moderbolaget är även utbytbar med root. Den första föräldern, så som den store-store-store-store-farfar eller mormor träd, först måste vi frigöra ner nivåerna först. Så korsar till botten, fri dem, och sedan komma tillbaka upp, utan dem, etc. Så det är trädet. 

Nu tittar vi på skogen. Forest är där du placerar alla dina Huffman träd. Det säger att vi kommer att ha något som kallas en tomt som innehåller en pekare till ett träd och en pekare till en tomt som kallas nästa. Vilken struktur gör denna typ av ut? Det slags säger där borta. Här borta. En länkad lista. Vi ser att när vi har en tomt är det som en länkad lista av tomter. En skog definieras som en länkad lista av tomter, och så struktur skogen är vi bara kommer att ha en pekare till vår första tomten och att tomten har ett träd i den, eller snarare pekar på ett träd och sedan pekar på nästa tomt, så vidare och så vidare. För att göra en skog som vi kallar mkforest. Sedan har vi några ganska användbara funktioner här. Vi har plocka där du passerar i en skog och sedan returvärdet är ett träd *, en pekare till ett träd. Hur pick gör det kommer att gå in i skogen som du pekar på sedan bort ett träd med den lägsta frekvensen från skogen och sedan ge dig pekaren till det trädet. När du ringer plocka, kommer trädet finns inte i skogen längre, men returvärdet är pekaren till det trädet. Då har du växt. Förutsatt att du skickar in en pekare till ett träd som har en icke-0 frekvens, hur anläggningen kommer att göra är det kommer att ta skogen, ta trädet, och plantera det trädet inne i skogen. Här har vi rmforest. I likhet med avlägsna träd, som i princip befriade alla våra träd för oss, ta bort skog kommer fri allt som står i skogen. 

Om vi ​​tittar på forest.c, vi förväntar oss att se minst 1 rmtree kommando där, eftersom att frigöra minne i skogen om en skog har träd i den, så småningom du kommer att behöva ta bort dessa träd också. Om vi ​​tittar på forest.c har vi vår mkforest, vilket är som vi förväntar oss. Vi malloc saker. Vi initiera den första tomten i skogen som NULL eftersom det är tomt till att börja med, då ser vi plocka, som returnerar trädet med den lägsta vikten, den lägsta frekvensen, och sedan gör sig av just nod som pekar på att trädet och nästa en, så det tar att av den länkade listan av skogen. Och så här har vi växt, som infogar ett träd i den länkade listan. Vilken skog gör är det snyggt håller det sorteras för oss. Och slutligen har vi rmforest och som väntat har vi rmtree kallas där. 

Man tittar på fördelningen koden så långt var huffile.c förmodligen den absolut svåraste att förstå, medan de andra filerna själva var ganska enkla att följa. Med vår kunskap om pekare och länkade listor och sådant, vi kunde följa ganska bra. Men allt vi behöver verkligen se till att vi förstår är det. H-filer eftersom du måste ringa dessa funktioner, som handlar om de returvärden, så se till att du till fullo förstår vilka åtgärder kommer att genomföras när du ringer ett av dessa funktioner. Men egentligen förstå inuti det inte helt nödvändigt eftersom vi har dem. H-filer. Vi har 2 fler filer kvar i vår distribution kod. 

Låt oss titta på soptippen. Dumpa genom sin kommentar här tar Huffman-komprimerad fil och sedan översätter och dumpar allt innehåll ut. Här ser vi att det ringer hfopen. Detta är typ av spegling att lämna * ingång = fopen, och då du passerar i informationen. Det är nästan identiska med undantag istället för en fil * du passerar en Huffile, istället för fopen du passerar i hfopen. Här läser vi i huvudet först, vilket är typ av liknar hur vi läser i huvudet för en bitmappsfil. Vad vi gör här är att kontrollera för att se om rubrikinformationen innehåller rätt magiska nummer som anger att det är en verklig Huff fil, då alla dessa kontroller för att se till att filen som vi öppen är en verklig blåste fil eller inte. Vad detta innebär är det matar frekvenserna för alla de symboler som vi kan se inom en terminal i en grafisk tabell. Denna del kommer att vara användbar. Den har en lite och läser bit för bit in i variabel bit och sedan skriver ut det. Så om jag skulle kalla dump den hth.bin, som är resultatet av huffing en fil med personal lösningen, skulle jag få detta. Det mata alla dessa tecken och sedan sätta den frekvens med vilken de visas. Om vi ​​ser, de flesta av dem är 0s förutom detta: H, som visas två gånger, och sedan T, som visas en gång. Och så här har vi själva meddelandet i 0 och 1. Om vi ​​tittar på hth.txt, vilket förmodligen det ursprungliga meddelandet som blåste, Vi förväntar oss att se några Hs och Ts där. Specifikt förväntar vi oss att se bara 1 T och 2 HS. Här är vi i hth.txt. Det har verkligen HTH. Ingår i det, även om vi inte kan se det, är ett radmatningstecken. Den Huff Filen hth.bin också kodar för nyradstecken också. Här eftersom vi vet att ordern är HTH och sedan nyrad, kan vi se att förmodligen H representeras av bara en enda 1 och då T är troligen 01 och sedan nästa H är 1 samt och sedan har vi en nyrad anges med två 0s. Cool. 

Och slutligen, eftersom vi har att göra med flera. C och. H-filer, vi kommer att ha en ganska komplex argument till kompilatorn, och så här har vi en Makefile som gör dumpa dig. Men faktiskt, måste du gå om att göra din egen puff.c fil. Makefile faktiskt inte behandlar göra puff.c för dig. Vi lämnar det upp till dig att redigera Makefile. När du anger ett kommando som gör allt, till exempel, kommer det att göra dem alla till dig. Känn dig fri att titta på exempel på Makefile från tidigare pset liksom att gå bort av denna för att se hur du skulle kunna göra ditt Puff fil genom att redigera den här Makefile. Det är ungefär det för vår distribution kod. 

När vi har fått igenom det, så här är bara en påminnelse hur vi ska ha att göra med Huffman noderna. Vi kommer inte att kalla dem noder längre, vi kommer att kalla dem träd där vi kommer att representera sin symbol med en röding, deras frekvens, antalet förekomster, med ett heltal. Vi använder det för att det är mer exakt än en flottör. Och då vi har en annan pekaren till vänster barnet samt rätt barn. En skog, som vi såg, är bara en länkad lista av träd. I slutändan, när vi bygger upp vår Huff fil, Vi vill att vår skog ska innehålla bara 1 träd - 1 träd, 1 rot med flera barn. Tidigare när vi bara göra våra Huffman träd, Vi började genom att placera alla noder på vår skärm och säger att vi ska ha dessa noder, Så småningom ska bli bladen, och detta är deras symbol, det är deras frekvens. I vår skog om vi bara har 3 bokstäver, det är en skog av 3 träd. Och sedan när vi går på, när vi lagt den första föräldern, Vi gjorde en skog av 2 träd. Vi bort 2 av dessa barn från vår skog och ersatt det med en förälder nod som hade de 2 noder som barn. Och sedan slutligen, vår sista steget med att göra vårt exempel med As, B, och Cs skulle vara att göra det slutliga moderbolaget, och så då skulle föra vår totala räkningen på träd i skogen till 1. Ser alla hur du börjar med flera träd i skogen och sluta med 1? Okej. Cool. 

Vad behöver vi göra för Puff? Vad vi behöver göra är att se till att, som alltid, de ger oss rätt typ av ingång så att vi verkligen kan köra programmet. I detta fall kommer att ge oss efter deras första kommandoradsargument 2 mer: den fil som vi vill expandera och utgången där den uppackade filen. Men när vi ser till att de passerar oss i rätt mängd värden, Vi vill se till att ingången är en Huff fil eller inte. Och sedan när vi garantera att det är en Huff fil, så vi vill bygga vårt träd, bygga upp trädet så att det matchar trädet att den person som skickade meddelandet byggas. Sedan efter vi bygger trädet, då kan vi ta itu med 0 och 1 som de gått i, Följ dem längs vår träd eftersom det är identiskt, och sedan skriva det budskap, tolka bitarna tillbaka i tecken. Och sedan i slutet eftersom vi har att göra med pekare här, Vi vill se till att vi inte har några minnesläckor och att vi gratis allt. 

Korrekt användning är gammal hatt för oss nu. Vi tar in en ingång, vilket kommer att bli namnet på filen att blåsa, och då vi anger en utgång, så namnet på filen för den puffade utmatning, som kommer att vara textfilen. Det är användningen. Och nu vill vi se till att ingången är huffed eller inte. Tänka tillbaka, var det något i distributionen kod som kan hjälpa oss med att förstå om en fil blåste eller inte? Det var information i huffile.c om Huffeader. Vi vet att varje Huff filen har en Huffeader i samband med det ett magiskt nummer såväl som en array av frekvenserna för varje symbol samt en kontrollsumma. Vi vet det, men vi tog också en titt på dump.c, där det läsa in en Huff fil. Och så för att göra det, måste den kontrollera om det verkligen var blåste eller inte. Så kanske vi kunde använda dump.c som en struktur för vår puff.c. Tillbaka till pset 4 när vi hade filen copy.c som kopieras i RGB tripplar och vi tolkade det för DECKARE och ändra storlek, liknande, vad du kan göra bara köra kommandot som cp dump.c puff.c och använda en del av koden där. Men, det kommer inte att vara så enkelt för en process för översättning din dump.c till puff.c, men åtminstone det ger dig någonstans att börja om hur man kan säkerställa att ingången faktiskt blåste eller inte liksom några andra saker. Vi har säkerställt korrekt användning och se till att ingången är huffed. Varje gång vi har gjort att vi har gjort vårt rätta felkontroll, så tillbaka och avsluta funktionen om något fel uppstår, om det finns ett problem. 

Nu vad vi vill göra är att bygga själva trädet. Om vi ​​tittar i Forest finns 2 huvudfunktioner att vi kommer att vilja bli väl förtrogen med. Det är den booleska funktionen växt som växter en icke-0 frekvens träd inne vår skog. Och så det du skickar i en pekare till en skog och en pekare till ett träd. Snabb fråga: Hur många skogar har du när du bygger en Huffman träd? Vår skog är som vår duk, eller hur? Så vi bara kommer att ha 1 skog, men vi kommer att ha flera träd. Så innan du ringer växt, du kommer förmodligen att vilja göra din skog. Det finns ett kommando för att om du tittar in forest.h på hur du kan göra en skog. Du kan plantera ett träd. Vi vet hur man gör det. Och då kan du också välja ett träd från skogen, bort ett träd med den lägsta vikt och ger dig pekaren till det. Tänker tillbaka på när vi gjorde de exempel själva, när vi drar ut, vi helt enkelt bara lagt till länkar. Men här i stället för att bara lägga länkarna, tänka på det mer som du tar bort 2 av dessa noder och sedan ersätta den med en annan. För att uttrycka det i termer av att plocka och plantera, du plockar 2 träd och sedan plantera ett annat träd som har de 2 träd som du plockat som barn. Att bygga Huffman s träd, kan du läsa i symboler och frekvenser för eftersom Huffeader ger det till dig, ger dig en rad av frekvenserna. Så du kan gå vidare och bara ignorera något med 0 i det eftersom vi inte vill 256 blad i slutet av den. Vi vill bara antalet blad som är tecken som faktiskt används i filen. Du kan läsa i dessa symboler, och var och en av dessa symboler som har icke-0 frekvenser, de kommer att bli träd. Vad du kan göra är varje gång du läser i en icke-0 frekvens symbol, du kan plantera det där trädet i skogen. När du plantera träden i skogen, kan du gå med dessa träd som syskon, så gå tillbaka till plantering och plocka där du väljer 2 och sedan växt 1, om detta 1 att du planterar är förälder till de 2 barnen som du plockat. Så då din slutresultatet kommer att bli ett enda träd i skogen. Det är hur du bygger ditt träd. 

Det finns flera saker som kan gå fel här eftersom vi har att göra med att göra nya träd och hantera pekare och sånt. Innan när vi hade att göra med pekare, när vi malloc'd vi ville se till att det inte returnera oss en NULL-pekare värde. Så vid flera steg i denna process det kommer att bli flera fall där ditt program kan misslyckas. Vad du vill göra är att du vill vara säker på att du hanterar dessa fel, och i spec står att hantera dem graciöst, så vill skriva ut ett meddelande till användaren berätta varför programmet måste sluta och sedan omgående avsluta det. För att göra detta felhantering, kom ihåg att du vill kontrollera den varje gång att det kan finnas ett fel. Varenda gång du gör en ny pekare du vill vara säker på att det är framgångsrikt. Innan vad vi brukade göra är att göra en ny pekare och malloc det, och då skulle vi kontrollera huruvida pekaren är NULL. Så det kommer att bli några fall där du bara kan göra det, men ibland du faktiskt ringer en funktion och inom den funktionen, det är den som gör det mallocing. I så fall, om vi ser tillbaka till vissa funktioner i koden, några av dem är booleska funktioner. I det abstrakta fallet om vi har en boolesk funktion som kallas foo, I princip kan vi anta att förutom att göra allt foo gör, eftersom det är ett booleskt funktion returnerar det sant eller falskt - sant om det lyckas, falskt om inte. Så vi vill kontrollera om returvärdet av foo är sant eller falskt. Om det är falskt, det betyder att vi kommer att vilja skriva ut någon form av meddelande och avsluta programmet. Vad vi vill göra är att kontrollera returvärdet foo. Om foo returnerar false, då vi vet att vi stött på någon typ av fel och vi måste avsluta vårt program. Ett sätt att göra detta är att ha ett tillstånd där den faktiska funktionen i sig är ditt tillstånd. Säg foo tar i x. Vi kan ha som ett villkor om (foo (x)). I grund och botten innebär att om i slutet av köra foo den returnerar sant, då kan vi göra detta eftersom funktionen måste utvärdera foo För att utvärdera hela tillståndet. Så då det är hur du kan göra något om funktionen returnerar true och är framgångsrik. Men när du är felkontroll, vill du bara sluta om din funktion returnerar false. Vad du kan göra är att lägga bara en == falska eller bara lägga en smäll framför den och då har du if (! foo). I detta organ av detta villkor du skulle ha alla felhantering, så vill, "Kunde inte skapa detta träd" och sedan återvända 1 eller något liknande. Vad som gör, är dock att även om foo återvände falskt - Säg foo returnerar true. Då behöver du inte ringa foo igen. Det är en vanlig missuppfattning. Eftersom det var i ditt tillstånd, det redan utvärderats, så har du redan ett resultat om du använder gör träd eller något liknande eller växt eller plocka eller något. Det har redan detta värde. Det är redan körs. Så det är bra att använda booleska funktioner som villkoret eftersom om du faktiskt utföra kroppen av slingan, den utför funktionen ändå. 

Vår näst sista steget är att skriva meddelandet till filen. När vi bygga Huffman träd, och sedan skriva meddelandet till filen är ganska enkelt. Det är ganska enkelt nu att bara följa 0 och 1. Och så genom konvention vet vi att i en Huffman trädet 0s indikerar kvar och 1s anger rätt. Så då om du läser i bit för bit, varje gång du får en 0 du följa den vänstra grenen, och sedan varje gång du läser i en 1 du kommer att följa den rätta grenen. Och då du kommer att fortsätta tills du träffar ett löv eftersom bladen kommer att vara i slutet av grenarna. Hur kan vi berätta om vi har träffat en löv eller inte? Vi sa det innan. [Eleven] Om pekare är NULL. >> Ja. Vi kan berätta om vi har drabbats ett löv om pekare till både vänster och höger träd är NULL. Perfekt. Vi vet att vi vill läsa i bit för bit i vår Huff fil. Som vi såg tidigare i dump.c, är vad de gjorde de läser i bit för bit in i Huff filen och bara skrivas ut vad dessa bitar var. Vi kommer inte att göra det. Vi kommer att göra något som är lite mer komplicerat. Men vad vi kan göra är att vi kan ta det lite kod som läser in i lite. Här har vi heltalet bit representerar den aktuella biten som vi är på. Detta tar hand om iterera alla bitar i filen tills du träffar i slutet av filen. Baserat på det, då du kommer att vilja ha någon form av iterator att korsa ditt träd. Och sedan baserat på huruvida biten är 0 eller 1, du kommer att vilja antingen flytta den iterator till vänster eller flytta det åt höger ända tills du träffar ett löv, så hela vägen tills den nod som du är på pekar inte på några fler noder. Varför kan vi göra detta med en Huffman-fil, men inte morsekod? För i morsekod finns lite tvetydighet. Vi kan vara som, oh vänta, vi har träffat en bokstav på vägen, så kanske det här är vårt brev, medan om vi fortsatte bara lite längre, då skulle vi ha hit en annan bokstav. Men det kommer inte att hända i Huffman-kodning, så att vi kan lita på att det enda sättet att vi kommer att träffa ett tecken är om det nodens vänstra och högra barn är NULL. 

Slutligen vill vi frigöra alla våra minne. Vi vill både nära den Huff fil som vi har att göra med samt ta bort alla träd i vår skog. Baserat på din implementering, du kommer förmodligen att vilja ringa bort skog istället för att faktiskt gå igenom alla träden själv. Men om du gjort några tillfälliga träd, kommer du vill frigöra det. Du vet att din kod bäst, så du vet vart du fördela minne. Och så om du går in, börja med att även Styrning F'ing för malloc, se när du malloc och se till att du befria allt det men sedan bara gå igenom din kod, förstå var du kan ha allokerat minne. Brukar du kanske bara säga, "I slutet av en fil jag bara tänker ta bort skog på min skog," så i princip klart att minnet, fri att, "Och sedan jag kommer också att avsluta ärendet och sedan mitt program kommer att sluta." Men är det den enda gången som ditt program avslutas? Nej, eftersom det ibland kan ha varit ett misstag som hände. Kanske kunde vi inte öppna en fil eller vi kunde inte göra annat träd eller någon form av fel hände i minnesallokering processen och det återvände NULL. Ett fel inträffade och sedan vi återvände och sluta. Så då du vill vara säker på att en eventuell tid som ditt program kan sluta, du vill frigöra all din minne där. Det är inte bara kommer att vara i slutet av de viktigaste funktionen som du avslutar din kod. Du vill se tillbaka på alla instanser att din kod eventuellt kan återvända i förtid och sedan fri oavsett minne vettigt. Säg att du hade ringt göra skog och det återvände falskt. Så har du förmodligen inte kommer att behöva ta bort din skog eftersom du inte har en skog än. Men vid varje punkt i koden där du kan återvända i förtid du vill vara säker på att du frigör eventuell minne. 

Så när vi har att göra med att frigöra minne och har potentiella läckor, Vi vill inte bara använda vårt omdöme och vår logik men även använda Valgrind att avgöra om vi har befriat alla våra minne korrekt eller ej. Du kan antingen köra Valgrind på Puff och då måste man också ge det rätt antal kommandoradsargument med valgrind. Du kan köra det, men utgången är lite kryptiskt. Vi har fått lite van vid det med Speller, men vi behöver fortfarande lite mer hjälp, så då kör det med några fler flaggor som läckan-check = full, som förmodligen kommer att ge oss lite mer användbar utgången på Valgrind. 

Sedan en annan bra tips när du felsöker är skillnad kommandot. Du kan komma åt den personal genomförande av Huff, köra den på en textfil, och sedan mata den till en binär fil, en binär Huff fil, för att vara specifik. Sen om du kör din egen puff på den binär fil, då helst är din utmatade textfil kommer att vara identiska till den ursprungliga som du gått i. Här Jag använder hth.txt som exempel, och det är en talade om i din spec. Det är bokstavligen bara HTH och sedan en ny rad. Men definitivt gärna och du definitivt uppmuntras att använda längre exempel för din textfil. 

Du kan även ta ett skott på kanske komprimera och sedan dekomprimering några av de filer som du använde i Speller som Krig och fred eller Jane Austen eller något liknande - det skulle vara ganska häftigt - eller Austin Powers, typ att hantera större filer eftersom vi inte skulle komma ner till den om vi använde nästa verktyg här, ls-l. Vi är vana vid ls, som i princip visar alla innehållet i vår nuvarande katalog. Passerar i flaggan-l faktiskt visar storleken på dessa filer. Om du går igenom pset spec, går det faktiskt dig att skapa den binära filen, av huffing det, och du ser att för mycket små filer utrymme kostnaden att komprimera den och översätta all denna information av alla frekvenser och sånt som uppväger den faktiska nyttan att komprimera filen i första hand. Men om du kör det på några längre textfiler, så du kanske se att du börjar få lite nytta att komprimera dessa filer. 

Och slutligen har vi vår gamle vän GDB, som definitivt kommer att komma väl till pass också. 

Har vi några frågor om Huff träd eller processen kanske att göra träden eller några andra frågor om Huff'n Puff? Okej. Jag stannar runt för lite. 

Tack, alla. Detta var Genomgång 6. Och lycka till. 

[CS50.TV]