[Powered by Google Translate] [Walk Through - Probleem Set 6] [Zamyla Chan - Harvard Universiteit] [Hierdie is CS50. - CS50.TV] 

Hallo, almal, en welkom om Walk Through 6: Huff'n Puff. In Huff'n Puff wat ons doen gaan word wat handel met 'n Huffman saamgeperste lêer en dan gepruttel dit terug, so decompressie, sodat ons kan vertaal uit die 0'e en 1s dat die gebruiker stuur ons en sit dit terug in die oorspronklike teks. Pset 6 gaan wees pretty cool want jy gaan om te sien sommige van die gereedskap wat jy gebruik in pset 4 en pset 5 en soort en kombineer hulle in 1 mooi netjiese konsep wanneer jy kom om te dink oor dit. 

Ook, waarskynlik, pset 4 en 5 was die mees uitdagende psets wat ons gehad het om te bied. So van nou af, het ons hierdie 1 meer pset in C, en dan na dat ons op web programmering. So geluk julle om oor die moeilikste skof in CS50. 

Moving vir Huff'n Puff, ons toolbox vir hierdie pset gaan wees Huffman bome, so verstaan ​​van nie net hoe binêre bome werk, maar ook spesifiek Huffman bome, hoe hulle saamgestel. En dan gaan ons 'n baie van die verspreiding-kode te hê in hierdie pset, en ons sal kom om te sien wat werklik sommige van die kode ons dalk nie in staat wees om ten volle te verstaan ​​nog, en so sal die c-lêers., maar dan hul meegaande h lêers. sal ons genoeg begrip wat ons nodig het, sodat ons weet hoe die funksies werk of ten minste wat hulle veronderstel is om te doen - hulle insette en uitsette - selfs al weet ons nie wat gebeur in die swart blokkie of verstaan ​​nie wat gebeur in die swart blokkie in. En dan uiteindelik, soos gewoonlik, het ons te make met 'n nuwe datastrukture, spesifieke tipes van nodes wat verwys na sekere dinge, en so hier met 'n pen en papier nie net vir die ontwerp-proses en wanneer jy probeer om uit te vind hoe jou pset moet werk maar ook tydens ontfouting. Jy kan GDB langs jou pen en papier hê terwyl jy neem af wat die waardes is, waar jou pyle wys, en dinge soos dat. 

Eerste laat ons kyk na Huffman bome. Huffman bome binêre bome, wat beteken dat elke node net het 2 kinders. In Huffman bome die eienskap is dat die mees algemene waardes verteenwoordig deur die minste stukkies. Ons het gesien in die lesing voorbeelde van Morsekode, watter soort van gekonsolideerde sommige letters. As jy probeer om 'n A of 'n E te vertaal, byvoorbeeld, jy wat dikwels vertaling, so in plaas van met die volledige stel van die stukkies te gebruik toegeken vir daardie gewone datatipe jy compress dit af na minder, en dan die letters wat verteenwoordig minder dikwels word verteenwoordig met 'n lang stukkies want jy kan bekostig dat wanneer jy weeg die frekwensies wat daardie letters verskyn. Ons het dieselfde idee hier in Huffman bome waar ons 'n ketting, 'n soort van die pad om te kry om die bepaalde karakters. En dan die karakters wat die meeste frekwensie gaan word verteenwoordig met die minste stukkies. 

Die manier waarop jy bou 'n Huffman boom is deur die plasing van al die karakters wat verskyn in die teks en die berekening van die frekwensie, hoe dikwels hulle verskyn. Dit kan óf 'n telling van hoeveel keer die letters verskyn of dalk 'n persentasie uit van al die karakters hoeveel elkeen verskyn. En so wat jy doen, is wanneer jy al van daardie gekarteer uit, dan moet jy kyk vir die 2 laagste frekwensies en dan saam met hulle as broers en susters Waar is dan die ouer node het 'n frekwensie wat is die som van sy 2 kinders. En dan kan jy deur konvensie sê dat die linker node, jy volg dat deur die 0 tak, en dan die regterkantste node is die 1-tak. Soos ons gesien het in Morsekode, die een Gotcha was dat as jy net 'n beep en die beep dit was dubbelsinnig. Dit kan óf 1 letter of dit kan 'n reeks van 2 letters. En wat Huffman bome is gevolg deur die aard van die karakters of ons finale werklike karakters synde die laaste nodes op die tak - ons verwys na as blare - uit hoofde van daardie kan daar nie enige dubbelsinnigheid in terme van watter letter jy probeer om te enkodeer met die reeks van bisse want nêrens langs die bisse wat 1 letter sal jy nog 'n hele brief teëkom, en daar sal nie enige verwarring daar. Maar ons gaan in voorbeelde wat julle eintlik kan sien wat in plaas van ons net wat jy vertel dat dit is waar. 

Kom ons kyk na 'n eenvoudige voorbeeld van 'n Huffman boom. Ek het hier 'n string wat is 12 karakters lank wees. Ek het 4 As, 6 Bs, en 2 Cs. My eerste stap sou wees om te tel. Hoeveel keer het 'n verskyn? Dit blyk 4 keer in die tou. B verskyn 6 keer, en C verskyn 2 keer. Natuurlik, ek gaan om te sê Ek B is die gebruik van die meeste, Ek wil so om B te stel met die minste aantal bisse, die minste aantal 0'e en 1s. En dan is ek ook gaan om te verwag dat C die meeste bedrag van 0'e en 1s sowel vereis. Eerste wat ek hier het ek hulle in stygende orde in terme van frekwensie. Ons sien dat die C en die A, wat is ons 2 laagste frekwensies. Ons skep 'n ouer node, en daardie ouer node het nie 'n brief wat verband hou met dit, maar dit het 'n frekwensie wat is die som. Die som word 2 + 4, wat is 6. Dan volg ons die linker-tak. As ons op daardie 6 node, dan sou ons volg 0 om te kry tot C en dan 1 te kry A. So nou het ons 2 nodes. Ons het die waarde 6 en dan het ons ook 'n ander node met die waarde 6. En so het die 2 is nie net die 2 laagste, maar ook net die 2 wat oorgebly, sodat ons saam met dié deur 'n ander ouer, met die som 12. So hier is ons het ons Huffman boom waar om te kry tot B, sou dit net die bietjie 1 en dan te kry om 'ons wil hê dat 01 en dan C met 00. So hier sien ons dat ons basies hierdie karakters is verteenwoordig met 1 of 2 bisse waar die B, soos voorspel, het die minste. En dan het ons verwag het C die meeste te hê, maar omdat dit so 'n klein Huffman boom, dan is die A word ook verteenwoordig deur 2 stukkies in teenstelling tot iewers in die middel. 

Net om te gaan oor 'n ander eenvoudige voorbeeld van die Huffman boom, sê jy het die string "Hello." Wat jy doen is die eerste wat jy sou sê hoeveel keer het H verskyn in hierdie? H verskyn een en dan e verskyn een keer en dan het ons l verskyn twee keer en o verskyn een keer. En so is daar dan verwag ons watter letter om verteenwoordig te word deur die minste aantal bisse? [Student] l. >> L. Ja. l is reg. Ons verwag dat l om verteenwoordig te word deur die minste aantal bisse want l is die meeste gebruik word in die tou "Hallo." Wat ek nou doen is trek uit hierdie nodes. Ek het 1, wat is H, en dan ander 1, wat e, en dan 'n 1, wat is o - ek nou om dit in orde - en dan 2, wat l. Dan sê ek die manier wat ek gaan bou, 'n Huffman boom is die 2 nodes met die minste frekwensies te vind en maak hulle broers en susters deur die skep van 'n ouer node. Hier het ons het 3 nodusse met die laagste frekwensie. Hulle is almal 1. So hier is ons kies watter een gaan ons eerste skakel. Kom ons sê ek kies die H en die e. Die som van 1 + 1 is 2, maar hierdie node het nie 'n brief wat verband hou met dit. Dit hou net die waarde. Nou moet ons kyk na die volgende 2 laagste frekwensies. Dit is 2 en 1. Dit kan een van daardie 2 wees, maar ek gaan hierdie een te kies. Die som 3. En dan uiteindelik, ek het net 2 links, so dan is dit word 5. Dan is hier, soos verwag, as ek in die kodering vir daardie vul, 1s die regte tak en 0'e altyd die linker een. Dan het ons l verteenwoordig deur net 1 bietjie en dan die o 2 en dan die e deur 2 en dan val die H 3 stukkies. So kan jy hierdie boodskap oordra "Hallo" eerder as om werklik die gebruik van die karakters deur net 0'e en 1s. Onthou egter dat in verskeie gevalle moes ons bande met ons frekwensie. Ons kan óf die H en die o eerste miskien aangesluit het. Of dan later toe ons die l verteenwoordig deur 2 sowel as die by een verteenwoordig deur 2, kan ons óf een gekoppel. 

En so wanneer jy die 0'e en 1s, wat eintlik nie waarborg dat die ontvanger ten volle kan lees jou boodskap regs af die vlermuis omdat hulle dalk nie weet watter besluit wat jy gemaak het. So wanneer ons te doen het met Huffman kompressie, een of ander manier het ons die ontvanger van ons boodskap te vertel hoe ons besluit - Hulle moet 'n soort van ekstra inligting om te weet in Benewens die saamgeperste boodskap. Wat hulle nodig het om te verstaan ​​wat die boom eintlik lyk soos, hoe ons eintlik het dié besluite hê. 

Hier het ons net voorbeelde wat gebaseer is op die werklike telling doen, maar soms kan jy ook 'n Huffman boom gebaseer op die frekwensie waarteen letters verskyn, en dit is die presiese dieselfde proses. Hier is ek die uitdrukking van dit in terme van persentasies of 'n breuk, en so hier is die presies dieselfde ding. Ek vind die 2 laagste, vat hulle die volgende 2 laagste, vat hulle, totdat ek het 'n volledige boom. Selfs al kan ons dit doen een manier, wanneer ons te doen het met persentasies, dit beteken dat ons dinge is die verdeling en die hantering van desimale of dryf eerder As ons dink oor data strukture van 'n kop. Wat weet ons oor die dryf? Wat is 'n algemene probleem wanneer ons te doen het met dryf? [Student] vaag rekenkunde. >> Ja. Onakkuraatheid. As gevolg van floating point onakkuraatheid, vir hierdie pset so dat ons seker maak dat ons nie enige waardes verloor, dan is ons eintlik gaan om te word wat met die telling. So as jy was om te dink van 'n Huffman node, as jy kyk terug na die struktuur, as jy kyk na die groen, dit het 'n frekwensie wat verband hou met dit sowel as dit dui op 'n knoop aan die linkerkant asook 'n knoop aan sy regterkant. En dan die rooies is daar ook 'n karakter wat verband hou met hulle. Ons gaan nie afsonderlike kinders te maak vir die ouers en dan die finale nodes, wat ons verwys na as blare, maar eerder dié sal net NULL waardes. Vir elke node sal ons 'n karakter, die simbool dat node verteenwoordig, dan 'n frekwensie sowel as 'n wyser na die linkerkant kind sowel as sy reg kind. Die blare, wat heel aan die onderkant, sal ook node pointers aan hul linkerkant en aan hulle hul reg, maar sedert daardie waardes word nie verwys na die werklike nodes, wat hul waarde sou wees? >> [Student] null. >> Null. Presies. Hier is 'n voorbeeld van hoe jy kan verteenwoordig in die frekwensie dryf, maar ons gaan word om dit te hanteer met heelgetalle, so al wat ek gedoen het, is verander die datatipe daar. 

Kom ons gaan op 'n bietjie meer van 'n komplekse voorbeeld. Maar nou dat ons die eenvoudiges gedoen het nie, dis net dieselfde proses. Jy kry die 2 laagste frekwensies, som die frekwensies en dit is die nuwe frekwensie van jou voorgangernode, wat dui dan aan die linkerkant met die 0-tak en die reg met die 1-tak. As ons die string "Dit is cs50," dan moet ons tel hoeveel keer is T genoem, h genoem, i, s, c, 5, 0. Dan wat ek hier gedoen het, is met die rooi nodes Ek het net geplant, Ek het gesê ek gaan hierdie karakters om uiteindelik aan die onderkant van my boom. Diegene gaan wees al die blare. Dan wat ek gedoen het, is ek hulle deur die frekwensie in stygende volgorde gesorteer, en dit is eintlik die manier waarop die pset kode doen dit is dit sorteer dit deur die frekwensie en dan alfabeties. So het die syfers vir die eerste keer en dan alfabeties volgens die frekwensie. Dan wat ek sou doen, is ek die 2 laagste sou vind. Dit is 0 en 5. Ek sou vat, en dit is 2. Dan sou ek voortgaan, vind die volgende 2 laagste. Dit is die twee 1s, en dan dié geword 2 as goed. Nou weet ek dat my volgende stap gaan word by die laagste getal, wat is die T 1, en dan die keuse van een van die nodusse wat 2 as die frekwensie. So hier is ons het 3 opsies. Wat ek gaan om te doen vir die skyfie is visueel herrangskik hulle net vir jou sodat jy kan sien hoe ek dit is die opbou. Wat die kode en jou verspreiding kode gaan doen sou aansluit by die T- met die 0 en 5 node. So dan dat die somme tot 3, en dan sal ons voortgaan om die proses. Die 2 en die 2 nou is die laagste, so dan daardie som tot 4. Almal volg so ver? Okay. Daarna het ons die 3 en die 3 wat aangespreek moet word opgetel, so ek is net skakel dit so dat jy kan visueel so sien dat dit nie te morsige. Dan het ons 'n 6, en dan is ons finale stap is nou dat ons slegs 2 nodes ons som die wortel van die boom, wat 10 te maak. En die getal 10 maak sin omdat elke node verteenwoordig, hul waarde, die frekwensie, was hoeveel keer hulle in die tou verskyn, en dan het ons 5 karakters in ons string, so dit maak sin. As ons kyk hoe ons dit sou eintlik enkodeer, soos verwag, die ek en die s, en wat die meeste word verteenwoordig deur die minste aantal bisse. 

Wees versigtig hier. In Huffman bome van die geval saak eintlik. 'N hoofletter S is anders as 'n kleinletter s. As ons gehad het "Dit is CS50" met hoofletters, dan die klein letters is net twee keer verskyn, 'n knoop met 2 as sy waarde sou wees, en dan hoofletters S sal slegs een keer. So dan is jou boom strukture sou verander omdat jy eintlik 'n ekstra blaar hier. Maar die som sou nog 10. Dit is wat ons eintlik gaan om die roeping van die checksum, die toevoeging van al die tellings. 

Nou dat ons Huffman bome het gedek, kan ons duik in Huff'n Puff, die pset. Ons gaan om te begin met 'n gedeelte van die vrae, en dit gaan te kry wat jy gewoond met binêre bome en hoe om te werk om dat: teken nodes, die skep van jou eie typedef struct vir 'n node, en sien hoe jy kan plaas in 'n binêre boom, een wat gesorteer, kameelkoei dit, en dinge soos dat. Daardie kennis is beslis gaan om jou te help wanneer jy duik in die Huff'n Puff gedeelte van die pset. In die standaard uitgawe van die pset, jou taak is om Puff te implementeer, en in die hacker weergawe is jou taak is Huff te implementeer. Wat Huff doen, is wat dit neem om teks en dan is dit vertaal dit in die 0'e en 1s, sodat die proses wat ons hierbo gedoen het waar ons die frekwensies getel en dan het die boom en dan sê: "Hoe kry ek 'T?" T word verteenwoordig deur 100, dinge soos dat, en dan Huff sal neem om die teks en dan uitset dat binêre. Maar ook omdat ons weet dat ons wil ons ontvanger van die boodskap toe te laat die presiese dieselfde boom te herskep, sluit dit ook inligting oor die frekwensie tel. Dan met Puff ons gegee is om 'n binêre lêer van 0'e en 1s en ook die inligting oor die frekwensies. Ons vertaal al van daardie 0'e en 1s terug in die oorspronklike boodskap wat was, sodat ons decompressie. As jy die standaard uitgawe doen, hoef jy nie te implementeer Huff, so dan kan jy net gebruik maak van die personeel implementering van Huff. Daar is instruksies oor hoe om dit te doen in die spec. Jy kan die personeel implementering van Huff loop op 'n sekere teks lêer en gebruik dan dat die uitset as jou insette Puff. 

Soos ek voorheen genoem het, ons het 'n baie van verspreiding-kode vir hierdie een. Ek gaan om te begin gaan deur dit. Ek gaan die meeste van die tyd te spandeer op die h lêers want in die C-lêers., want ons het die h en dat ons met die prototipes van die funksies, ons nie ten volle nie nodig om presies te verstaan ​​- As jy nie verstaan ​​wat gaan aan in die C-lêers., Doen dan nie te veel bekommerd wees, maar beslis probeer om 'n blik te neem, want dit kan 'n paar wenke gee en dit is nuttig om gewoond te raak aan die lees van ander mense se kode. 

Looking by huffile.h, in die kommentaar dit verklaar 'n laag van abstraksie vir Huffman-gekodeerde lêers. As ons gaan af, sien ons dat daar 'n maksimum van 256 simbole wat ons codes dalk nodig vir. Dit sluit al die letters van die alfabet - hoofletters en klein - en dan simbole en nommers, ens. Dan is hier ons het 'n magie nommer die identifisering van 'n Huffman-gekodeerde lêer. Binne 'n Huffman-kode hulle gaan 'n sekere magic number wat verband hou met die kop. Dit kan lyk soos net 'n ewekansige magic number, maar as jy eintlik is dit vertaal in ASCII, dan is dit spel eintlik uit HUFF. Hier het ons het 'n struct vir 'n Huffman-geënkodeerde lêer. Daar is al van hierdie eienskappe wat verband hou met 'n Huff-lêer. Dan af hier het ons die bladsyboskrif ('header') vir 'n Huff-lêer, sodat ons noem dit Huffeader in plaas van die toevoeging van die ekstra h, want dit klink in elk geval dieselfde. Oulik. Ons het 'n magie nommer wat verband hou met dit. As dit is 'n werklike Huff lêer, gaan dit na die nommer bo, hierdie magie. En dan sal dit 'n skikking. Dus, vir elke simbool, waarvan daar 256, dit gaan om te lys wat die frekwensie van daardie simbole binne die Huff-lêer. En dan uiteindelik, ons het 'n checksum vir die frekwensies, wat moet die som van die frekwensies. So dit is wat 'n Huffeader is. Dan het ons het 'n paar funksies wat die standaard van die volgende bietjie in die Huff-lêer sowel as skryf 'n bietjie aan die Huff lêer en dan hierdie funksie hier, hfclose Dit sluit eintlik die Huff lêer. Voor, het ons te make met reguit net fclose, maar wanneer jy 'n Huff lêer, in plaas van fclosing dit wat jy eintlik gaan doen, is hfclose en hfopen dit. Dit is spesifieke funksies aan die Huff lêers wat ons gaan die hantering van. Dan is hier ons lees in die kop en skryf dan die kop. 

Net deur die lees van die h-lêer, kan ons soort van 'n gevoel kry van wat 'n Huff lêer kan wees, watter eienskappe dit het, sonder om eintlik gaan in die huffile.c, wat, as ons duik in, gaan 'n bietjie meer kompleks. Dit het al van die lêer I / O hier te doen met verwysings. Hier sien ons dat wanneer ons noem hfread, byvoorbeeld, is dit nog steeds doen het met fread. Ons is nie om ontslae te raak van daardie werksaamhede in sy geheel, maar ons stuur wat geneem moet word versorging van binne die Huff lêer in plaas van die doen dit self. Jy kan voel vry om te scan deur as jy nuuskierig en gaan en skil die laag 'n bietjie terug. 

Die volgende lêer dat ons gaan om te kyk na is tree.h. Voor in die Walk Through skyfies het ons gesê ons verwag 'n Huffman node en ons het 'n typedef struct node. Ons verwag dat dit 'n simbool, 'n frekwensie, en dan 2 node sterre. In hierdie geval wat ons doen, is dit in wese dieselfde is behalwe in plaas van node het ons gaan om te bel hulle bome. Ons het 'n funksie dat wanneer jy noem maak boom dit terug jy 'n boom wyser. Terug na Speller, wanneer jy besig was om 'n nuwe node jy sê node * nuwe woord = malloc (sizeof) en dinge soos dat. Basies, is mktree gaan doen met dit vir jou. Net so, wanneer jy wil om 'n boom te verwyder, sodat legen die boom wanneer jy klaar is met dit, in plaas van uitdruklik roep op daardie, jy eintlik net gaan om die funksie te rmtree gebruik waar jy in die wyser na daardie boom en dan tree.c sal sorg dit vir jou. 

Ons sien in tree.c. Ons verwag dieselfde funksies behalwe die implementering sowel sien. As wat ons verwag het, wanneer jy bel mktree dit mallocs die grootte van 'n boom in 'n wyser, initialisatie van al die waardes aan die NULL waarde, so 0s of NULLs, en terugstuur dan die wyser na daardie boom wat jy het nou net malloc'd aan jou. Hier wanneer jy noem verwyder boom dit maak eers seker dat jy dubbel is nie bevry. Dit maak seker dat jy eintlik 'n boom wat jy wil verwyder. Hier, want 'n boom sluit ook sy kinders, Wat dit beteken is dit noem rekursief verwyder boom aan die linkerkant node van die boom sowel as die regte node. Voordat dit bevry die ouer, die kinders wat dit nodig het om so goed te bevry. Ouer is ook uitruilbaar met wortel. Die eerste keer ooit ouer, so soos die groot-groot-groot-groot-oupa of ouma boom, het ons eers af te bevry die vlakke vir die eerste keer. So deurkruis na die bodem, gratis diegene, en dan terug te kom, gratis diegene, ens. So wat se boom. 

Nou kyk ons ​​in die bos. Bos is waar jy plaas al jou Huffman bome. Dit sê dat ons gaan om iets te hê wat 'n plot genoem Dit bevat 'n wyser na 'n boom sowel as 'n wyser na 'n plot genoem volgende. Watter struktuur doen hierdie soort van lyk? Dit soort van sê dit daar. Reg oor hier. 'N geskakelde lys. Sien ons dat wanneer ons 'n plot dit is soos 'n geskakelde lys van persele. 'N bos is gedefinieer as 'n geskakelde lys van erwe, en so die struktuur van die bos is ons net gaan om 'n wyser te hê aan ons eerste plot en dat die plot het 'n boom in dit of eerder aan 'n boom en wys dan na die volgende plot, so aan en so voort. 'N bos te maak, noem ons mkforest. Dan het ons 'n paar mooi nuttige funksies hier. Ons het kies waar jy in 'n bos en dan die terugkeer waarde is 'n Tree * 'n wyser na 'n boom. Wat pick sal doen, is dit gaan in die bos dat jy verwys na verwyder dan 'n boom met die laagste frekwensie van daardie bos en dan gee jy die wyser na daardie boom. Sodra jy 'n beroep kies, sal die boom nie bestaan ​​in die bos nie, maar die opbrengs waarde is die wyser na daardie boom. Dan moet jy plant. Met dien verstande dat jy in 'n wyser na 'n boom wat 'n nie-0 frekwensie, watter plant sal doen, sal dit die bos, neem die boom, en plant wat binnekant van die bos boom. Hier het ons 'rmforest. Similar boom te verwyder, wat basies almal van ons bome bevry vir ons, verwyder bos sal gratis alles vervat in daardie bos. 

As ons kyk na forest.c, sal ons verwag om ten minste 1 rmtree opdrag om te sien daar, omdat gratis geheue in die bos as 'n bos bome in, dan uiteindelik sal jy gaan hê om die bome te verwyder. As ons kyk na forest.c, ons het ons mkforest, wat soos ons verwag. Ons malloc dinge. Ons inisialiseer die eerste plot in die bos as NULL, omdat dit leeg is om mee te begin, dan sien ons pluk, wat gee die boom met die laagste gewig, die laagste frekwensie, en dan ontslae raak van daardie spesifieke node dat punte aan daardie boom en die volgende een, so dit neem dat van die geskakelde lys van die bos. En dan is hier ons het 'n plant, wat voeg 'n boom in die geskakelde lys. Wat bos is dit mooi hou dit gesorteer vir ons. En dan uiteindelik, ons het rmforest en, soos verwag, het ons rmtree genoem daar. 

Op soek na die verspreiding kode so ver, huffile.c was waarskynlik verreweg die moeilikste om te verstaan, terwyl die ander lêers self was redelik maklik om te volg. Met ons kennis van wysers en geskakelde lyste en sodanige ons in staat was om baie goed volg. Maar al wat ons nodig het om werklik te maak seker dat ons ten volle verstaan ​​die h-lêers. want jy moet die roeping van daardie werksaamhede, wat handel met daardie opgawe waardes, so maak seker dat jy ten volle verstaan ​​watter stappe uitgevoer gaan word wanneer jy bel een van daardie funksies. Maar eintlik begrip binnekant van dit is nie heeltemal nodig nie, want ons het daardie h lêers. Ons het 2 meer lêers links in ons verspreiding kode. 

Kom ons kyk na dump. Stort deur sy kommentaar hier, neem 'n Huffman-saamgeperste lêer en dan vertaal en vullishope van die inhoud uit. Hier sien ons dat dit hfopen opbelt. Dit is 'n soort van die spieël * insette FILE = fopen, en dan is jy in die inligting. Dit is byna identies, behalwe in plaas van 'n lêer * jy verby in 'n Huffile; in plaas van fopen jy verby in hfopen. Hier lees ons in die kop eerste, wat is 'n soort van soortgelyk aan hoe ons lees in die kop vir 'n bitmap-lêer. Wat ons hier doen, is om te kyk of die header information bevat die regte magie getal wat aandui dat dit 'n werklike Huff lêer, dan sal al hierdie kontrole om seker te maak dat die lêer wat ons oop is 'n werklike huffed lêer of nie. Wat dit beteken is dit uitgange die frekwensies van al die simbole wat ons kan sien binne 'n terminaal in 'n grafiese tafel. Hierdie gedeelte gaan nuttig te wees. Dit het 'n bietjie en lees bietjie vir bietjie in die veranderlike bietjie en dan druk dit uit. So as ek dump te roep op hth.bin, wat die gevolg is van 'n lêer te hijgen met behulp van die personeel oplossing, sou ek hierdie. Dit is printer al hierdie karakters en dan om die frekwensie waarteen hulle verskyn. As ons kyk, die meeste van hulle is 0e behalwe vir hierdie: H, wat twee keer voorkom, en dan T, wat verskyn een keer. En dan hier het ons die werklike boodskap in 0'e en 1s. As ons kyk by die hth.txt, wat vermoedelik die oorspronklike boodskap wat huffed, ons verwag om te sien sommige Hs en Ts daar. Spesifiek, ons verwag net 1 T om te sien en 2 Hs. Hier is ons in hth.txt. Dit het inderdaad HTH. Ingesluit in daar, maar ons kan dit nie sien nie, is 'n newline karakter. Die Huff lêer hth.bin is ook die enkodering van die newline karakter as goed. Hier omdat ons weet dat die orde is HTH en dan newline, kan ons sien dat waarskynlik die H is verteenwoordig deur net 'n enkele 1 en dan die T is waarskynlik 01 en dan die volgende H 1 asook en dan het ons 'n newline aangedui deur twee 0s. Cool. 

En dan uiteindelik, omdat ons te doen het met verskeie c en h lêers, ons gaan 'n redelik komplekse argument te hê aan die vertaler, en so hier het ons 'n makefile wat dump maak vir jou. Maar eintlik, jy het om te gaan oor die maak van jou eie puff.c lêer. Die makefile eintlik nie hanteer vir jou puff.c te maak. Ons verlaat dat tot jy die makefile te wysig. Wanneer jy 'n opdrag soos alles maak, byvoorbeeld, sal dit maak almal van hulle vir jou. Voel vry om te kyk na die voorbeelde van makefile uit die verlede pset sowel as van hierdie een af ​​om te sien hoe jy dalk in staat wees om jou Puff lêer te maak deur die redigering van hierdie makefile. Dit is omtrent dit vir ons verspreiding kode. 

Sodra ons gekry het deur daardie, dan is hier is net 'n herinnering van hoe ons gaan doen met die Huffman nodes. Ons gaan nie bel hulle nodes nie, ons gaan om te bel hulle bome waar ons gaan te word wat hul simbool met 'n char, hulle frekwensie, die aantal voorvalle, met 'n heelgetal. Wat ons gebruik, want dit is meer akkuraat is as 'n float. En dan het ons nog 'n wyser na die linker kind sowel as die regte kind. 'N bos, soos ons gesien het, is net 'n geskakelde lys van bome. Uiteindelik, wanneer ons die opbou van ons Huff lêer, ons wil ons bos net 1 boom te bevat - 1 boom, 1 wortel met verskeie kinders. Vroeër op wanneer ons net om ons Huffman bome, ons begin deur al die nodusse op ons skerm en gesê ons gaan hierdie nodes te hê, Uiteindelik het hulle gaan om die blare te wees, en dit is hul simbool, dit is hulle frekwensie. In ons bos as ons net 3 letters het, dis 'n bos van 3 bome. En dan as ons gaan, wanneer ons die eerste ouer bygevoeg, ons het 'n bos van 2 bome. Ons verwyder 2 van die kinders uit die bos en dan vervang dit met 'n ouer node wat die 2 nodes as kinders gehad het. En dan uiteindelik, ons laaste stap met die maak van ons 'n voorbeeld met die As, Bs, en Cs sou wees om die finale ouer te maak, en so dan sou dit bring ons totale telling van die bome in die bos tot 1. Nie almal sien hoe jy begin met verskeie bome in jou bos en eindig met 1? Okay. Cool. 

Wat moet ons doen om vir Puff? Wat ons nodig het om te doen is om seker te maak dat, soos altyd, hulle gee ons die regte tipe van inset sodat ons kan eintlik loop die program. In hierdie geval is hulle gaan om te gee ons na hul eerste command-line argument 2 meer: ​​die lêer wat ons wil decomprimeren en die uitset van die gedecomprimeerd lêer. Maar wanneer ons maak seker dat hulle slaag ons in die regte hoeveelheid van waardes, ons wil om te verseker dat die inset is 'n Huff lêer of nie. En dan wanneer ons waarborg dat dit is 'n Huff lêer, dan wil ons ons boom te bou, die opbou van die boom van so 'n aard dat dit ooreenstem met die boom wat die persoon wat die boodskap gestuur het gebou. Dan na ons bou die boom, dan kan ons hanteer die 0'e en 1s dat hulle geslaag het, volg wat langs ons boom omdat dit identies is, en skryf dan die boodskap uit, interpreteer die stukkies terug in die karakters. En dan aan die einde, want ons handel met wysers hier, ons wil hê om seker te maak dat ons nie enige geheue lekkasies en dat ons alles. 

Verseker korrekte gebruik is ou hoed vir ons deur die nou. Ons neem in 'n inset, wat gaan die naam van die lêer om te puff, en dan het ons 'n uitset spesifiseer, sodat die naam van die lêer vir die gepofte produksie, wat sal die tekslêer wees. Dit is gebruik. En nou is ons wil om te verseker dat die insette huffed of nie. Dink terug, was daar iets in die verspreiding-kode wat ons kan help met 'n begrip of 'n lêer huffed of nie? Daar is inligting in huffile.c oor die Huffeader. Ons weet dat elke Huff-lêer het 'n Huffeader wat daarmee geassosieer word met 'n magie nommer sowel as 'n verskeidenheid van die frekwensies vir elke simbool sowel as 'n checksum. Ons weet dat, maar ons het ook 'n blik op dump.c, waarin dit lees in 'n Huff-lêer. En so het dit te doen, dit het om te kyk of dit regtig is huffed of nie. So miskien kan ons gebruik as 'n struktuur vir ons puff.c. dump.c Terug na pset 4 toe ons die lêer copy.c wat gekopieer in RGB triples en ons verduidelik dat vir detective verhaal en Resize, insgelyks, is net wat jy kan doen voer die opdrag soos cp dump.c puff.c en gebruik sommige van die kode daar. , Is dit egter nie so eenvoudig te wees van 'n proses vir die vertaling jou dump.c in puff.c, maar ten minste is dit gee jou iewers te begin oor hoe om te verseker dat die insette is eintlik huffed of nie sowel as 'n paar ander dinge. Ons het verseker behoorlike gebruik en verseker dat die insette huffed. Elke keer wat ons gedoen het dat ons behoorlike foutopsporing gedoen het, so terugkeer en ophou van die funksie as sommige versuim plaasvind, as daar 'n probleem is. 

Nou wat ons wil doen is om die bou van die werklike boom. As ons kyk in die Bos, is daar 2 belangrikste funksies dat ons gaan om te wil om 'n baie vertroud is met. Daar is die Boole-funksie plant dat plante 'n nie-0 frekwensie boom in ons bos. En so is daar jy slaag in 'n wyser na 'n bos en 'n wyser na 'n boom. Vinnige vraag: Hoeveel woude sal jy hê wanneer jy die bou van 'n Huffman boom? Ons bos is soos ons doek, reg? So gaan ons net 1 bos te hê, maar ons gaan verskeie bome te hê. Dus, voordat jy plant noem, is jy waarskynlik gaan om te wil jou bos te maak. Daar is 'n opdrag dat as jy kyk na forest.h oor hoe jy kan 'n bos maak. Jy kan 'n boom plant. Ons weet hoe om dit te doen. En dan kan jy ook kies 'n boom uit die bos, die verwydering van 'n boom met die laagste gewig en gee jou die wyser na daardie. Dink terug aan toe ons besig was om die voorbeelde wat onsself, wanneer ons dit te teken, het ons eenvoudig net die skakels bygevoeg. Maar hier in plaas van net die toevoeging van die skakels, dink dit meer as jy 2 van daardie nodes is die verwydering en dan dit te vervang deur 'n ander een. Uit te druk in terme van die pluk en te plant, jy pluk 2 bome en dan ander boom te plant wat die 2 bome wat jy opgetel het as kinders. Huffman se boom op te bou, kan jy lees in die simbole en frekwensies ten einde omdat die Huffeader gee wat aan u, gee jou 'n verskeidenheid van die frekwensies. Sodat jy kan gaan voort en ignoreer maar net enigiets met die 0 want ons wil nie 256 blare aan die einde van dit. Ons wil net die aantal blare wat karakters wat werklik gebruik word in die lêer. Jy kan lees in die simbole, en elk van die simbole wat nie-0 frekwensies, dié gaan wees bome. Wat jy kan doen, is elke keer as jy lees in 'n nie-0 frekwensie simbool, jy kan plant daardie boom in die bos. Sodra jy plant die bome in die bos, kan jy saam met die bome as broers en susters, so terug te gaan na plant en pluk waar jy kies 2 en dan plant 1, waar dat die 1 wat jy plant is die ouer van die 2 kinders wat jy opgetel het. So dan is jou eindresultaat is gaan na 'n enkele boom in jou bos te wees. Dit is hoe jy jou boom te bou. 

Daar is 'n paar dinge wat kon verkeerd gaan hier omdat ons te doen het met die maak van nuwe bome en die hantering met wenke en dinge soos dat. Voordat wanneer ons te doen het met pointers, wanneer ons malloc'd ons wou om seker te maak dat dit nie terug vir ons 'n NULL pointer waarde. So op verskeie stappe in hierdie proses is daar gaan wees verskeie gevalle waar jou program kan misluk. Wat jy wil doen, is wat jy wil om seker te maak dat jy die foute hanteer, en in die spec dit sê hulle om grasieus te hanteer, so graag 'n boodskap aan die gebruiker druk vertel hulle waarom die program het om op te hou en dan stop dit dadelik. Hierdie fout hantering om te doen, onthou dat jy dit wil hê om seker te maak elke keer dat daar 'n mislukking te wees. Elke keer wat jy maak 'n nuwe pointer jy wil om seker te maak dat suksesvolle. Voor wat ons gebruik om te doen, is om 'n nuwe wyser en malloc dit maak, en dan sou ons kontroleer of dat die wyser is NULL. So daar gaan 'n paar gevalle waar jy kan net dit doen, maar soms is jy eintlik die roeping van 'n funksie en binne daardie funksie, wat is die een wat die mallocing doen. In daardie geval, as ons terugkyk na sommige van die funksies in die kode, sommige van hulle is Boole-funksies. In die abstrakte geval as ons 'n Boole-funksie genoem foo, basies, kan ons aanneem dat benewens om te doen alles wat foo doen, want dit is 'n Boole-funksie, is dit terug waar of onwaar - ware indien suksesvol, valse indien nie. So ons wil om te kontroleer of die terugkeer waarde van foo is waar of onwaar is. As dit vals is, dit beteken dat ons gaan om te wil 'n soort van 'n boodskap te druk en dan sluit die program. Wat ons wil doen, is kyk na die terugkeer waarde van cat. As foo terugkeer vals is, dan weet ons dat ons 'n soort van fout teëgekom en ons moet ons program om op te hou. 'N manier om dit te doen is 'n toestand waar die werklike funksie self is jou toestand. Sê foo neem in x. Ons kan as 'n voorwaarde as (foo (x)). Basies, wat beteken dat aan die einde van die uitvoering van foo dit terug waar, dan kan ons doen dit omdat die funksie het foo te evalueer ten einde die hele toestand te evalueer. So dan is dit hoe jy iets kan doen indien die funksie gee waar en suksesvol is. Maar wanneer jy foutopsporing, jy wil net om op te hou as jou funksie gee vals. Wat jy kan doen is net voeg 'n == vals of voeg net 'n slag in die voorkant van dit en dan moet jy if (! foo). Binne daardie liggaam van daardie toestand wat jy wil hê van die fout hantering, so wil hê, "Kon nie hierdie boom" en dan terug 1 of iets soos dit. Wat dit doen, al is, is dat selfs al foo teruggekeer valse - Sê foo terugkeer ware. Dan hoef jy nie foo weer bel. Dit is 'n algemene wanopvatting. Want dit was in jou toestand, dit reeds geëvalueer, sodat jy het reeds die resultaat as jy gebruik maak boom of iets soos dit of plant of pick of iets. Dit het reeds daardie waarde. Dit is reeds uitgevoer. So dit is nuttig Boole-funksies te gebruik as die toestand want of jy nie eintlik die liggaam van die lus uitvoer, Dit voer die funksie in elk geval. 

Ons tweede laaste stap is om die boodskap te skryf na die lêer. Sodra ons die bou van die Huffman boom, dan skryf die boodskap na die lêer is redelik eenvoudig. Dit is redelik eenvoudig nou net volg die 0'e en 1s. En so deur konvensie ons weet dat die 0'e dui in 'n Huffman boom links en die 1s dui reg. Daarom dan, as jy lees bietjie vir bietjie, elke keer dat jy 'n 0 jy volg die linker-tak, en dan elke keer wat jy lees in 'n 1 jy gaan die regte tak te volg. En dan is jy gaan om voort te gaan totdat jy getref 'n blaar omdat die blare gaan word aan die einde van die takke. Hoe kan ons vertel of ons het 'n blaar of nie getref? Ons het gesê dit voor. [Student] As die verwysings is NULL. >> Ja. Ons kan sê as ons 'n blaar getref het as die verwysings na beide die linker en regter bome is NULL. Perfect. Ons weet wat ons wil lees bietjie vir bietjie in ons Huff lêer. Soos ons gesien het voor in dump.c, wat hulle gedoen het, is hulle lees bietjie vir bietjie in die Huff-lêer en net gedruk wat daardie stukkies was. Ons is nie van plan om dit te doen. Ons gaan te wees om iets te doen wat 'n bietjie meer kompleks is. Maar wat ons kan doen is wat ons kan neem dat die bietjie van die kode wat in die stuk lees. Hier het ons die integer bietjie wat die huidige bietjie dat ons op. Dit sorg iterating al die stukkies in die lêer totdat jy getref die einde van die lêer. Gebaseer op dat, dan is jy gaan om te wil 'n soort van Iterator jou boom te verken. En dan gebaseer op of die bietjie 0 of 1, jy gaan hê om óf dat Iterator skuif na links of na regs beweeg al die pad tot jy 'n blaar getref, sodat al die pad tot op daardie node dat jy op nie wys nie meer nodes. Hoekom kan ons dit doen met 'n Huffman lêer, maar nie Morsekode? Want in Morsekode is daar is 'n bietjie van dubbelsinnigheid. Ons kon wees, oh wag, het ons 'n letter langs die pad getref het, so miskien is dit is ons brief, terwyl as ons voortgegaan om net 'n bietjie meer, dan sou ons getref het 'n ander brief. Maar dit is nie gaan gebeur in Huffman kodering, sodat ons kan verseker wees dat die enigste manier waarop ons gaan om 'n karakter te tref is indien daardie node se links en regs kinders NULL. 

Ten slotte, ons wil al ons geheue te bevry. Ons wil aan beide naby die Huff lêer wat ons het is die hantering van sowel as al die bome in die bos verwyder. Gebaseer op jou implementering, jy is waarskynlik gaan om te wil om te bel bos verwyder in plaas van eintlik gaan deur al die bome self. Maar as jy enige tydelike bome, wil jy te bevry. Jy weet jou kode die beste, sodat jy weet waar jy die toekenning van geheue. En so, as jy gaan, begin deur selfs beheer F'ing vir malloc, sien wanneer jy malloc en maak seker dat jy vry om al van daardie maar dan net gaan deur jou kode, begrip van waar jy kan geheue toegeken het. Gewoonlik kan jy net sê: "Aan die einde van 'n lêer is ek net gaan op my bos bos te verwyder," so basies duidelik dat die geheue, gratis, "En dan het ek ook gaan om die lêer te sluit en dan my program gaan om op te hou." Maar is dit die enigste keer dat jou program verlaat? Nee, want soms is daar kon gewees het 'n fout wat gebeur het. Miskien kan ons nie 'n lêer oopmaak of ons kon nie 'n ander boom of 'n soort van fout in die geheue toekenning proses gebeur en daarom is dit het NUL teruggestuur. 'N Fout het gebeur en dan is ons terug en stop. So is julle dan wil hê om seker te maak dat enige moontlike tyd dat jou program kan ophou, jy wil al jou geheue om daar te bevry. Dit is nie net gaan aan die einde van die hooffunksie dat jy ophou om jou kode te wees. Jy wil om terug te kyk na elke geval dat jou kode potensieel kan vroeg terug en dan vry watter geheue sin maak. Sê jy het 'n beroep maak bos en teruggekom het vals. Dan sal jy waarskynlik nie nodig om jou bos te verwyder want jy het nie 'n bos nie. Maar by elke punt in die kode waar jy kan vroeg terug jy wil om seker te maak dat jy vry om enige moontlike geheue. 

So wanneer ons te doen het met bevry geheue en met moontlike lekkasies, ons wil nie net gebruik maak van ons oordeel en ons logika maar ook gebruik om Valgrind te bepaal of ons al ons geheue behoorlik bevry het of nie. Jy kan een Valgrind op Puff en dan het jy ook dit slaag die regte hoeveelheid van command-line argumente te Valgrind. Jy kan hardloop, maar die uitset is 'n bietjie kripties. Ons het 'n bietjie wat gebruik word om dit met Speller gekry, maar ons het nog 'n bietjie meer hulp nodig het, so dan loop dit met 'n paar vlae soos die lek-check = volle, wat sal waarskynlik gee ons 'n paar meer nuttig uitset op Valgrind. 

Nog 'n nuttige wenk wanneer jy ontfouting is die diff opdrag. Jy kan toegang tot die personeel se implementering van Huff, hardloop dat 'n tekslêer, en dan uitvoer om dit te 'n binêre lêer, 'n binêre Huff lêer, om meer spesifiek te wees. Dan as jy jou eie puff op daardie binêre lêer, dan ideaal is jou outputted tekslêer gaan identies wees na die oorspronklike een wat jy geslaag het. Hier is ek met behulp van hth.txt as die voorbeeld, en dit is die een wat gepraat oor in jou spec. Dit is letterlik net HTH en dan 'n newline. Maar beslis voel vry en jy is beslis aangemoedig om meer voorbeelde te gebruik vir jou teks lêer. 

Jy kan selfs 'n kans op die miskien comprimeren en dan decompressie sommige van die lêers wat jy gebruik in Speller soos oorlog en vrede of Jane Austen of iets soos dit - dit sal gaaf wees - of Austin Powers, soort van die hantering van groter lêers, want ons sal nie afkom om dit as ons die volgende hulpmiddel hier, ls-l gebruik. Ons kan gebruik om ls, wat basies al die inhoud lys in ons huidige gids. Wat in die vlag-l vertoon eintlik die grootte van die lêers. As jy gaan deur die pset spec, dit loop jy eintlik deur die skep van die binêre lêer, hijgen dit, en jy sien dat vir baie klein lêers die ruimte koste van die comprimeren en die vertaling van al die inligting van al die frekwensies en dinge soos wat swaarder weeg as die werklike voordeel van die comprimeren van die lêer in die eerste plek. Maar as u hardloop en dit op 'n paar langer teks lêers, dan moet jy kan sien dat jy begin om voordeel te kry in die comprimeren van die lêers. 

En dan uiteindelik, ons het ons ou pal GDB, wat is beslis gaan om te kom handig te pas. 

Het ons enige vrae oor Huff bome of die proses miskien van die maak van die bome of enige ander vrae oor Huff'n Puff? Okay. Ek sal bly vir 'n bietjie rond. 

Dankie, almal. Dit was Walk Through 6. En 'n goeie geluk. 

[CS50.TV]