[Powered by Google Translate] [Tutorial - Butlletí de problemes 6] [Zamyla Chan - Harvard University] [Aquesta és CS50. - CS50.TV] 

Hola a tots i benvinguts a Tutorial 6: Puff Huff'n. En Puff Huff'n el que estem fent estarà tractant amb un arxiu comprimit Huffman i després bufar una còpia de seguretat, de manera que la descompressió, pel que podem traduir de el 0 i 1 que l'usuari ens envia i convertir de nou en el text original. Pset 6 va a ser molt bo perquè vas a veure algunes de les eines que va utilitzar en el conjunt de processadors 4 i 5 i el conjunt de processadors tipus de combinació en un concepte bastant net quan s'arriba a pensar-hi. 

També, sens dubte, pset 4 i 5 van ser els conjunts de processadors més difícils que hem hagut d'oferir. Així que a partir d'ara, tenim aquest conjunt de processadors 1 més en C, i després d'això estem en la programació web. Així que us felicito per aconseguir sobre la gepa més dura en CS50. 

Passant per Puff Huff'n, la nostra caixa d'eines per a aquest conjunt de processadors seran arbres de Huffman, de manera que entendre no només com funcionen els arbres binaris, sinó també específicament arbres Huffman, com estan construïts. I llavors tindrem una gran quantitat de codi distribució en aquest conjunt de processadors, i arribarem a veure que en realitat part del codi no podria ser capaç d'entendre completament encara, de manera que aquests seran els arxius. C, però llavors els seus arxius adjunts. h ens donarà prou coneixement que necessitem perquè puguem saber com aquestes funcions es o almenys el que han de fer - les entrades i sortides - encara que no sabem el que està passant en el quadre negre o no entén el que està passant en el quadre negre en el seu interior. I, finalment, com sempre, es tracta de noves estructures de dades, determinats tipus de nodes que apunten a certes coses, i aquí té una ploma i un paper, no només per al procés de disseny i quan vostè està tractant d'esbrinar com el conjunt de processadors han de treballar però també durant la depuració. Vostè pot tenir GDB amb el seu llapis i paper mentre es pren de manera que els valors són, on les fletxes estan apuntant, i coses per l'estil. 

Primer donem una ullada als arbres de Huffman. Arbres Huffman són arbres binaris, el que significa que cada node només té 2 fills. En arbres Huffman la característica és que els valors més freqüents estan representats pels menys bits. Hem vist en els exemples de conferències de codi Morse, quin tipus de consolidat algunes lletres. Si vostè està tractant de traduir una A o una E, per exemple, estàs traduint sovint, així que en lloc d'haver d'utilitzar tot el conjunt de bits previstes per aquest tipus de dades és habitual, es comprimeix a menys, i després aquestes cartes que estan representats amb menys freqüència es representen amb més bits d' ja que pot donar-se el luxe de que quan vostè pesa les freqüències que aquestes cartes apareixen. Tenim la mateixa idea aquí en els arbres de Huffman on estem fent una cadena, una mena de camí per arribar als determinats caràcters. I després els personatges que tenen més freqüència seran representats amb el menor nombre de bits. 

La manera com es construeix un arbre de Huffman és mitjançant la col · locació de tots els caràcters que apareixen en el text i el càlcul de la seva freqüència, la freqüència amb què apareixen. Això podria ser un recompte de les vegades que les lletres apareixen o potser un percentatge d'entre tots els personatges de la quantitat de cada un d'ells apareix. I així, el que fas és un cop que tens tot això fos assignada, llavors busqui les 2 freqüències més baixes i després unir-los com a germans on llavors el node pare té una freqüència que és la suma dels seus 2 nens. I llavors, per convenció, dir que el node esquerre, vostè segueix que, seguint la ramificació 0, i després el node més a la dreta és la branca 1. Com hem vist al codi Morse, el Gotcha una era que si tenies un bip bip i el era ambigua. És ben podria ser 1 carta o podria ser una seqüència de lletres 2. I què arbres Huffman fa és perquè per la naturalesa dels personatges o la final els personatges reals que són els nodes anteriors en el ram - ens referim a aquelles com fulles - en virtut que no hi pot haver cap ambigüitat en termes de la carta que vostè està tractant de codificar amb la sèrie de bits perquè enlloc al llarg dels bits que representen una carta es troba una altra carta sencera, i no hi haurà cap confusió allà. Però entrarem en exemples que vostès poden veure realment que en lloc de nosaltres simplement li diu que això és cert. 

Vegem un exemple simple d'un arbre de Huffman. Tinc una cadena que aquí és de 12 caràcters. Tinc 4 As, 6 B, i C 2. El meu primer pas seria comptar. Quantes vegades Una aparèixer? Sembla 4 vegades a la cadena. B apareix 6 vegades, i C apareix 2 vegades. Naturalment, jo vaig a dir que estic fent servir B amb més freqüència, així que vull representar B amb el menor nombre de bits, el menor nombre de 0s i 1s. I llavors jo també esperaré C i requereixen major quantitat de 0s i 1s també. En primer lloc el que vaig fer aquí els vaig posar en ordre ascendent en termes de freqüència. Veiem que la C i l'A, aquestes són les nostres dues freqüències més baixes. Creem un node pare, i que el node pare no té una carta associada a ell, però té una freqüència, que és la suma. La suma esdevé 2 + 4, que és 6. Després seguim la branca esquerra. Si estiguéssim en aquest node 6, llavors seguiríem 0 a arribar a C i després 1 per arribar a A. Així que ara tenim dos nodes. Tenim el valor 6 i després també tenim un altre node amb el valor 6. I així, els dos no són només el més baix 2, però també només el 2 que queden, Per això amb els d'altres pares, amb la suma és 12. Així que aquí tenim el nostre arbre de Huffman on per arribar a B, que no seria més que el bit 1 i després d'arribar a un tindríem 01 i després C, amb 00. Així que aquí veiem que bàsicament estem representant aquests caràcters amb 1 o 2 bits on el B, com es va predir, té la menor. I llavors el que esperàvem C als que més tenen, però ja que és un petit arbre de Huffman, A continuació, el també està representat per 2 bits en lloc de en algun lloc en el medi. 

Només per repassar altre exemple simple de l'arbre de Huffman, diu que té la cadena "Hola". El que fa és primer que diria quantes vegades H apareguin en el present? H apareix una vegada i després i apareix una vegada i després tenim l apareix dues vegades i o una vegada que apareix. I llavors esperem que la carta de ser representat pel menor nombre de bits? [Estudiant] l. >> L. Si. l és correcte. Esperem l a estar representat pel menor nombre de bits perquè l s'utilitza més en la cadena "Hola". Què faré ara és treure aquests nodes. Tinc 1, que és H, i després un altre 1, que és i, i després un 1, que és O - ara mateix m'estic posant en ordre - i després 2, que és l. Llavors em diuen que el camí que vaig a construir un arbre de Huffman és trobar els 2 nodes que tenen menys freqüències i fer-los germans mitjançant la creació d'un node pare. Aquí tenim 3 nodes amb la freqüència més baixa. Són tots 1. Així que aquí hem de triar un que anem a vincular primer. Diguem de triar l'H i el correu. La suma de 1 + 1 és 2, però aquest node no té una lletra associada amb ella. Només té el valor. Ara ens centrarem en els propers 2 freqüències més baixes. Això és 2 i 1. Això podria ser qualsevol dels 2, però jo vaig a triar aquest. La suma és 3. I, finalment, només tinc 2 a l'esquerra, de manera que es converteix després 5. Llavors aquí, com era d'esperar, si compliment la codificació perquè, 1s sempre la branca dreta i 0s són el de l'esquerra. Llavors tenim l representada per només 1 bit i després o el 2 per i llavors el correu per 2 i després el H cau a 3 bits. Així que vostè pot transmetre aquest missatge "Hola" en lloc d'utilitzar realment els personatges amb només 0s i 1s. No obstant això, recordeu que en diversos casos hem tingut llaços amb la nostra freqüència. Podríem haver ni es va unir a la H i O potser el primer. O llavors més endavant, quan vam tenir la l representat per 2 així com el unit 01:00 representat per 2, podríem haver vinculat qualsevol d'ells. 

I així, quan s'envia el 0 i 1, que en realitat no garanteix que el destinatari pot llegir completament el missatge tot d' perquè no es pot saber quina decisió que ha realitzat. Així que quan ens enfrontem amb la compressió Huffman, d'alguna manera hem de dir-li al receptor del nostre missatge com decidim - Necessita saber algun tipus d'informació addicional A més del missatge comprimit. Ells necessiten entendre el que l'arbre es veu realment com, la manera com realment va fer aquestes decisions. 

Aquí estàvem fent exemples basats en el recompte real, però de vegades també pot tenir un arbre de Huffman basat en la freqüència amb què apareixen les lletres, i és exactament el mateix procés. Aquí m'estic expressant en termes de percentatges o fracció, i aquí exactament el mateix. Em sembla el més baix 2, els suma, la més baixa 2 següent, sumar-los, fins que tingui un arbre. Tot i que podria fer-ho de qualsevol manera, quan estem tractant amb percentatges, això vol dir que estem dividint les coses i tractar amb decimals o més aviat flota si estem pensant en estructures de dades d'un cap. Què sabem sobre els flotadors? Què és un problema comú quan ens enfrontem amb flotadors? [Estudiant] aritmètica imprecisa. Sí >>. La imprecisió. A causa de la imprecisió de coma flotant, per aquest conjunt de processadors de manera que ens assegurem que no es perd cap valor, llavors estem realment estarà tractant amb el comte. Així que si vostè anés a pensar en un node Huffman, si mirem cap enrere a l'estructura d'aquí, si ens fixem en els verds té una freqüència associada a ella així com que apunta a un node a la seva esquerra, així com un node a la seva dreta. I a continuació, els vermells no tenen també un caràcter associat amb ells. No farem altres diferents per als pares i després els nodes finals, la qual ens referim com fulles, sinó més aviat els que acaben tindran valors NULL. Per cada node que tindrem un caràcter, el símbol que representa aquest node, a continuació, una freqüència, així com un punter al seu fill esquerre, així com el seu fill dret. Les fulles, que es troben a la part inferior, també tindria punters a nodes a la seva esquerra ia la seva dreta, però ja que aquests valors no estan apuntant als nodes reals, qual cosa el seu valor sigui? >> [Estudiant] NULL. >> NULL. Exactament. Heus aquí un exemple de com es pot representar la freqüència en carrosses, però anem a tractar amb ell amb nombres enters, així que tot el que he fet és canviar el tipus de dades allà. 

Anirem a una mica més d'un exemple complex. Però ara que hem fet els més simples, és només el mateix procés. Trobareu les 2 freqüències més baixes, sumi les freqüències i aquesta és la nova freqüència del seu node pare, que al seu torn apunta a la seva esquerra amb la ramificació 0 i el dret a la sucursal 1. Si tenim la cadena "This is CS50", llavors compti les vegades que s'esmenta T, h esmentat, i, s, c, 5, 0. Llavors el que vaig fer aquí és amb els nodes vermells Acabo de plantats, He dit que vaig a tenir aquests personatges finalment al fons del meu arbre. Els que seran tots els fulls. Llavors el que vaig fer és que ells ordenats per freqüència en ordre ascendent, i això és en realitat la forma en què el codi de conjunt de processadors que fa Val la classe de freqüència i després per ordre alfabètic. Per tant, té els números primer i després alfabèticament per la freqüència. Llavors el que jo faria és que anava a trobar la més baixa 2. Això és 0 i 5. Jo els suma, i això és 2. A continuació, m'agradaria seguir, trobar el proper 2 baix. Aquests són els dos 1s, i després convertir-se en els 2 també. Ara sé que el meu pròxim pas va a unir-se a la xifra més baixa, que és la T, l'1, i després triar un dels nodes que té 2 com la freqüència. Així que aquí tenim 3 opcions. El que vaig a fer pel tobogan és només visualment reordenar per a vostè perquè pugui veure com ho estic construint. El que el codi i el codi de distribució es farà seria unir-se a la T un amb el node 0 i 5. Així que les sumes a 3, i després continuem el procés. El 2 i el 2 ara són els més baixos, perquè després els suma a 4. Tothom seguint fins ara? Bé. Després, després que tenim el 3 i el 3 que han de ser sumats, així que de nou només ho estic canviant de manera que vostè pot veure visualment perquè no sigui massa complicat. Llavors tenim un 6, i després el nostre pas final és ara que només tenim dos nodes sumem aquells als que l'arrel del nostre arbre, que és 10. I el número 10 té sentit perquè cada node representat, seu valor, el seu número de freqüència, era quantes vegades va aparèixer a la cadena, i després tenim 5 caràcters en la nostra cadena, pel que té sentit. Si mirem a la forma en que realment ho codificar, com s'esperava, la i i la s, que apareixen amb més freqüència estan representats pel menor nombre de bits. 

Aneu amb compte aquí. En el cas d'arbres Huffman realment importa. Una S majúscula és diferent a una s minúscula. Si tinguéssim "Aquest és CS50" amb lletres majúscules, la s minúscula només apareixen dues vegades, Seria un node amb dos com el seu valor, i després S majúscula només seria un cop. Així que l'arbre podria canviar les estructures, ja que en realitat tenen un full addicional aquí. Però la suma encara seria 10. Això és el que realment estarà trucant a la suma de comprovació, l'addició de tots els recomptes. 

Ara que hem cobert els arbres Huffman, podem submergir-nos en Huff'n Puff, el conjunt de processadors. Anem a començar amb una secció de preguntes, i això es posarà vostè acostumat amb els arbres binaris i la forma d'operar al voltant del següent: nodes de dibuix, la creació de la seva pròpia estructura typedef per un node, i veure com es pot inserir en un arbre binari, que està classificat, travessant, i coses per l'estil. Aquest coneixement és, sens dubte ajudarà quan et submergeixis a la part Puff Huff'n del conjunt de processadors. En l'edició estàndard del conjunt de processadors, la seva tasca és implementar Puff, i en la versió pirata de la seva tasca és implementar Huff. Què Huff fa és que pren el text i després es tradueix en el 0 i 1, de manera que el procés que hem fet anteriorment, on comptem amb les freqüències i després va fer l'arbre i després va dir: "Com puc obtenir T?" T està representat per 100, coses així, Huff i després prendria el text i després la sortida que binària. Però també perquè sabem que volem permetre que el nostre destinatari del missatge per tornar a crear el mateix arbre exacta, sinó que també inclou informació sobre els comptes de la freqüència. Després, amb Puff se'ns dóna un arxiu binari de 0 i 1 i donada també la informació sobre les freqüències. Traduïm tots els de tornada 0s i 1s en el missatge original que va ser, pel que estem descomprimint això. Si vostè està fent l'edició estàndard, no cal implementar Huff, així llavors vostè pot utilitzar l'aplicació personal de Huff. Hi ha instruccions en l'especificació de com fer això. Podeu executar l'aplicació personal de Huff en un arxiu de text determinat i aleshores utilitzar aquesta sortida com l'entrada a Puff. 

Com ja he dit abans, tenim una gran quantitat de codi de distribució d'aquesta. Vaig a començar a anar a través d'ell. Vaig a passar la major part del temps al. Arxius h perquè en l'expedient. c, perquè tenim la h. i que ens proporciona els prototips de les funcions, no acabem d'entendre exactament que - Si no entén el que està passant en l'expedient. C, llavors no et preocupis massa, però sens dubte prova a fer una ullada, ja que podria donar algunes pistes i és útil per acostumar-se a la lectura de codi d'altres persones. 

Quant a huffile.h, en els comentaris es declara una capa d'abstracció envers codi de Huffman arxius. Si anem cap avall, veiem que hi ha un màxim de 256 símbols que pot ser que necessiti per codis. Això inclou totes les lletres de l'alfabet en majúscules i minúscules - i després els símbols i números, etc Llavors aquí tenim un nombre màgic que identifica un arxiu amb codificació Huffman. Dins d'un codi Huffman que tindran un nombre de certa màgia associat amb la capçalera. Això podria semblar només un nombre màgic a l'atzar, però si en realitat es tradueixen en ASCII, llavors el que realment explica Huff. Aquí tenim una estructura d'un arxiu amb codificació Huffman. No totes aquestes característiques associades amb un arxiu de Huff. Llavors aquí tenim la capçalera d'un arxiu de Huff, per això en diem Huffeader en lloc d'afegir la h extra perquè sona igual de totes maneres. Cute. Tenim un nombre màgic associat amb ell. Si es tracta d'un veritable arxiu de Huff, que serà el nombre de dalt, aquest màgic. I llavors tindrà una matriu. Així, per a cada símbol, dels quals hi ha 256, que va a enumerar el que la freqüència d'aquests símbols es troben a l'arxiu de Huff. I, finalment, tenim una suma de comprovació de les freqüències, que ha de ser la suma d'aquestes freqüències. Així que això és el que un Huffeader és. Llavors tenim algunes funcions que retornen el següent bit a l'arxiu de Huff així com escriu un bit en el fitxer de Huff, i llavors aquesta funció aquí, hfclose, que en realitat tanca l'arxiu Huff. Abans, es tractava de recta just fclose, però quan es té un arxiu de Huff, en lloc del fclosing el que realment farà és hfclose i hfopen ella. Són funcions específiques als arxius Huff que estarem tractant. Llavors aquí es llegeix a la capçalera i després escriure la capçalera. 

Amb només llegir l'arxiu. H puguem tipus de tenir una idea de què és un arxiu Huff podria ser, ¿Quines característiques té, sense haver d'anar a la huffile.c, que, si ens submergim en, serà una mica més complex. Té tot l'arxiu I / O aquí tractant amb punters. Aquí veiem que quan anomenem hfread, per exemple, encara es tracta d'fread. No anem a desfer-nos d'aquestes funcions del tot, però estem enviant als quals es van ocupar de dins de l'arxiu de Huff en lloc de fer tot nosaltres mateixos. Vostè pot sentir-se lliure per explorar a través d'això si vostè és curiós i anar a pelar la capa de nou una mica. 

El següent arxiu que anem a mirar és tree.h. Abans del Tutorial llisca vam dir d'esperar un node Huffman i vam fer un node typedef struct. Esperem que tingui un símbol, una freqüència, i després 2 estrelles node. En aquest cas el que estem fent és que aquest és essencialment el mateix però en lloc de node anem a cridar arbres. Tenim una funció que quan es crida a fer arbre que li retorna un punter arbre. Retorn a Speller, quan estaven fent un nou node vostè ha dit node paraula * nou = malloc (sizeof) i coses per l'estil. Bàsicament, mktree es tractarà amb això per tu. De la mateixa manera, quan es vol treure un arbre, pel que és essencialment alliberant a l'arbre quan hagi acabat amb ell, en comptes de cridar explícitament lliure en què, en realitat estàs només va a utilitzar la funció de rmtree on es passa el punter a aquest arbre i després tree.c es farà càrrec d'això per tu. 

Analitzem tree.c. Esperem que les mateixes funcions, excepte per veure la implementació. No és sorprenent, quan es diu mktree el mallocs la mida d'un arbre en un punter, inicialitza tots els valors per al valor NULL, de manera que 0 º o nuls, i torna el punter a aquest arbre que acaba de malloc'd a vostè. Aquí quan es diu a eliminar arbre per primera vegada s'assegura que vostè no està alliberant doble. S'assegura que vostè realment té un arbre que voleu eliminar. Heus aquí perquè un arbre també inclou els seus fills, el que això fa és que crida de forma recursiva eliminar arbre al node esquerre de l'arbre així com el node dret. Abans que s'allibera als pares, ha de alliberar els nens també. Pares també és intercanviable amb l'arrel. El pare per primera vegada, així que com el tatara-tatara-tatara-tatara-avi o arbre àvia, primer hem de alliberar pels primers nivells. Així que recórrer fins al fons, sense ells, i després tornar a pujar, sense ells, etc Així que això és arbre. 

Ara ens centrarem en els boscos. Bosc és on es col · loquen tots els arbres de Huffman. És com dir que haurem cosa que es diu una parcel · la que conté un punter a un arbre, així com un punter a una trama anomenada següent. Quina estructura té aquest tipus de sembla? En certa manera es diu per aquí. Just per aquí. Una llista enllaçada. Veiem que quan tenim un argument que és com una llista enllaçada de parcel · les. Un bosc es defineix com una llista enllaçada de parcel · les, de manera que l'estructura del bosc és només tindrem un punter a la nostra primera parcel · la i que la parcel · la té un arbre dins d'ella o, més aviat apunta a un arbre i després apunta a la trama següent, així successivament i així successivament. Perquè un bosc que anomenem mkforest. A continuació tenim algunes funcions molt útils aquí. Hem de triar on es passa en un bosc i després el valor de retorn és un * Arbre, un punter a un arbre. Què selecció farà és que vaig a entrar al bosc que està apuntant a després retiri un arbre amb la freqüència més baixa d'aquest bosc i després donar-li el punter a aquest arbre. Quan vostè truqui a recollir, l'arbre no existirà mai més al bosc, però el valor de retorn és el punter a aquest arbre. Llavors vostè té la planta. Sempre que es passa un punter a un arbre que té una freqüència de no-0, quina planta farà és que prendrà el bosc, prengui l'arbre, i que dins de la planta de l'arbre de la selva. Aquí tenim rmforest. Similar a eliminar arbre, que bàsicament va alliberar a tots els nostres arbres per a nosaltres, treure bosc que per a tota realitat lliure contingut en aquest bosc. 

Si ens fixem en forest.c, esperarem a veure almenys una ordre rmtree allà, perquè per alliberar memòria al bosc si un bosc té arbres-hi, després, eventualment hauràs treure aquests arbres també. Si ens fixem en forest.c, tenim la nostra mkforest, que és el que esperem. Tenim coses malloc. Ens inicialitzar la primera parcel · la al bosc com NULL perquè està buit, per començar, llavors veiem selecció, que retorna l'arbre amb el pes més baix, la freqüència més baixa, i després es desfà d'aquest node particular que apunta a aquest arbre i el que ve, per la qual cosa pren que de la llista enllaçada de la selva. I llavors aquí tenim planta, que insereix un arbre a la llista enllaçada. El que fa és que els boscos bé manté ordenats per a nosaltres. I, finalment, tenim rmforest i, com era d'esperar, tenim rmtree anomenat allà. 

Quant a la distribució de codi fins ara, huffile.c va ser probablement amb molt més difícil d'entendre, mentre que els altres arxius en si eren força fàcils de seguir. Amb el nostre coneixement dels punters i llistes enllaçades i tal, hem estat capaços de seguir bastant bé. Però tot el que necessitem fer realment segur que estem totalment d'entendre són els arxius. H perquè cal estar trucant a aquestes funcions, que tracta dels valors de retorn, així que assegureu-vos que comprèn perfectament l'acció que es realitzarà cada vegada que es cridi a una d'aquestes funcions. Però en realitat la comprensió dins de la mateixa no és molt necessari perquè tenim aquests. Arxius h. Tenim 2 més arxius que queden en el nostre codi de distribució. 

Fem una ullada a abocador. Bolcat pel seu comentari aquí pren un arxiu comprimit Huffman- i després tradueix i abocadors de tot el seu contingut fora. Aquí veiem que s'està cridant hfopen. Aquesta és una espècie de mirall per presentar d'entrada * = fopen, i després se li passa la informació. És gairebé idèntic excepte que en lloc d'un arxiu * que estiguis passant un Huffile; en lloc de fopen que està passant a hfopen. Aquí llegim a la primera capçalera, que és una espècie de manera similar a com es llegeix a la capçalera per a un arxiu de mapa de bits. El que estem fent aquí és la comprovació per veure si la informació de l'encapçalament conté el nombre màgic correcte que indica que és un arxiu real Huff, llavors totes aquestes comprovacions per assegurar-se que l'arxiu obert que és un arxiu real huffed o no. El que això fa és que emet les freqüències de tots els símbols que podem veure dins d'un terminal en una taula gràfica. Aquesta part serà útil. Té una mica i llegeix poc a poc en la variable de bits i després imprimeix. Així que si jo fos a cridar bolcat en hth.bin, que és el resultat d'inhalar un arxiu utilitzant la solució personal, m'agradaria tenir això. És la sortida de tots aquests personatges i després posar la freqüència amb què apareixen. Si ens fixem, la majoria d'ells són 0s excepte per això: H, que apareix dues vegades, i llavors T, que apareix una vegada. I aquí tenim el missatge real en 0s i 1s. Si ens fixem en hth.txt, que presumiblement és el missatge original que es bufo, esperem veure alguns Hs i Ts en aquest país. En concret, s'espera veure a 1 T i HS 2. Aquí estem en hth.txt. En efecte, té HTH. Inclòs en allà, encara que no ho podem veure, és un caràcter de nova línia. El hth.bin arxiu Huff també es codifica el caràcter de nova línia també. Heus aquí perquè sabem que l'ordre és HTH i després salt de línia, podem veure que probablement l'H està representada per només un únic 1 i després la T és probablement 01 i després el següent és H 1, així i llavors tenim una nova línia indicada per dos 0s. Cool. 

I finalment, perquè estem tractant múltiple. Cy. Arxius h, tindrem un argument prou complex per al compilador, i aquí tenim un Makefile que fa bolcat per a vostè. Però en realitat, hi ha d'anar sobre la fabricació del seu propi arxiu puff.c. El Makefile en realitat no tracta de fer puff.c per a vostè. Estem deixant que depèn de vostè per editar el Makefile. Quan s'introdueix una ordre com fan tots, per exemple, farà tot per vostè. Siéntase lliure de mirar els exemples de Makefile del conjunt de processadors passat així com sortir d'aquest per veure com podria ser capaç de fer que l'arxiu Puff mitjançant l'edició d'aquest Makefile. Això és tot pel nostre codi de distribució. 

Quan hagi passat per això, llavors aquí és només un altre recordatori de la manera com tindrem tracte amb els nodes de Huffman. No estarem trucant als nodes més, nosaltres estarem trucant arbres on anem a representar el seu símbol amb un char, seva freqüència, el nombre d'ocurrències, amb un nombre enter. Estem usant això perquè és més precís que un flotador. I després tenim un altre punter al fill esquerre i el fill dret. Un bosc, com hem vist, és només una llista enllaçada d'arbres. En última instància, quan estem construint el nostre arxiu Huff, volem que el nostre bosc per contenir només 1 arbre - Un arbre, una arrel amb diversos nens. Anteriorment quan estàvem fent els nostres arbres Huffman, comencem posant tots els nodes en la nostra pantalla i dir que tindrem aquests nodes, eventualment seran les fulles, i aquesta és el seu símbol, es tracta de la seva freqüència. En el nostre bosc si només tenim tres cartes, que és un bosc de 3 arbres. I després, a mesura que avancem, quan es va agregar el primer pare, vam fer un bosc de 2 arbres. Hem eliminat dos dels fills del nostre bosc i després ho va reemplaçar amb un node pare que tenia aquests dos nodes com els nens. I, finalment, el nostre últim pas amb la fabricació del nostre exemple amb l'As, Bs i Cs seria fer la matriu final, i és així, que portaria al nostre compte total dels arbres al bosc a 1. Tothom veu com s'inicia amb diversos arbres al bosc i acabar amb 1? Bé. Cool. 

Què és el que hem de fer per Puff? El que hem de fer és assegurar-se que, com sempre, ens donen el tipus d'entrada perquè pugui executar el programa. En aquest cas, estarem donant-nos després del seu primer argument de la línia d'ordres 2 més: l'arxiu que desitja descomprimir i la sortida de l'arxiu descomprimit. Però quan ens assegurem que ens passi en la quantitat correcta dels valors, volem assegurar que l'entrada és un fitxer Huff o no. I un cop et garantim que és un arxiu de Huff, llavors volem construir el nostre arbre, construir l'arbre de manera que coincideixi amb l'arbre que la persona que va enviar el missatge construït. A continuació, després de construir l'arbre, llavors podem tractar amb ell, 0s i 1s que van passar a segueixen al llarg del nostre arbre perquè és idèntic, i després escriure aquest missatge, interpretar els bits de nou en chars. I després, al final, ja que es tracta de punters aquí, volem assegurar-nos que no tenim pèrdues de memòria i que tot sigui gratis. 

Vetllar per l'ús adequat és força vell per a nosaltres per ara. Prenem en una entrada, que serà el nom del fitxer que s'inflen, i llavors especificar una sortida, de manera que el nom de l'arxiu per a la sortida d'inflat, que serà l'arxiu de text. Aquesta és el seu ús. I ara volem assegurar-nos que l'entrada està esbufegar com si no. Pensant-ho bé, hi havia alguna cosa en el codi de distribució que ens poden ajudar a amb la comprensió de si un arxiu està esbufegar o no? No hi havia informació en huffile.c sobre la Huffeader. Sabem que tots els arxius Huff té un Huffeader associat amb un nombre màgic així com una matriu de les freqüències per a cada símbol així com una suma de comprovació. Ho sabem, però que també ens va portar una ullada a dump.c, en el qual es llegeix en un arxiu de Huff. I per fer això, havia de comprovar si realment es va bufar com si no. Així que potser podríem utilitzar dump.c com una estructura per al nostre puff.c. Tornar al conjunt de processadors 4 quan vam tenir la copy.c arxiu que va copiar en triples RGB i es va interpretar que per Whodunit i canvi de mida, de la mateixa manera, el que es pot fer és executar la comanda com cp dump.c puff.c i l'ús d'una part del codi allà. No obstant això, no serà tan senzill d'un procés per a la traducció de la seva dump.c en puff.c, però almenys li dóna un lloc per començar en la forma de garantir que l'entrada està realment o no esbufegar així com algunes altres coses. Ens hem assegurat l'ús adequat i assegurar-se que l'entrada està esbufegar. Cada vegada que hem fet el que hem fet el nostre revisió d'errors adequat, el de tornar i deixar la funció si es produeix alguna fallada, si hi ha un problema. 

Ara el que vull fer és construir l'arbre real. Si ens fixem en el bosc, hi ha 2 funcions principals que anem a voler conèixer molt bé. Aquí hi ha la planta funció booleana que planta un arbre freqüència no-0 a l'interior del nostre bosc. I així es passa un punter a un bosc i un punter a un arbre. Una pregunta ràpida: Com molts boscos es té quan vostè està construint un arbre de Huffman? El nostre bosc és com el nostre llenç, no? Així que només tindrem un bosc, però tindrem diversos arbres. Així que abans de trucar a la planta, que està probablement va a voler fer el seu bosc. Hi ha una ordre perquè si ens fixem en forest.h sobre com vostè pot fer un bosc. Vostè pot plantar un arbre. Sabem com fer-ho. I llavors vostè pot també escollir un arbre del bosc, l'eliminació d'un arbre amb el pes més baix i que li dóna el punter a això. Pensant de nou a quan estàvem fent els exemples de nosaltres mateixos, quan l'estàvem traient, simplement acaba d'afegir els enllaços. Però aquí, en lloc de limitar-se a afegir els enllaços, Crec que és més com estàs traient 2 dels nodes i després reemplaçar-lo per un altre. Per expressar que en termes de collita i sembra, vostè està recollint dos arbres i després plantar un altre arbre que té aquests dos arbres que vostè va escollir com nens. Per construir arbre de Huffman, es pot llegir en els símbols i les freqüències per tal de perquè el Huffeader dóna a tu, t'ofereix una àmplia gamma de les freqüències. Així que vostè pot seguir endavant i simplement fer cas omís de qualsevol cosa amb el 0 en el mateix perquè no volem 256 fulls al final de la mateixa. Només volem que el nombre de fulls que són personatges que s'utilitza realment en l'arxiu. Vostè pot llegir en aquests símbols, i cada un d'aquests símbols que tenen freqüències no-0, els que seran arbres. El que pot fer és que cada vegada que es llegeix en un símbol de freqüència no-0, vostè pot plantar aquest arbre al bosc. Quan plantar els arbres al bosc, vostè pot unir-se als arbres com germans, així d'anar de nou a la sembra i la collita en el qual recollir 2 i després la planta 1, on aquesta planta 1 que vostè és el pare dels dos nens que vostè va escollir. Així que el resultat final serà un sol arbre al bosc. Aquesta és la forma de construir el seu arbre. 

Hi ha diverses coses que podrien sortir malament aquí perquè estem tractant amb la fabricació de nous arbres i fer front als punters i coses per l'estil. Abans, quan estàvem tractant amb punters, sempre que malloc'd volíem assegurar-nos que no ens retornen un valor de punter NULL. Així que en diversos passos dins d'aquest procés no seran diversos casos on el programa podria fallar. El que vull fer és que vostè vol assegurar-se que vostè maneja aquests errors, i en l'especificació que diu manejar amb gràcia, així com imprimir un missatge a l'usuari dient per què el programa ha de deixar de fumar i després ràpidament sortir-ne. Per això, el control d'errors, recordi que vostè desitgi comprovar cada vegada que hi ha podria ser un fracàs. Cada vegada que vostè està fent un nou punter vostè vol assegurar-se que això és un èxit. Abans del que solem fer és fer un nou punter i malloc ella, i llavors podríem comprovar si aquest punter és NULL. Així que aquí hi haurà alguns casos on només es pot fer això, però de vegades en realitat està cridant a una funció i dins d'aquesta funció, que és la que està fent el mallocing. En aquest cas, si mirem enrere a algunes de les funcions dins del codi, alguns d'ells són funcions booleanes. En el cas abstracte si tenim una funció booleana anomenada foo, Bàsicament, podem suposar que, a més de fer el que fa foo, ja que és una funció booleana, retorna vertader o fals - true si és correcte, false en cas contrari. Així que volem comprovar si el valor de retorn de foo és vertader o fals. Si és fals, això vol dir que anem a voler imprimir algun tipus de missatge i surti del programa. El que volem fer és comprovar el valor retornat de foo. Si foo retorna false, llavors sabem que ens trobem amb algun tipus d'error i hem de sortir del nostre programa. Una manera de fer això és tenir una condició on la funció en si és la seva condició. Digui foo pren en x. Podem tenir com a condició if (foo (x)). Bàsicament, això vol dir que si al final de l'execució de foo retorna veritable, llavors no podem fer això perquè la funció d'avaluar foo amb la finalitat d'avaluar la condició general. Així que així és com es pot fer alguna cosa si la funció retorna veritat i la aconsegueix. Però quan un és la comprovació d'errors, només vol deixar de fumar si la seva funció retorna false. El que podria fer és afegir un == false o simplement afegir una explosió al davant d'ella i després tens if (! foo). Dins d'aquest cos d'aquesta condició que tindria tot el control d'errors, així com, "No s'ha pogut crear aquest arbre" i després retornar 1 o alguna cosa per l'estil. El que fa, però, és que encara foo retornat false - Digui foo retorna true. Llavors vostè no ha de trucar a foo nou. Això és un error comú. A causa que va ser en la seva condició, ja està avaluat, de manera que ja tenen el resultat si vostè està utilitzant make arbre o alguna cosa així o de la planta o de la selecció o una cosa així. Ja té aquest valor. Ja està executat. Així que és útil l'ús de funcions booleanes com la condició perquè si està o no fa és executar el cos del bucle, s'executa la funció de totes maneres. 

El nostre segon a últim pas és escriure el missatge a l'arxiu. Un cop de construir l'arbre de Huffman, a continuació, escriure el missatge en l'arxiu és bastant senzill. És bastant senzill ara a seguir només el 0 i 1. I així, per convenció, se sap que en un arbre de Huffman dels 0 Indiqueu esquerre i el 1s indicar dreta. Així que si vostè llegeix en poc a poc, cada vegada que s'obté un 0 podràs seguir la branca esquerra, i després cada vegada que es llegeix en un 1 vostè seguirà la branca dreta. I llavors vostè va a continuar fins arribar a un full perquè les fulles estaran a l'extrem de les branques. Com podem saber si ens hem topat amb un full o no? Ho hem dit abans. [Estudiant] Si els punters són NULL. Sí >>. Podem saber si ens hem topat amb un full si els punters als arbres de l'esquerra i la dreta són NULL. Perfecte. Sabem que volem llegir a poc a poc en el nostre arxiu de Huff. Com hem vist abans en dump.c, el que van fer és que llegeixen en poc a poc a l'arxiu de Huff y només imprimeix el que els bits eren. No estarem fent això. Estarem fent una cosa que és una mica més complex. Però el que podem fer és que podem prendre aquest tros de codi que llegeix a la broca. Aquí tenim el bit enter que representa el bit actual que estem. Aquest s'encarrega de iteració a tots els bits en l'arxiu fins que arribi al final de l'arxiu. Basat en això, llavors vostè va a voler tenir algun tipus de Iterador per recórrer l'arbre. I a continuació, en funció de si el bit és 0 o 1, vostè va a voler moure qualsevol que Iterador cap a l'esquerra o moure'ls a la dreta tot el camí fins arribar a un full, de manera que tot el camí fins a aquest node que està en no apunta a cap nodes més. Per què hi farem això amb un arxiu de Huffman, però no el codi Morse? Perquè en codi Morse que hi ha una mica d'ambigüitat. Podríem ser com, oh espera, ens hem topat amb una carta en el camí, així que potser aquesta és la nostra carta, mentre que si seguim una mica més, llavors hauria colpejat una altra carta. Però això no passarà a la codificació Huffman, per la qual cosa podem estar segurs que l'única manera que anem a colpejar un caràcter és si els fills esquerre i dret que node són NULL. 

Finalment, volem alliberar tots de la nostra memòria. Volem tant a tancar l'arxiu Huff que hem estat tractant amb així com eliminar tots els arbres del nostre bosc. Segons la seva aplicació, vostè està probablement va a voler cridar a treure bosc lloc de realment anar a través de tots els arbres vostè mateix. Però si vostè va fer els arbres temporals, haurà d'alliberar això. Vostè sap que el seu millor codi, així que vostè sap on és l'assignació de memòria. Així que si vas a, comenci fins i tot per al Control f'ing malloc, veient cada vegada que malloc i assegurar-se que et alliberi de tot això però llavors només va a través del seu codi, entendre en què podria haver assignat la memòria. En general, podeu dir: "Després d'un arxiu que només vaig a treure la meva bosc en bosc" així que bàsicament esborrar aquest record, sense que, "I llavors jo també vaig a tancar l'arxiu i llavors el meu programa deixarà de fumar." Però és que l'única vegada que el seu programa es tanca? No, perquè de vegades pot haver hagut un error que va ocórrer. Potser no hem pogut obrir un arxiu o no podíem fer altra arbre o algun tipus d'error ocorregut en el procés d'assignació de memòria i pel que va tornar NULL. Un errada i després vam tornar i deixar de fumar. Així que vostè vol assegurar-se que qualsevol moment és possible que el programa pot deixar de fumar, desitja alliberar tota la memòria allà. No només estarà a la final de la funció principal que surt del seu codi. Vols veure de nou a tots els casos que el codi potencialment podria tornar abans d'hora i després alliberar la memòria tot el que té sentit. Digui que l'havia cridat a fer del bosc i que va tornar falsa. Llavors probablement no haurà de treure el seu bosc No té un bosc encara. Però en tots els punts del codi en el qual podria tornar abans d'hora vostè voldrà assegurar-se que vostè alliberar qualsevol memòria possible. 

Així que quan ens enfrontem a l'alliberament de memòria i tenir fuites potencials, Volem no només utilitzarem el nostre judici i la nostra lògica sinó també utilitzar Valgrind per determinar si s'ha alliberat tota la nostra memòria correctament o no. Podeu executar Valgrind en Puff i llavors vostè ha de passar també el nombre correcte d'arguments de línia de comandes per Valgrind. Pots córrer, però la sortida és una mica críptic. Ens hem tornat una mica acostumat a això amb el revisor ortogràfic, però encara necessitem l'ajuda d'una mica més, de manera que també s'executa amb algunes banderes més com la fugida-check = complet, que probablement ens donarà una sortida més útil sobre Valgrind. 

Després, un altre consell útil quan s'està depurant és la comanda diff. Pot accedir a l'aplicació al personal de Huff, córrer que en un arxiu de text, i després la sortida a un fitxer binari, un arxiu binari Huff, que és específica. Llavors si executa el seu propi alè sobre aquest arxiu binari, llavors l'ideal, l'arxiu de text de sortida tipus serà idèntic a l'original que passa pulg Aquí estic fent servir hth.txt com a exemple, i aquesta és la que es parla en la seva especificació. Això és, literalment, només HTH i després un salt de línia. Però definitivament se sent lliure i que són sens dubte anima a utilitzar més exemples per l'arxiu de text. 

Vostè pot fins i tot fer una foto a potser la compressió i descompressió de llavors alguns dels arxius que s'utilitzen en Speller com Guerra i Pau o Jane Austen o alguna cosa per l'estil - que seria una mena de fresc - o Austin Powers, tipus de tractar amb arxius més grans, ja que no hauria arribat fins a ell si fem servir la següent eina aquí, ls-l. Estem acostumats a ls, que bàsicament mostra tots els continguts al nostre directori actual. En passar per la bandera-l en realitat mostra la mida dels arxius. Si vostè va a través de l'especificació del conjunt de processadors, el que realment li guia a través de crear l'arxiu binari, de bufar, i es veu que per arxius molt petits el cost de l'espai de comprimir i traduir tota aquesta informació de totes les freqüències i coses per l'estil que sigui més gran que el benefici real de comprimir l'arxiu en el primer lloc. Però si l'executa en alguns arxius de text més llargs, llavors és possible que vegi que vostè comença a aconseguir algun benefici a la compressió dels arxius. 

I, finalment, tenim al nostre vell amic GDB, que sens dubte serà molt útil també. 

Tenim alguna pregunta sobre els arbres Huff o el procés potser de fer que els arbres o qualsevol altra pregunta sobre Puff Huff'n? Bé. Em quedaré voltant per una mica. 

Gràcies a tots. Això era Tutorial 6. I bona sort. 

[CS50.TV]