[Powered by Google Translate] [Soluzione - Problema Set 6] [Zamyla Chan - Harvard University] [Questo è CS50. - CS50.TV] 

Ciao a tutti, e benvenuti a Scenario 6: Puff Huff'n. In Puff Huff'n quello che stiamo facendo sta andando a che fare con un file compresso Huffman e poi sbuffando di nuovo in su, in modo da decompressione, in modo che possiamo tradurre dal 0 e 1 che l'utente ci invia e convertirlo di nuovo nel testo originale. Pset 6 è sarà piuttosto fresco perché si sta andando a vedere alcuni degli strumenti utilizzato nel pset 4 e 5 e pset tipo di combinarle in 1 concetto abbastanza carino quando si arriva a pensarci. 

Inoltre, probabilmente, pset 4 e 5 sono stati i più difficili pset che aveva da offrire. Quindi da ora, abbiamo questa pset altri 1 in C, e poi, dopo che siamo alla programmazione web. Quindi voi congratulo per superare il più duro gobba in CS50. 

Passando per Puff Huff'n, la nostra cassetta degli attrezzi per questo pset saranno alberi di Huffman, in modo da comprendere non solo come il lavoro binario alberi, ma anche in particolare alberi di Huffman, come sono costruiti. E poi stiamo andando ad avere un sacco di codice di distribuzione in questo pset, e ci vengono a vedere che in realtà parte del codice potremmo non essere in grado di comprendere appieno ancora, e così quelli che saranno i file. c, ma poi i loro accompagnatori. h file ci darà abbastanza capire che abbiamo bisogno in modo da sapere come funzionano queste funzioni o per lo meno quello che dovrebbero fare - i loro ingressi e uscite - anche se non sappiamo cosa sta succedendo nella scatola nera o non capiscono cosa sta succedendo nella scatola nera all'interno. E infine, come al solito, si tratta di strutture di dati nuovi, specifici tipi di nodi che puntano a certe cose, ed ecco avente una carta e penna non solo per il processo di progettazione e quando si sta cercando di capire come dovrebbe funzionare il vostro pset ma anche durante il debug. Si può avere GDB insieme alla tua carta e penna, mentre si prende giù quali sono i valori, in cui le frecce siano rivolte, e cose del genere. 

Prima diamo un'occhiata agli alberi di Huffman. Alberi di Huffman sono alberi binari, il che significa che ogni nodo ha solo 2 figli. Negli alberi Huffman la caratteristica è che i valori più frequenti sono rappresentati dai minor quantità di bit. Abbiamo visto negli esempi delle lezioni di codice Morse, che tipo di consolidato alcune lettere. Se stai cercando di tradurre una A o una E, per esempio, si sta traducendo che spesso, così, invece di dover utilizzare il set completo di bit assegnare per il solito tipo di dati, lo si comprime fino a meno, e poi quelle lettere che sono rappresentati meno spesso sono rappresentati con più bit perché si può permettere che, quando si pesano le frequenze che le lettere compaiono. Abbiamo la stessa idea qui in alberi di Huffman dove stiamo facendo una catena, una sorta di percorso per arrivare ai personaggi alcuni. E poi i personaggi che hanno più frequenza stanno per essere rappresentata con il minor numero di bit. 

Il modo in cui si costruisce un albero di Huffman è mettere tutti i personaggi che compaiono nel testo e calcolando la loro frequenza, la frequenza con cui appaiono. Questo potrebbe essere un conteggio di quante volte quelle lettere appaiono o forse una percentuale su tutti i caratteri quante ognuno appare. E così quello che fai è una volta che avete tutto questo fuori mappato, poi si guarda per le 2 frequenze più basse e poi unirsi a loro come fratelli dove poi il nodo genitore ha una frequenza che è la somma delle sue due bambini. E poi, per convenzione, dire che il nodo di sinistra, si segue che seguendo lo 0 ramo, e quindi il nodo più a destra è il 1 filiale. Come abbiamo visto in codice Morse, il un dettaglio è che se si ha solo un segnale acustico e il segnale acustico era ambigua. Esso potrebbe essere 1 lettera o potrebbe essere una sequenza di due lettere. E allora cosa Huffman alberi fa è perché dalla natura dei personaggi o i nostri personaggi finali effettivi che sono i nodi ultime sul ramo - ci riferiamo a quelli come foglie - in virtù di che non vi può essere alcuna ambiguità in termini di quale lettera si sta cercando di codificare con la serie di bit perché nulla lungo i bit che rappresentano 1 lettera vi incontrano un'altra lettera tutto, e non ci sarà alcuna confusione lì. Ma andiamo in esempi che voi ragazzi può effettivamente vedere che invece di noi solo dicendo che questo è vero. 

Vediamo un semplice esempio di un albero di Huffman. Ho una stringa qui che è di 12 caratteri. Ho 4 Come, 6 B, e 2 Cs. Il mio primo passo sarebbe quello di contare. Quante volte A appare? Appare 4 volte nella stringa. B appare 6 volte, e C compare 2 volte. Naturalmente, ho intenzione di dire che sto usando B il più delle volte, quindi voglio rappresentare B con il minor numero di bit, il minor numero di 0 e 1. E poi ho anche intenzione di aspettare C di richiedere il maggior numero di 0 e 1, come pure. In primo luogo quello che ho fatto qui è Li ho messi in ordine crescente in termini di frequenza. Vediamo che la C e la A, queste sono le nostre 2 frequenze più basse. Creiamo un nodo genitore, e tale nodo padre non dispone di una lettera ad esso associata, ma ha una frequenza, che è la somma. La somma diventa 2 + 4, che è 6. Poi seguiamo il ramo di sinistra. Se fossimo in quel nodo 6, poi ci avrebbe seguito da 0 a raggiungere C e poi 1 per arrivare ad A. Così ora abbiamo 2 nodi. Abbiamo il valore 6 e quindi abbiamo anche un altro nodo con il valore 6. E così quei 2 non sono solo più 2, ma anche solo il 2 che sono di sinistra, così ci uniamo a quelle di un altro genitore, con la somma sia 12. Quindi qui abbiamo il nostro albero di Huffman dove per arrivare a B, che sarebbe solo il bit 1 e poi per arrivare a A avremmo 01 e quindi C con 00. Così, qui vediamo che, in fondo stiamo rappresentare questi caratteri con 1 o 2 bit dove il B, come previsto, ha il minimo. E poi ci aspettavamo C per avere di più, ma dal momento che è un piccolo albero di Huffman, poi la A è rappresentato da 2 bit a differenza qualche parte nel mezzo. 

Solo per andare oltre un altro semplice esempio di albero di Huffman, dire che hai la stringa "Ciao". Quello che fai è prima dire quante volte H appare in questo? H appare una volta e poi e compare una sola volta e poi abbiamo l appare due volte e o apparire una volta. E così poi ci aspettiamo che la lettera di essere rappresentato dal minor numero di bit? [Studente] l. >> L. Gia '. l è giusto. Ci aspettiamo l per essere rappresentato dal minimo numero di bit perché l è usato più in la stringa "Ciao". Quello che sto per fare ora è tirare fuori questi nodi. Ho 1, che è H, e poi un altro 1, che è posta, e poi un 1, che è O - in questo momento io li sto mettendo in ordine - e poi 2, che è l. Allora io dico che il modo in cui ho costruito un albero di Huffman è quello di trovare i 2 nodi con meno frequenze e li rendono fratelli creando un nodo padre. Qui abbiamo 3 nodi con la frequenza più bassa. Sono tutti 1. Ecco quindi scegliere quale andremo a collegare prima. Diciamo che ho scelto l'H e l'indirizzo. La somma di 1 + 1 è 2, ma questo nodo non ha una lettera ad esso associati. Tiene solo il valore. Ora guardiamo i prossimi 2 frequenze più basse. Che è 2 e 1. Questo potrebbe essere uno di questi 2, ma ho intenzione di scegliere questo. La somma è 3. E poi finalmente, ho solo 2 a sinistra, in modo quindi che diventa 5. Poi qui, come previsto, se compilare la codifica per questo, 1s sono sempre il ramo di destra e 0 sono la sinistra. Poi abbiamo l rappresentato dal solo 1 po 'e poi l'O di 2 e quindi l'e da 2 e poi l'H scende a 3 bit. Così si può trasmettere questo messaggio "Ciao" invece di realtà utilizzando i caratteri da solo 0 e 1. Tuttavia, ricordare che in diversi casi abbiamo avuto legami con la nostra frequenza. Avremmo potuto né aderito H e l'O forse prima. Oppure poi più tardi, quando abbiamo avuto la l rappresentata da 2 nonché l'unita quello rappresentato da 2, abbiamo potuto legati né uno. 

E così, quando si invia il 0 e 1, che in realtà non garantisce che il destinatario può leggere il messaggio completo destra fuori del blocco perché potrebbe non sapere quale decisione che hai fatto. Così, quando abbiamo a che fare con la compressione Huffman, in qualche modo dire al destinatario del nostro messaggio come abbiamo deciso - Hanno bisogno di sapere qualche tipo di informazioni aggiuntive in aggiunta al messaggio compresso. Hanno bisogno di capire che cosa l'albero si presenta come, come abbiamo effettivamente fatto quelle decisioni. 

Qui stavamo solo facendo esempi basati sul conteggio effettivo, ma a volte si può anche avere un albero di Huffman in base alla frequenza con cui le lettere appaiono, e il processo è esattamente lo stesso. Qui mi sto esprimendo in termini di percentuali o di una frazione, ed ecco la stessa cosa. Trovo il 2 più basso, riassumerle, il più basso 2 successivo, li somma, finché non avrò un albero pieno. Anche se potremmo farlo in entrambi i modi, quando abbiamo a che fare con percentuali, che significa che stiamo dividere le cose e si occupano di decimali o meglio galleggia se stiamo pensando di strutture di dati di una testa. Che cosa sappiamo di carri? Che cosa è un problema comune quando abbiamo a che fare con i galleggianti? [Studente] aritmetica impreciso. Sì >>. Imprecisione. A causa di imprecisione in virgola mobile, per questo pset in modo da assicurarsi che che non perde alcun valore, allora siamo veramente andando a che fare con il conteggio. Quindi, se si dovesse pensare ad un nodo Huffman, se si guarda indietro alla struttura qui, se si guardano quelle verdi ha una frequenza ad esso associati nonché punta a un nodo alla sua sinistra e un nodo alla sua destra. E poi i rossi ci hanno anche un carattere associato con loro. Non stiamo andando a fare quelle separate per i genitori e poi i nodi finali, cui ci riferiamo come foglie, ma questi saranno solo i valori NULL. Per ogni nodo avremo un carattere, il simbolo che rappresenta quel nodo, quindi una frequenza e un puntatore al suo figlio sinistro e il suo figlio destro. Le foglie, che sono in fondo, avrebbe anche puntatori nodo alla loro sinistra e alla loro destra, ma dal momento che tali valori non siano rivolte ai nodi reali, quale sarebbe il loro valore è? >> [Studente] NULL. >> NULL. Esattamente. Ecco un esempio di come si potrebbe rappresentare la frequenza di carri allegorici, ma stiamo andando a che fare con con numeri interi, quindi tutto quello che ho fatto è cambiare il tipo di dati lì. 

Passiamo a un po 'più di un esempio complesso. Ma ora che abbiamo fatto quelli semplici, è proprio lo stesso processo. Potete trovare le 2 frequenze più basse, sommare le frequenze e questa è la nuova frequenza del nodo padre, che punta poi alla sua sinistra con il ramo 0 e il diritto con il ramo 1. Se abbiamo la stringa "Questo è CS50", quindi contiamo quante volte viene citato T, h accennato, i, s, c, 5, 0. Allora quello che ho fatto qui è con i nodi rossi ho appena piantato, Ho detto che ho intenzione di avere questi personaggi alla fine nella parte inferiore del mio albero. Coloro che saranno tutte le foglie. Allora quello che ho fatto è che li ordinato per frequenza in ordine crescente, e questo è in realtà il modo in cui il codice pset fa è esso viene ordinato in base alla frequenza e poi in ordine alfabetico. Così ha i numeri e poi in ordine alfabetico per la frequenza. Allora quello che vorrei fare è che avrei trovato il 2 più basso. Questo è 0 e 5. Io li somma, e questo è 2. Poi vorrei continuare, trovare il prossimo 2 più basso. Questi sono gli 1 due, e poi quelli diventano 2, come pure. Ora so che il mio prossimo passo sta per entrare a far parte il numero più basso, che è la T, l'1 e quindi scegliendo uno dei nodi che ha 2 come frequenza. Quindi qui abbiamo 3 opzioni. Che cosa ho intenzione di fare per la diapositiva è solo visivamente riorganizzare per voi in modo che si può vedere come lo sto costruendo. Quello che il codice e il codice di distribuzione è intenzione di fare sarebbe far parte T uno con il nodo 0 e 5. Allora che le somme a 3, e poi continuiamo il processo. Il 2 e il 2 ora sono i più bassi, in modo poi quelli somma a 4. Tutti in seguito fino ad ora? Va bene. Poi, dopo che abbiamo il 3 e il 3 che devono essere sommati, così ancora una volta sto solo di commutazione in modo che si può vedere visivamente in modo che non diventi troppo disordinato. Poi abbiamo un 6, e poi il nostro passo finale è che ora abbiamo solo 2 nodi sommiamo quelli per rendere la radice del nostro albero, che è 10. E il numero 10 ha un senso, perché ogni nodo rappresentato, il loro valore, il loro numero di frequenza, è quante volte sono apparsi nella stringa, e poi abbiamo 5 caratteri nella nostra stringa, in modo che abbia un senso. Se guardiamo a come si sarebbe in realtà lo codifica, come previsto, la i e la s, che appaiono più spesso sono rappresentati dal minor numero di bit. 

Fate attenzione qui. Negli alberi di Huffman caso conta realmente. Un S maiuscola è diverso da una s minuscola. Se avessimo "Questo è CS50" con lettere maiuscole, quindi la lettera minuscola s solo apparire due volte, sarebbe un nodo con 2 come il suo valore, e quindi S maiuscola sarebbe solo una volta. Allora l'albero sarebbe cambiare le strutture, perché in realtà hanno una foglia in più qui. Ma la somma sarebbe ancora 10. Questo è quello che stiamo effettivamente andando a essere chiamata la somma di controllo, l'aggiunta di tutti i conteggi. 

Ora che abbiamo coperto gli alberi di Huffman, siamo in grado di tuffarsi in Puff Huff'n, il pset. Stiamo per iniziare con una sezione di domande, e questo sta per farti abituato con gli alberi binari e come operare in giro che: nodi di disegno, creare il tuo proprio struct typedef per un nodo, e vedere come è possibile inserire in un albero binario, che è ordinato, movimento, e cose del genere. Questa conoscenza è sicuramente essere di aiuto quando ci si immerge nella porzione Puff Huff'n del pset. Nell'edizione standard del pset, il vostro compito è quello di attuare Puff, e nella versione hacker, il vostro compito è quello di attuare Huff. Che cosa fa è Huff prende il testo e poi si traduce in 0 e 1, in modo che il processo che abbiamo fatto in precedenza in cui abbiamo contato le frequenze e poi ha fatto l'albero e poi disse: «Come faccio a T?" T è rappresentato da 100, cose del genere, e poi Huff avrebbe preso il testo e poi output binario. Ma anche perché sappiamo che vogliamo permettere che il nostro destinatario del messaggio per ricreare l'albero esattamente lo stesso, ma include anche le informazioni sui conteggi di frequenza. Poi con Puff ci viene dato un file binario di 0 e 1 e dato anche informazioni relative alle frequenze. Traduciamo tutti i vostri cari 0 e 1 nel messaggio originale che era, quindi siamo decompressione che. Se stai facendo l'edizione standard, non è necessario implementare Huff, così allora si può semplicemente utilizzare l'implementazione staff di Huff. Ci sono istruzioni nelle specifiche su come farlo. È possibile eseguire l'applicazione personale di Huff su un file di testo certa e quindi utilizzare tale uscita come input per Puff. 

Come ho detto prima, abbiamo un sacco di codice di distribuzione per questo. Ho intenzione di cominciare ad andare attraverso di essa. Ho intenzione di passare la maggior parte del tempo sul file. H perché nei file. c, perché abbiamo il. h e che ci fornisce i prototipi delle funzioni, non siamo pienamente bisogno di capire esattamente - Se non si capisce cosa sta succedendo nei file. C, quindi non preoccupatevi troppo, ma provare a dare un'occhiata, perché potrebbe dare qualche suggerimento ed è utile abituarsi a leggere il codice di altre persone. 

Guardando huffile.h, nei commenti dichiara un livello di astrazione per Huffman codifica dei file. Se andiamo verso il basso, si vede che c'è un massimo di 256 simboli che potremmo bisogno di codici per. Ciò include tutte le lettere dell'alfabeto - maiuscole e minuscole - e poi simboli e numeri, ecc Allora qui abbiamo un numero magico che identifica un Huffman codifica del file. All'interno di un codice di Huffman che stanno per avere un certo numero magico associato con l'intestazione. Questo potrebbe sembrare un semplice numero magico casuale, ma se in realtà si traducono in ASCII, quindi incantesimi effettivamente fuori HUFF. Qui abbiamo una struttura di un file con codifica Huffman. Ci sono tutte queste caratteristiche associate a un file Huff. Quindi qui abbiamo l'intestazione di un file Huff, e così lo chiamiamo Huffeader invece di aggiungere il h extra perché sembra lo stesso in ogni caso. Carino. Abbiamo un numero magico associato. Se è un file vero e proprio Huff, che sta per essere il numero in alto, questa magia uno. E poi avrà una serie. Quindi per ogni simbolo, di cui ci sono 256, sta andando a elencare ciò che la frequenza di tali simboli sono all'interno del file Huff. E poi finalmente, abbiamo una somma di controllo per le frequenze, che dovrebbe essere la somma di tali frequenze. Quindi questo è quello che è un Huffeader. Poi ci sono alcune funzioni che restituiscono il bit successivo nel file Huff così come scrive un po 'per il file Huff, e poi questa funzione qui, hfclose, che chiude effettivamente il file Huff. Prima, avevamo a che fare con diritto solo fclose, ma quando si ha un file Huff, invece di esso fclosing ciò che si sta effettivamente andando a fare è hfclose e hfopen esso. Queste sono funzioni specifiche ai file Huff che stiamo andando a che fare con. Poi qui si legge nell'intestazione e quindi scrivere l'intestazione. 

Proprio leggendo il file. H possiamo sorta di ottenere un senso di ciò che un file di Huff potrebbe essere, quali sono le caratteristiche che ha, senza andare effettivamente sul huffile.c, che, se ci immergiamo in, sta per essere un po 'più complessa. Ha tutti i file di I / O qui che fare con i puntatori. Qui si vede che, quando chiamiamo hfread, per esempio, è ancora alle prese con fread. Non stiamo sbarazzarsi di queste funzioni del tutto, ma stiamo inviando quelli da prendere cura di all'interno del file di Huff, invece di fare tutto da soli. Si può sentire libero di eseguire la scansione attraverso questo se siete curiosi e andare a buccia lo strato posteriore un po '. 

Il file successivo che stiamo andando a guardare è tree.h. Prima nell'argomento Procedura dettagliata scorre abbiamo detto ci aspettiamo un nodo Huffman e abbiamo fatto un nodo typedef struct. Ci aspettiamo di avere un simbolo, una frequenza, e poi 2 stelle nodo. In questo caso quello che stiamo facendo è questo è essenzialmente la stessa tranne che invece di nodo che andremo a chiamarli alberi. Abbiamo una funzione che quando si chiama fanno albero ti restituisce un puntatore albero. Eseguire il backup di Speller, quando si stavano facendo un nuovo nodo hai detto nodo * nuova parola = malloc (sizeof) e cose del genere. In sostanza, mktree sta andando a che fare con quella per voi. Allo stesso modo, se si desidera rimuovere un albero, in modo che 'essenzialmente liberare l'albero quando hai finito con esso, invece di chiamare esplicitamente libero su questo, si sta effettivamente solo andando a utilizzare la funzione rmtree dove si passa il puntatore su quell'albero e poi tree.c si prenderà cura di questo per voi. 

Guardiamo in tree.c. Ci aspettiamo che le stesse funzioni se non per vedere l'attuazione e. Come ci aspettavamo, quando si chiama mktree mallocs che le dimensioni di un albero in un puntatore, inizializza tutti i valori per il valore NULL, quindi 0 o valori nulli, e restituisce il puntatore a tale albero che hai appena malloc'd a voi. Qui quando si chiama rimozione albero che prima fa in modo che non stai doppia liberazione. Si fa in modo che in realtà hanno un albero che si desidera rimuovere. Ecco perché un albero comprende anche i suoi figli, Quello che fa è che chiama ricorsivamente rimuovere albero sul nodo di sinistra dell'albero così come il nodo di destra. Prima libera la madre, deve liberare i figli. Capogruppo è anche intercambiabile con root. Il genitore prima volta, così come il gran-gran-gran-gran-nonno o albero nonna, prima dobbiamo liberare le livelli di prima. Quindi attraversare fino in fondo, senza quelli, e poi tornare su, senza quelli, ecc Ecco, questo è albero. 

Ora guardiamo alla foresta. Foresta vengono inseriti tutti i vostri alberi di Huffman. Sta dicendo che stiamo andando ad avere qualcosa che si chiama una trama che contiene un puntatore a un albero come un puntatore a una trama chiamata successiva. Quale struttura fa questo tipo di look simile? E 'sorta di si dice laggiù. Proprio qui. Una lista concatenata. Vediamo che quando abbiamo una trama è come una lista concatenata di trame. Una foresta è definito come una lista concatenata di trame, e così la struttura del bosco è che stiamo solo andando ad avere un puntatore per il nostro primo disegno e che la trama ha un albero dentro o punta piuttosto a un albero e punta quindi alla trama successiva, così via e così via. Per effettuare una foresta che chiamiamo mkforest. Poi ci sono alcune funzioni molto utili qui. Abbiamo scegliere dove si passa in un bosco e poi il valore di ritorno è un * albero, un puntatore a un albero. Che scelta farà sarà andrà nella foresta che si sta puntando a quindi rimuovere un albero con la frequenza più bassa di quella foresta e poi ti danno il puntatore a tale struttura. Una volta l'intercettazione, l'albero non esisterà più nella foresta, ma il valore di ritorno è un puntatore a quella struttura. Poi ci sono delle piante. A condizione che si passa un puntatore a un albero che ha un non-0 di frequenza, quale pianta farà è che ci vorrà la foresta, prendere l'albero, e la pianta che all'interno albero della foresta. Qui abbiamo rmforest. Simile a rimuovere albero, che fondamentalmente liberato tutti i nostri alberi per noi, rimuovere foresta sarà tutto libera contenuto in quella foresta. 

Se guardiamo in forest.c, ci aspettiamo di vedere almeno 1 comando rmtree in là, perché per liberare memoria nel bosco, se una foresta con alberi in esso, poi alla fine si sta andando ad avere per rimuovere quegli alberi troppo. Se guardiamo in forest.c, abbiamo il nostro mkforest, che è come ci aspettiamo. Noi malloc cose. Abbiamo inizializzare il primo lotto nella foresta come NULL perché è vuota per cominciare, poi vediamo scelta, che restituisce l'albero con il minor peso, la frequenza più bassa, e poi si fa eliminare quel determinato nodo che punta a quell'albero e quello successivo, quindi ci vuole che fuori dalla lista concatenata della foresta. E poi qui abbiamo delle piante, che si inserisce un albero nella lista collegata. Che cosa si è forestale mantiene ben risolto per noi. E poi finalmente, abbiamo rmforest e, come previsto, abbiamo rmtree chiamato lì. 

Guardando il codice di distribuzione fino ad ora, huffile.c era probabilmente di gran lunga la più difficile da capire, mentre gli altri file stessi erano abbastanza semplice da seguire. Con la nostra conoscenza di puntatori e liste concatenate e così via, siamo stati in grado di seguire abbastanza bene. Ma tutto quello che dobbiamo fare davvero sicuri di comprendere appieno è il file h. perché è necessario essere chiamata a queste funzioni, si occupano di quei valori di ritorno, in modo da assicurarsi di comprendere appieno quale azione sta per essere eseguita ogni volta che si chiama una di queste funzioni. Ma in realtà la comprensione all'interno di esso non è assolutamente necessario, perché ci sono quelli. File h. Abbiamo 2 più file lasciati nel nostro codice di distribuzione. 

Diamo un'occhiata a discarica. Dump dal suo commento qui prende un Huffman file compresso e poi traduce e discariche di tutto il suo contenuto fuori. Qui vediamo che sta chiamando hfopen. Questa è una specie di mirroring di file di input * = fopen, e poi si passa le informazioni. E 'quasi identico tranne che invece di un file * si sta passando in una Huffile; invece di fopen si sta passando a hfopen. Qui si legge nella prima intestazione, che è una specie di simile a come si legge nell'intestazione per un file bitmap. Quello che stiamo facendo qui è il controllo per vedere se l'intestazione informazioni contiene il giusto numero magico che indica che si tratta di un file vero e proprio Huff, allora tutti questi controlli per assicurarsi che il file che si è aperto un file vero e proprio sbuffò o meno. Quello che fa è che emette le frequenze di tutti i simboli che possiamo vedere all'interno di un terminale in una tabella grafica. Questa parte sarà utile. Ha un po 'e legge poco a poco nel bit variabile e quindi stampa fuori. Quindi, se dovessi chiamare dump hth.bin, che è il risultato di sbuffare un file utilizzando la soluzione personale, vorrei ottenere questo. E 'uscita di tutti questi personaggi e poi mettere la frequenza con cui compaiono. Se guardiamo, la maggior parte di loro sono 0s salva questa: H, che appare due volte, e quindi T, che appare una volta. E poi qui abbiamo il messaggio attuale in 0 e 1. Se guardiamo hth.txt, che è presumibilmente il messaggio originale che è stato sbuffò, ci aspettiamo di vedere un po 'di Hs e Ts in là. In particolare, ci aspettiamo di vedere solo 1 T e 2 Hs. Qui siamo in hth.txt. Ha infatti HTH. Incluso in là, anche se non si vede, è un carattere di nuova riga. Il hth.bin file di Huff è anche la codifica del carattere di nuova riga pure. Ecco perché sappiamo che l'ordine è HTH e poi ritorno a capo, possiamo vedere che probabilmente la H è rappresentato da un solo singolo 1 e quindi la T è probabilmente 01 e quindi il successivo è H 1 nonché e poi abbiamo una nuova riga indicata da due 0. Cool. 

E poi, infine, perché abbiamo a che fare con più. Ce. File h, stiamo andando ad avere un argomento piuttosto complesso per il compilatore, e così qui abbiamo un Makefile che fa per voi discarica. Ma in realtà, si deve fare per rendere il proprio file puff.c. Il Makefile in realtà non si tratta di fare puff.c per voi. Stiamo lasciando che fino a di modificare il Makefile. Quando si immette un comando come fanno tutti, ad esempio, farà tutti per voi. Sentitevi liberi di guardare gli esempi di Makefile dalla pset passato così come andare fuori di questo per vedere come si potrebbe essere in grado di rendere il vostro file di Puff modificando il Makefile. Questo è tutto per il nostro codice di distribuzione. 

Una volta che abbiamo ottenuto attraverso quella, allora qui è solo un altro promemoria di come stiamo andando a che fare con i nodi Huffman. Non abbiamo intenzione di chiamare loro nodi più; abbiamo intenzione di essere li chiama alberi dove stiamo andando di rappresentare il loro simbolo con un char, loro frequenza, il numero di occorrenze, con un numero intero. Stiamo utilizzando tale perché è più preciso di un galleggiante. E poi abbiamo un altro puntatore al figlio sinistro e il figlio destro. Una foresta, come abbiamo visto, è solo una lista concatenata di alberi. In definitiva, quando stiamo costruendo il nostro file Huff, vogliamo che la nostra foresta per contenere solo 1 albero - 1 albero, 1 radice con più di un figlio. In precedenza, quando stavamo facendo i nostri alberi di Huffman, abbiamo iniziato mettendo tutti i nodi sul nostro schermo e dire che stiamo andando ad avere questi nodi, alla fine si sta andando ad essere le foglie, e questo è il loro simbolo, questa è la loro frequenza. Nella nostra foresta, se dobbiamo solo 3 lettere, che è una foresta di 3 alberi. E poi come si va avanti, quando abbiamo aggiunto il primo genitore, abbiamo fatto una foresta di 2 alberi. Abbiamo rimosso 2 di quei bambini dal nostro bosco e poi lo ha sostituito con un nodo padre che ha avuto questi 2 nodi come i bambini. E poi finalmente, il nostro ultimo passo con rendendo il nostro esempio con il nome, B, e Cs sarebbe rendere il genitore finale, e così poi che avrebbe portato il nostro numero totale di alberi nella foresta a 1. Ritiene vedere a tutti come si inizia con più alberi nella foresta e finire con 1? Va bene. Cool. 

Che cosa dobbiamo fare per Puff? Quello che dobbiamo fare è garantire che, come sempre, ci danno il giusto tipo di ingresso in modo da poter effettivamente eseguire il programma. In questo caso si sta andando ad essere ci sta dando dopo il loro primo argomento della riga di comando 2 più: il file che vogliamo decomprimere e l'output del file decompresso. Ma una volta che ci assicuriamo che ci passano la giusta quantità di valori, vogliamo garantire che l'input è un file Huff o meno. E poi una volta vi possiamo garantire che si tratta di un file di Huff, quindi vogliamo costruire il nostro albero, costruire l'albero in modo che corrisponda l'albero che la persona che ha inviato il messaggio costruito. Poi, dopo che costruire l'albero, allora possiamo affrontare il, 0 e 1, che hanno superato in seguono quelli lungo il nostro albero perché è identico, e poi scrivere quel messaggio, interpretare i bit di nuovo in caratteri. E poi alla fine, perché abbiamo a che fare con i puntatori qui, si vuole fare in modo che non ci sono perdite di memoria e che tutto gratis. 

Assicurare un corretto utilizzo è vecchio cappello per noi ormai. Prendiamo in un ingresso, che sarà il nome del file a sbuffare, e poi specificare un output, quindi il nome del file per l'output soffiato, che sarà il file di testo. Questo è il loro utilizzo. E ora vogliamo garantire che l'ingresso è sbuffò o meno. Ripensandoci, c'era qualcosa nel codice di distribuzione che potrebbe aiutarci con la comprensione se un file è sbuffò o no? C'era informazioni huffile.c sulla Huffeader. Sappiamo che ogni file Huff ha un Huffeader associato con un numero magico nonché una serie di frequenze per ogni simbolo nonché una checksum. Sappiamo che, ma abbiamo anche preso una sbirciatina al dump.c, in cui si leggeva in un file Huff. E così, per farlo, doveva verificare se davvero è stato sbuffò o meno. Quindi, forse, potremmo usare dump.c come una struttura per il nostro puff.c. Torna a pset 4 quando abbiamo avuto la copy.c file copiato in triple RGB e abbiamo interpretato che per Whodunit e ridimensionamento, allo stesso modo, quello che si potrebbe fare è semplicemente eseguire il comando come cp dump.c puff.c e utilizzare parte del codice lì. Tuttavia, non sarà così semplice di un processo per tradurre il vostro dump.c in puff.c, ma almeno ti dà qualche parte per iniziare su come garantire che l'ingresso è effettivamente sbuffò o meno così come alcune altre cose. Abbiamo assicurato un corretto utilizzo e ha assicurato che l'ingresso è sbuffò. Ogni volta che abbiamo fatto, che abbiamo fatto il nostro controllo proprio errore, così tornare e uscire dalla funzione se qualche errore, se c'è un problema. 

Ora, quello che vogliamo fare è costruire l'albero vero e proprio. Se guardiamo nella foresta, ci sono 2 funzioni principali che stiamo andando a voler diventare molto familiare. C'è l'impianto funzione booleana che le piante di un non-0 albero di frequenza all'interno della nostra foresta. E così ci si passa un puntatore a un bosco e un puntatore a un albero. Domanda veloce: Quante foreste che si ha quando si sta costruendo un albero di Huffman? La nostra foresta è come la nostra tela, giusto? Quindi stiamo solo andando avere 1 foresta, ma abbiamo intenzione di avere più alberi. Quindi, prima di chiamare pianta, si sta probabilmente andando a voler rendere la vostra foresta. C'è un comando per che, se si guarda in forest.h su come si può fare una foresta. Si può piantare un albero. Noi sappiamo come farlo. E allora si può anche scegliere un albero dal bosco, la rimozione di un albero con il minor peso e dando il puntatore a questo. Pensi a quando stavamo facendo gli esempi noi stessi, quando stavamo tirando fuori, abbiamo semplicemente aggiunto i link. Ma qui invece di aggiungere i link, pensare più come si sta rimuovendo 2 di quei nodi e poi sostituirlo con un altro. Per esprimere che in termini di raccolta e impianto, si sta raccogliendo 2 alberi e poi piantare un altro albero che ha quei 2 alberi che avete raccolto da bambini. Per costruire albero di Huffman, è possibile leggere i simboli e le frequenze in ordine perché il Huffeader che dà a voi, ti dà una vasta gamma di frequenze. Così si può andare avanti e ignorare qualsiasi cosa con lo 0 in esso perché non vogliamo 256 foglie alla fine di esso. Noi vogliamo solo il numero di fogli che sono i caratteri che vengono effettivamente utilizzati nel file. È possibile leggere in tali simboli, e ciascuno di questi simboli che hanno frequenze non-0, coloro che stanno per essere alberi. Che cosa si può fare ogni volta che si è letto in un non-0 frequenza di simbolo, è possibile piantare quell'albero nel bosco. Una volta che piantare gli alberi della foresta, si può aderire quegli alberi come fratelli, così tornare a piantare e raccogliere in cui si sceglie 2 e poi impianto 1, dove che 1 che si pianta è il padre dei 2 bambini che hai scelto. Quindi il risultato finale sarà un unico albero nella foresta. Ecco come si costruisce l'albero. 

Ci sono diverse cose che potrebbero andare male qui perché abbiamo a che fare con fare nuovi alberi e trattare con puntatori e cose del genere. Prima, quando avevamo a che fare con i puntatori, ogni volta che malloc'd abbiamo voluto fare in modo che non ci ha restituito un valore NULL pointer. Quindi, a diversi passi all'interno di questo processo ci saranno diversi casi in cui il programma potrebbe fallire. Che cosa si vuole fare è che si vuole fare in modo che gestire tali errori, e nelle specifiche dice di gestirli con grazia, così come stampare un messaggio all'utente dicendo loro motivo per cui il programma deve uscire e poi prontamente uscire. Per fare questo la gestione degli errori, si ricordi che si desidera controllare ogni volta che ci potrebbe essere un guasto. Ogni volta che si sta facendo un nuovo puntatore si vuole fare in modo che questo è successo. La prima cosa che abbiamo usato per fare è effettuare un nuovo puntatore e lo malloc, e poi ci sarebbe verificare se tale puntatore è NULL. Quindi ci saranno alcuni casi in cui si può solo farlo, ma a volte si sta effettivamente chiamando una funzione e all'interno di tale funzione, che è quello che sta facendo il mallocing. In tal caso, se guardiamo indietro ad alcune delle funzioni all'interno del codice, alcuni di loro sono funzioni booleane. Nel caso in astratto se abbiamo una funzione booleana chiamata foo, in fondo, si può supporre che, oltre a fare tutto ciò che fa pippo, dal momento che è una funzione booleana, restituisce vero o falso - vero se ha successo, false in caso contrario. Quindi, vogliamo verificare se il valore di ritorno di foo è vera o falsa. Se è falso, il che significa che stiamo andando a voler stampare un qualche tipo di messaggio e quindi chiudere il programma. Quello che vogliamo fare è controllare il valore di ritorno di foo. Se foo restituisce false, allora sappiamo che abbiamo incontrato qualche tipo di errore e abbiamo bisogno di chiudere il nostro programma. Un modo per farlo è avere una condizione in cui la funzione di vero e proprio è la sua condizione. Dire foo prende in x. Possiamo avere come condizione if (foo (x)). Fondamentalmente, significa che se alla fine di eseguire foo restituisce vero, allora si può fare questo perché la funzione deve valutare foo al fine di valutare la condizione intero. Allora è così che si può fare qualcosa se la funzione restituisce true e ha successo. Ma quando si è il controllo degli errori, si desidera solo uscire se la funzione restituisce false. Che cosa si potrebbe fare è aggiungere un == false o semplicemente aggiungere un botto di fronte ad essa e poi ci sono if (! foo). All'interno di quel corpo di tale condizione si avrebbe tutta la gestione degli errori, così come, "Impossibile creare questo albero" e poi tornare 1 o qualcosa del genere. Cosa che fa, però, è che anche se pippo ha restituito false - Dire foo restituisce true. Allora non c'è bisogno di chiamare foo nuovo. Questo è un errore comune. Perché era nelle tue condizioni, è già valutata, così hai già il risultato se si sta usando make albero o qualcosa del genere o di un impianto o di ritiro o qualcosa del genere. Ha già quel valore. E 'già eseguito. Quindi è utile utilizzare le funzioni booleane come condizione perché se realmente eseguito il corpo del ciclo, esegue la funzione comunque. 

Il nostro secondo per ultimo passo è scrivere il messaggio nel file. Una volta che si costruisce l'albero di Huffman, quindi scrivere il messaggio nel file è abbastanza semplice. E 'abbastanza semplice per seguire solo la 0 e 1. E così, per convenzione, si sa che in un albero di Huffman le 0s indicano a sinistra e gli 1 indicano a destra. E allora se si leggono in poco a poco, ogni volta che si ottiene uno 0 si segue il ramo di sinistra, e quindi ogni volta che si legge in un 1 avete intenzione di seguire il ramo di destra. E poi avete intenzione di continuare fino a colpire una foglia perché le foglie stanno per essere alla fine dei rami. Come possiamo sapere se abbiamo colpito una foglia o no? L'abbiamo detto prima. [Studente] Se i puntatori sono NULL. Sì >>. Siamo in grado di dire se abbiamo colpito una foglia se i puntatori agli alberi sia di sinistra e destra sono NULL. Perfetto. Sappiamo che si desidera leggere a poco a poco nel nostro file di Huff. Come abbiamo visto prima in dump.c, quello che hanno fatto è che leggono poco a poco nel file Huff e appena stampata che cosa fossero quei bit. Non abbiamo intenzione di fare questo. Stiamo andando a fare qualcosa che è un po 'più complessa. Ma quello che possiamo fare è che possiamo prendere quel po 'di codice che legge al bit. Qui abbiamo il bit numero intero che rappresenta il bit corrente che siamo sulla. Questo si occupa di scorrere tutti i bit nel file fino a colpire la fine del file. Sulla base di questo, allora si sta andando a voler avere un qualche tipo di iteratore per attraversare il vostro albero. E quindi a seconda che il bit è 0 o 1, si sta andando a voler spostare o che iteratore a sinistra o spostare verso destra tutta la strada fino a quando si colpisce una foglia, per cui tutta la strada fino a quel nodo che si è in non puntare ai nodi più. Perché possiamo fare questo con un file di Huffman, ma non il codice Morse? Perché in codice Morse c'è un po 'di ambiguità. Potremmo essere come, oh attesa, abbiamo colpito una lettera lungo la strada, quindi forse questa è la nostra lettera, mentre se abbiamo continuato solo un po 'di più, poi ci avrebbe colpito un'altra lettera. Ma questo non succederà nella codifica Huffman, in modo che possiamo stare tranquilli che l'unico modo che stiamo andando a colpire un personaggio è se i bambini a destra ea sinistra di quel nodo sono NULL. 

Infine, vogliamo liberare tutta la nostra memoria. Vogliamo sia vicino il file Huff che abbiamo avuto a che fare con così come rimuovere tutti gli alberi della nostra foresta. Sulla base della sua implementazione, probabilmente stai andando a voler chiamare rimuovere foresta invece di realtà passa attraverso tutti i voi stessi alberi. Ma se hai fatto di alberi temporanei, ti consigliamo di liberare questo. Tu conosci il tuo codice migliore, in modo da sapere dove si sta allocazione di memoria. E quindi se si va, si fa partire anche da controllo f'ing per malloc, vedendo ogni volta che si malloc e fare in modo che liberano tutto questo ma poi basta passare attraverso il codice, capire dove si potrebbe avere memoria allocata. Di solito si può solo dire: "Alla fine di un file Sto solo andando a rimuovere foresta sulla mia foresta," quindi fondamentalmente chiaro che la memoria, gratuito che, "E poi ho anche intenzione di chiudere il file e quindi il mio programma sta per uscire." Ma è l'unica volta che il programma si chiude? No, perché a volte ci potrebbe essere stato un errore quello che è successo. Forse non abbiamo potuto aprire un file o non siamo riusciti a fare un altro albero o un qualche tipo di errore è accaduto nel processo di allocazione di memoria e così ha restituito NULL. Un errore è accaduto e poi siamo tornati e uscire. Allora si vuole fare in modo che ogni volta che possibile che il programma può uscire, si vuole liberare tutta la memoria lì. Non è solo sarà alla fine della funzione principale che si chiude il codice. Si vuole guardare indietro a ogni istanza che il codice potenzialmente potrebbe restituire prematuramente e quindi tutto ciò che libera la memoria ha un senso. Diciamo che aveva chiamato fare foresta e che ha restituito false. Allora probabilmente non sarà necessario rimuovere l'insieme di strutture perché non si dispone di una foresta ancora. Ma, in ogni punto del codice in cui si potrebbe tornare prematuramente si vuole fare in modo che liberano la memoria possibile. 

Così, quando abbiamo a che fare con la liberazione della memoria e con perdite potenziali, si desidera utilizzare non solo il nostro giudizio e la nostra logica ma anche utilizzare Valgrind per determinare se abbiamo liberato tutti della nostra memoria correttamente o meno. È possibile eseguire Valgrind sulla sfoglia e poi si deve anche passare il giusto numero di riga di comando argomenti Valgrind. È possibile eseguire, ma l'uscita è un po 'criptico. Abbiamo ottenuto un po 'l'abitudine con correttore ortografico, ma abbiamo ancora bisogno di aiuto un po' di più, così allora in esecuzione con alcune bandiere più come la perdita-check = pieno, che probabilmente ci darà un output più disponibile su Valgrind. 

Poi un altro suggerimento utile per il debug è il comando diff. È possibile accedere implementazione del personale di Huff, eseguire che in un file di testo, e poi l'output in un file binario, un file binario Huff, per essere precisi. Poi, se si esegue il tuo soffio proprio su quel file binario, poi idealmente, il file di testo in output sarà identico a quello originale che avete passato trovi Qui sto usando hth.txt come esempio, e questo è quello parlato nelle specifiche. Questo è letteralmente HTH e poi un ritorno a capo. Ma sicuramente sentire liberi e vi sono sicuramente incoraggiati ad usare gli esempi più per il file di testo. 

Si può anche prendere un colpo a forse la compressione e la decompressione poi alcuni dei file che avete usato per Speller come Guerra e pace o Jane Austen o qualcosa del genere - che sarebbe un po 'freddo - o di Austin Powers, tipo di trattare con file di grandi dimensioni, perché non sarebbe venuto al dunque se abbiamo utilizzato lo strumento successivo qui, ls-l. Siamo abituati a ls, che elenca in pratica tutti i contenuti nella nostra directory corrente. Passando il flag-l visualizza effettivamente le dimensioni di tali file. Se si passa attraverso la specifica pset, cammina in realtà l'utente attraverso la creazione del file binario, di sbuffare, e si vede che per i file molto piccoli il costo dello spazio di compressione e tradurre tutte le informazioni di tutte le frequenze e cose del genere è superiore ai benefici effettivi di comprimere il file in primo luogo. Ma se lo si esegue su alcuni file di testo più lunghi, allora si potrebbe vedere che si inizia ad avere qualche beneficio nel comprimere tali file. 

E poi finalmente, abbiamo la nostra GDB vecchio amico, che è sicuramente di tornare utile anche. 

Abbiamo qualche domanda sugli alberi Huff o il processo forse di fare gli alberi o qualsiasi altra domanda su Puff Huff'n? Va bene. Starò in giro per un po '. 

Grazie a tutti. Questo era Walkthrough 6. E buona fortuna. 

[CS50.TV]