[Powered by Google Translate] [Procédure pas à pas - 6 Set problème]
[Zamyla Chan - Université de Harvard]
[C'est CS50. - CS50.TV]
>> Bonjour à tous et bienvenue dans Procédure pas à pas 6: Puff Huff'n.
En Puff Huff'n ce que nous faisons va avoir affaire à un fichier compressé Huffman
puis souffler en arrière, donc le décompresser,
afin que nous puissions traduire du 0 et de 1 que l'utilisateur envoie-nous
et le reconvertir dans le texte original.
Pset 6 va être assez cool parce que vous allez voir quelques-uns des outils
que vous avez utilisé dans pset pset 4 et 5 et sorte de les combiner en 1 concept très soigné
quand vous venez d'y penser.
>> De plus, sans doute, pset 4 et 5 sont les plus difficiles psets que nous avions à offrir.
A partir de maintenant, nous avons cette pset 1 plus dans C,
puis, après que nous sommes sur la programmation web.
Alors vous féliciter pour avoir surmonté le plus dur bosse CS50.
>> Passant pour Puff Huff'n, notre boîte à outils pour ce pset vont être les arbres de Huffman,
afin de comprendre non seulement comment le travail arbres binaires, mais aussi en particulier des arbres de Huffman,
comment ils sont construits.
Et puis nous allons avoir beaucoup de code de la distribution dans ce jeu de processeurs,
et nous viendrons à voir ce que fait une partie du code
nous pourrions ne pas être en mesure de bien comprendre encore,
et si ceux-ci seront les fichiers. c, mais qui les accompagnent. h dossiers
nous donnera assez de compréhension que nous avons besoin afin que nous sachions comment ces fonctions sont
ou du moins ce qu'ils sont censés faire - leurs entrées et sorties -
même si nous ne savons pas ce qui se passe dans la boîte noire
ou ne comprennent pas ce qui se passe dans la boîte noire à l'intérieur.
Et puis finalement, comme d'habitude, nous avons affaire à des structures de données nouvelles,
certains types de nœuds qui pointent vers certaines choses,
et voici donc avoir un stylo et du papier, non seulement pour le processus de conception
et quand vous êtes à essayer de comprendre comment votre pset devrait fonctionner
mais aussi pendant le débogage.
Vous pouvez avoir GDB à côté de votre stylo et du papier pendant que vous prenez vers le bas quelles sont les valeurs,
où vos flèches pointent, et des choses comme ça.
>> Premièrement, regardons les arbres de Huffman.
Arbres Huffman sont des arbres binaires, ce qui signifie que chaque nœud possède seulement 2 enfants.
Dans les arbres de Huffman la caractéristique est que les valeurs les plus fréquentes
sont représentés par le plus petit nombre de bits.
Nous avons vu dans les exemples de cours de code Morse, qui sorte de synthèse des lettres.
Si vous essayez de traduire un A ou un E, par exemple,
vous traduisez que souvent, au lieu d'avoir à utiliser l'ensemble de bits
alloué pour ce type d'habitude les données, vous le compresser jusqu'à moins,
puis ces lettres qui sont représentés sont moins souvent représenté avec plus de bits
parce que vous pouvez vous permettre que lorsque vous pesez sur les fréquences que ces lettres apparaissent.
Nous avons la même idée ici dans les arbres de Huffman
où nous faisons une chaîne, une sorte de chemin pour arriver aux certains caractères.
Et puis les personnages qui ont le plus de fréquence
vont être représenté avec le moins de bits.
>> La façon dont vous construisez un arbre de Huffman
est de placer tous les personnages qui apparaissent dans le texte
et le calcul de leur fréquence, combien de fois ils apparaissent.
Il peut s'agir d'un compte de combien de fois ces lettres apparaissent
ou peut-être un pourcentage de rupture de tous les caractères combien chacun apparaît.
Et qu'est-ce que vous faites est une fois que vous avez tout cela sur cartographiés,
puis vous regardez pour les 2 fréquences les plus basses, puis de les rejoindre en tant que frères et sœurs
où le noeud parent a une fréquence qui est la somme de ses 2 enfants.
Et puis vous dire que, par convention, le noeud gauche,
que vous suivez par la suite la branche 0,
puis le nœud le plus à droite est la branche 1.
Comme nous l'avons vu dans le code Morse, le gotcha-ci était que si vous aviez juste un bip et le bip
il était ambiguë.
Elle peut soit être une lettre ou il pourrait s'agir d'une séquence de 2 lettres.
Et qu'est-ce Huffman arbres ne c'est parce que, par nature, des personnages
ou finaux nos personnages réels étant les derniers noeuds sur la branche -
nous nous référons à ceux que les feuilles - en vertu de cela, il ne peut pas y avoir d'ambiguïté
aux termes de laquelle la lettre que vous essayez d'encoder avec la suite de bits
parce que nulle part le long des bits qui représentent 1 lettre
vous rencontrez une autre lettre ensemble, et il n'y aura pas de confusion.
Mais nous irons dans des exemples que vous les gars pouvez réellement voir ce que
au lieu de nous juste vous dire que c'est vrai.
>> Voyons un exemple simple d'un arbre de Huffman.
J'ai ici une chaîne qui est de 12 caractères.
Comme j'ai 4, 6 chambres et 2 Cs.
Ma première étape serait de compter.
Combien de fois ne semblent Une? Il apparaît 4 fois dans la chaîne.
B apparaît 6 fois, et C apparaît 2 fois.
Naturellement, je vais dire que je suis l'aide de B le plus souvent,
si je veux représenter B avec le plus petit nombre de bits, le nombre minimum de 0 et de 1.
Et puis je vais aussi s'attendre C à exiger la plus grande quantité de 0 et de 1 aussi.
D'abord ce que j'ai fait ici est je les ai mis dans l'ordre croissant en termes de fréquence.
Nous voyons que la C et A, ce sont nos 2 fréquences les plus basses.
Nous créons un noeud parent, et ce nœud parent n'a pas une lettre qui lui est associée,
mais il a une fréquence qui est la somme.
La somme devient 2 + 4, qui est la 6.
Puis nous suivons la branche gauche.
Si nous étions à ce noeud 6, puis nous suivrons 0 pour obtenir à C
puis 1 pour se rendre à A.
Nous avons donc maintenant 2 noeuds.
Nous avons la valeur 6, puis nous avons aussi un autre nœud avec la valeur 6.
Et si les 2 ne sont pas seulement le plus bas 2, mais aussi tout simplement les 2 qui restent,
C'est pourquoi, avec celles de l'autre parent, avec la somme de 12.
Nous avons donc ici notre arbre de Huffman
où se rendre à B, qui ne serait que le bit 1
et puis vous rendre à nous aurions 01 puis C ayant 00.
Donc, ici, nous voyons que, fondamentalement, nous représentons ces caractères avec 1 ou 2 bits
où le B, comme prévu, a tout le moins.
Et puis nous nous attendions à C comptent le plus, mais puisque c'est comme un petit arbre de Huffman,
puis l'un est aussi représenté par 2 bits au lieu de quelque part au milieu.
>> Juste pour revenir sur un autre exemple simple de l'arbre de Huffman,
dire que vous avez la chaîne "Bonjour".
Ce que vous faites est d'abord vous dire combien de fois ne H apparaissent dans cette?
H apparaît une fois et puis e apparaît une fois et puis nous avons l apparaissant deux fois
o et apparaissant une fois.
Et alors nous nous attendons à laquelle la lettre doit être représenté par le plus petit nombre de bits?
[L'élève] l. L >>. Ouais. l est à droite.
Nous nous attendons l d'être représentés par le plus petit nombre de bits
parce que l est le plus utilisé dans la chaîne "Bonjour".
Ce que je vais faire maintenant est de faire ressortir ces nœuds.
J'ai 1, qui est H, puis une autre 1, qui est e, puis un 1, qui est o -
en ce moment je leur mise au point - puis 2, qui est l.
Puis-je dire la façon dont je construis un arbre de Huffman est de trouver les 2 noeuds avec le moins de fréquences
et de les rendre frères et sœurs en créant un nœud parent.
Ici, nous avons 3 noeuds avec la plus basse fréquence. Ils sont tous 1.
Nous voilà donc choisir celui qui nous allons relier premier.
Disons que je choisis le H et le e.
La somme de 1 + 1 = 2, mais ce noeud n'a pas de lettre qui lui est associée.
Il détient un peu la valeur.
Maintenant, nous regardons les 2 prochaines fréquences les plus basses.
Ce sont 2 et 1. Cela pourrait être l'un de ceux 2, mais je vais choisir celui-ci.
La somme est 3.
Et puis finalement, je n'ai que 2 à gauche, si cela devient 5.
Alors voilà, comme prévu, si je remplis dans le codage pour cela,
1s sont toujours la branche de droite et de 0 sont celle de gauche.
Ensuite, nous avons l représentée par seulement 1 bit, puis le joint de 2
et ensuite la 2 e par le H puis retombe à 3 bits.
Ainsi, vous pouvez transmettre ce message "Bonjour" au lieu d'utiliser effectivement les caractères
simplement en 0 et de 1.
Cependant, rappelez-vous que dans plusieurs cas nous avons eu des liens avec notre fréquence.
Nous aurions pu soit rejoint le H et le premier peut-être o.
Ou alors plus tard, quand nous avons eu la l représenté par 2
ainsi que le joint représenté par une 2, on aurait pu liés soit une.
>> Et donc quand vous envoyez le 0 et de 1, cela ne fait pas une garantie
que le destinataire peut lire entièrement votre message dès le départ
car ils risquent de ne pas savoir quelle décision que vous avez fait.
Alors, quand nous avons affaire à une compression de Huffman,
en quelque sorte, nous devons informer le destinataire de notre message que nous avons décidé -
Ils ont besoin de savoir un certain genre d'information supplémentaire
en plus du message compressé.
Ils ont besoin de comprendre ce que l'arbre ressemble réellement,
comment nous pris ces décisions.
>> Ici, nous ne faisions que des exemples basés sur le nombre réel,
mais parfois vous pouvez aussi avoir un arbre de Huffman
basée sur la fréquence à laquelle les lettres apparaissent, et c'est le même processus.
Ici, je vais l'exprimer en termes de pourcentage ou une fraction,
et voici donc exactement la même chose.
Je trouve la plus faible 2, les résumer, les 2 plus basse suivante, les résumer,
jusqu'à ce que j'aie un arbre complet.
Même si nous pourrions le faire de toute façon, quand nous traitons avec des pourcentages,
cela signifie que nous sommes diviser les choses et de traiter avec des décimales ou plutôt flotte
si nous pensons à des structures de données d'une tête.
Que savons-nous sur les flotteurs?
Qu'est-ce qu'un problème commun quand nous traitons avec des flotteurs?
[L'élève] arithmétique imprécise. Ouais >>. L'imprécision.
En raison de l'imprécision virgule flottante, pour ce pset afin que nous nous assurions
que nous ne perdons pas toutes les valeurs, alors nous allons en fait avoir affaire avec le comte.
Donc, si vous deviez penser à un nœud de Huffman, si vous regardez en arrière à la structure ici,
si vous regardez les verts il a une fréquence qui lui est associé
aussi bien qu'il pointe vers un nœud à sa gauche, ainsi que d'un noeud à sa droite.
Et puis il ya les rouges ont également un caractère qui leur est associée.
Nous n'allons pas faire de séparés pour les parents, puis les nœuds finaux,
que nous appelons les feuilles, mais plutôt ceux qui vont juste avoir la valeur NULL.
Pour chaque nœud, nous aurons un caractère, le symbole que représente ce nœud,
alors une fréquence, ainsi qu'un pointeur vers son enfant gauche et droite de son enfant.
Les feuilles, qui sont tout en bas, aurait également pointeurs de noeuds
à leur gauche et à leur droite, mais puisque ces valeurs ne sont pas orientées vers des noeuds réels,
quelle serait leur valeur soit? >> [L'élève] NULL. NULL >>. Exactement.
Voici un exemple de la façon dont vous pouvez représenter la fréquence de flotteurs,
mais nous allons y faire face avec des nombres entiers,
donc tout ce que je fait est de changer le type de données là-bas.
>> Passons maintenant à un peu plus d'un exemple complexe.
Mais maintenant que nous avons fait les plus simples, c'est juste le même processus.
Vous trouverez les 2 fréquences les plus basses, la somme des fréquences
et c'est la nouvelle fréquence de votre noeud parent,
qui pointe alors à sa gauche avec la branche 0 et le droit à la branche 1.
Si nous avons la chaîne "C'est CS50", alors nous compter combien de fois est mentionnée T,
h mentionné, i, s, c, 5, 0.
Alors qu'est-ce que j'ai fait ici est avec les nœuds rouges que je viens plantés,
J'ai dit que je vais avoir fini ces caractères au bas de mon arbre.
Ceux vont être toutes les feuilles.
Ensuite, ce que j'ai fait, c'est que je les trier par fréquence en ordre croissant,
et c'est en fait la façon dont le code pset il ne
est-ce qu'il trie par fréquence puis par ordre alphabétique.
Ainsi, il a les chiffres d'abord, puis par ordre alphabétique de la fréquence.
Alors qu'est-ce que je ferais, c'est que je ne trouve plus bas 2. C'est 0 et 5.
Je les résume, et c'est 2. Ensuite, je voudrais continuer, trouver les 2 prochaines bas.
Ce sont les 1 deux, puis ceux-ci deviennent 2 ainsi.
Maintenant je sais que ma prochaine étape va être de rejoindre le plus petit nombre,
qui est le T, le 1, puis en choisissant l'un des noeuds qui a la fréquence 2.
Nous avons donc ici 3 options.
Ce que je vais faire pour la diapositive est juste visuellement les réorganiser pour vous
afin que vous puissiez voir comment je suis en train de construire.
Ce que le code et le code de distribution va faire serait rejoindre le T
avec le noeud 0 et 5.
Alors que des sommes à 3, puis nous continuons le processus.
Le 2 et le 2 maintenant sont les plus bas, oui, alors ceux somme de 4.
Tout le monde suit ce jour? D'accord.
Puis, après que nous avons le 3 et le 3 qui doivent être additionnés,
donc encore une fois je ne fais que passer afin que vous puissiez voir visuellement afin qu'il ne soit pas trop salissant.
Ensuite, nous avons un 6, et alors notre dernière étape consiste maintenant que nous n'avons que 2 nœuds
nous résumons les faire à la racine de notre arbre, qui est de 10.
Et le numéro 10 a un sens parce que chaque nœud représenté,
leur valeur, leur numéro de fréquence, c'était combien de fois ils sont apparus dans la chaîne,
puis nous avons 5 personnages de notre chaîne, donc cela fait sens.
Si nous regardons la façon dont nous aurions fait l'encoder,
comme prévu, le i et le s, qui apparaissent le plus souvent
sont représentés par le plus petit nombre de bits.
>> Faites attention ici.
Dans le cas des arbres de Huffman importe réellement.
Un S majuscule est différent d'un s minuscule.
Si nous avions «C'est CS50" avec des majuscules, minuscules, puis le s ne semblent deux fois,
serait un nœud avec 2 comme valeur, puis majuscule S ne serait qu'une seule fois.
Alors votre arbre allait changer les structures, car vous avez réellement une feuille supplémentaire ici.
Mais la somme serait encore 10.
C'est ce que nous allons en fait être l'appel de la somme de contrôle,
l'addition de tous les chefs d'accusation.
>> Maintenant que nous avons couvert des arbres de Huffman, on peut plonger dans Puff Huff'n, le pset.
Nous allons commencer avec une section de questions,
et ce qui se passe pour vous l'habitude d'arbres binaires et comment fonctionnent autour de ce qui suit:
nœuds de dessin, créez votre propre struct typedef pour un nœud,
et de voir comment vous pouvez insérer dans un arbre binaire, celui qui est triée,
traversant, et des choses comme ça.
Cette connaissance va certainement vous aider lorsque vous plongez dans la partie Puff Huff'n
de la pset.
Dans l'édition standard du jeu de processeurs, votre tâche est de mettre en œuvre Puff,
et dans la version pirate votre tâche est de mettre en œuvre Huff.
Qu'est-ce Huff fait est qu'il faut texte, puis elle se traduit par des 0 et des 1,
de sorte que le processus que nous avons fait ci-dessus où nous avons compté les fréquences
et ensuite l'arbre et dit alors: «Comment puis-je obtenir T?"
T est représenté par 100, des choses comme ça,
puis Huff prendrait le texte, puis sortie binaire.
Mais aussi parce que nous savons que nous voulons permettre à nos destinataire du message
pour recréer l'arbre exactement le même, il comprend également des informations sur les comptes de fréquence.
Puis, avec Puff on nous donne un fichier binaire de 0 et de 1
et compte tenu également de l'information sur les fréquences.
Nous traduisons tous ceux qui reviennent 0 et de 1 dans le message original qui a été,
Nous sommes donc décompresser cela.
Si vous faites l'édition standard, vous n'avez pas besoin de mettre en œuvre Huff,
alors vous pouvez simplement utiliser l'application personnel de Huff.
Il ya des instructions dans les spécifications sur la façon de le faire.
Vous pouvez exécuter l'application personnel de Huff sur un fichier texte certain
et ensuite utiliser cette sortie comme entrée de Puff.
>> Comme je l'ai mentionné précédemment, nous avons une grande quantité de code de distribution de celui-ci.
Je vais commencer à aller à travers elle.
Je vais passer la plupart du temps sur le fichiers. H
parce que dans les fichiers de c., parce que nous avons l'h.
et qui nous fournit les prototypes des fonctions,
nous ne sommes pas totalement besoin de comprendre exactement -
Si vous ne comprenez pas ce qui se passe dans les fichiers de c., Alors ne vous inquiétez pas trop,
mais certainement essayer de faire un tour car il pourrait donner quelques conseils
et il est utile de s'habituer à la lecture de code d'autres personnes.
>> En regardant huffile.h, dans les commentaires qu'il déclare une couche d'abstraction pour Huffman codés fichiers.
Si nous descendons, nous voyons qu'il ya un maximum de 256 symboles que nous pourrions avoir besoin pour les codes.
Cela comprend toutes les lettres de l'alphabet en majuscules et minuscules - -
et puis symboles et des chiffres, etc
Ensuite, nous avons ici un nombre magique identifier un fichier codé Huffman.
Au sein d'un code de Huffman ils vont avoir un nombre magique certaine
associée à l'en-tête.
Cela pourrait ressembler à un simple numéro de magie aléatoire,
mais si vous avez réellement le traduire en ASCII, il énonce effectivement sur HUFF.
Ici, nous avons une structure d'un fichier codé Huffman.
Il ya toutes ces caractéristiques associées à un fichier Huff.
Alors ici nous avons l'en-tête d'un fichier Huff, afin que nous appelons Huffeader
au lieu d'ajouter l'h supplémentaire, car il sonne de la même façon.
Cute.
Nous avons un nombre magique qui lui est associé.
Si c'est un fichier réel Huff, ça va être le nombre au-dessus, celui-ci magie.
Et puis il aura un tableau.
Ainsi, pour chaque symbole, dont il existe 256,
il va lister ce que la fréquence de ces symboles se trouvent dans le fichier Huff.
Et puis enfin, nous avons une somme de contrôle pour les fréquences,
qui devrait être la somme de ces fréquences.
C'est donc ce qui est un Huffeader.
Ensuite, nous avons quelques fonctions qui retournent le bit suivant dans le fichier Huff
ainsi que le transcrit dans le fichier Huff, puis cette fonction ici, hfclose,
qui ferme le fichier Huff.
Avant, nous avions affaire à droite juste fclose,
mais quand vous avez un fichier Huff, au lieu de le fclosing
ce que vous allez réellement faire est hfclose et hfopen.
Ce sont des fonctions spécifiques aux fichiers Huff que nous allons être confrontés.
Alors voilà, nous lisons dans l'en-tête, puis d'écrire l'en-tête.
>> Juste en lisant le fichier. H nous pouvons sorte de se faire une idée de ce qu'est un fichier Huff peut-être,
quelles sont les caractéristiques qu'il possède, sans pour autant entrer dans le huffile.c,
qui, si nous plonger, va être un peu plus complexe.
Il dispose de tous les fichiers I / O affaire ici avec des pointeurs.
Ici, nous voyons que lorsque nous appelons hfread, par exemple, il est toujours aux prises avec fread.
Nous ne sommes pas de se débarrasser de ces fonctions tout à fait, mais nous envoyons ceux qui doivent être pris en charge
dans le fichier Huff au lieu de faire tout nous-mêmes.
Vous pouvez, n'hésitez pas à parcourir si vous êtes curieux
et d'aller peler la couche arrière un peu.
>> Le prochain dossier que nous allons regarder est tree.h.
Avant Procédure pas à pas dans la glisse, nous avons dit nous nous attendons à un nœud de Huffman
et nous avons fait un nœud typedef struct.
Nous nous attendons à avoir un symbole, une fréquence, puis 2 étoiles nœud.
Dans ce cas, ce que nous faisons, c'est que c'est essentiellement la même
sauf qu'au lieu de nœud, nous allons appeler les arbres.
Nous avons une fonction que lorsque vous appelez make arbre, il vous renvoie un pointeur arbre.
Retour vers Speller, lorsque vous faisiez un nouveau nœud
vous avez dit noeud * nouveau mot = malloc (sizeof) et des choses comme ça.
Fondamentalement, mktree va avoir affaire à cela pour vous.
De même, lorsque vous souhaitez supprimer un arbre,
donc c'est essentiellement en libérant l'arbre lorsque vous avez terminé avec lui,
au lieu de d'appeler explicitement gratuitement sur cela, vous êtes en fait juste l'intention d'utiliser la fonction rmtree
où vous passez le pointeur sur cet arbre, puis tree.c prendra soin de cela pour vous.
>> Nous nous penchons sur tree.c.
Nous attendons les mêmes fonctions, sauf pour voir la mise en œuvre aussi bien.
Comme on s'y attendait, lorsque vous appelez mktree il mallocs la taille d'un arbre dans un pointeur,
initialise toutes les valeurs à la valeur NULL, donc 0 ou NULL,
puis retourne le pointeur vers cet arbre que vous venez de malloc pour vous.
Ici, lorsque vous appelez enlever un arbre il fait d'abord s'assurer que vous n'êtes pas à double libération.
Il permet de s'assurer que vous avez réellement un arbre que vous souhaitez supprimer.
Ici, à cause d'un arbre comprend également ses enfants,
ce que cela ne se fait-il s'appelle récursivement enlever un arbre sur le noeud de gauche de l'arbre
ainsi que le noeud de droite.
Avant cela libère le parent, il doit libérer les enfants aussi.
Parent est également interchangeable avec la racine.
Le parent première fois, donc comme le grand-grand-grand-grand-père
ou un arbre grand-mère, il faut d'abord libérer le bas les niveaux d'abord.
Donc, traverser vers le bas, sans ceux-ci, et puis revenir, sans ceux-ci, etc
Donc, c'est l'arbre.
>> Maintenant, nous regardons la forêt.
Forest est où vous placez tous vos arbres Huffman.
C'est dire que nous allons avoir quelque chose qui s'appelle un complot
qui contient un pointeur sur un arbre, ainsi qu'un pointeur vers une parcelle suivante appelée.
Quelle est la structure fait ce genre de ressembler?
Il sorte de qu'il dit là-bas.
Par ici.
Une liste chaînée.
Nous voyons que lorsque nous avons un terrain, c'est comme une liste chaînée de parcelles.
Une forêt est défini comme une liste chaînée de parcelles,
et si la structure de la forêt, c'est que nous allons juste d'avoir un pointeur vers notre première parcelle
et que la parcelle a un arbre en son sein ou fait plutôt à un arbre
et pointe alors vers la parcelle suivante, ainsi de suite et ainsi de suite.
Pour faire une forêt que nous appelons mkforest.
Ensuite, nous avons quelques fonctions très utiles ici.
Nous avons choisir où vous passez dans une forêt, puis la valeur de retour est un * Arbre,
un pointeur vers un arbre.
Qu'est-ce médiator vous faire, c'est de se rendre dans la forêt que vous pointez
puis retirer un arbre avec la fréquence la plus basse de cette forêt
et puis vous donner le pointeur vers cet arbre.
Une fois que vous l'interception, l'arbre n'existe pas dans la forêt plus,
mais la valeur de retour est le pointeur vers cet arbre.
Ensuite, vous avez des plantes.
Pourvu que vous passez un pointeur vers un arbre qui a une fréquence non-0,
quelle plante va faire, c'est qu'il faudra la forêt, prendre l'arbre, et plante à l'intérieur de l'arbre de la forêt.
Ici, nous avons rmforest.
Semblable à enlever un arbre, qui, fondamentalement, libéré de tous nos arbres pour nous,
retirer la forêt sera tout libre contenue dans cette forêt.
>> Si nous regardons dans forest.c, nous allons attendre de voir au moins 1 commande rmtree là-dedans,
parce que, pour libérer de la mémoire dans la forêt si une forêt a des arbres qui s'y trouvent,
puis finalement vous allez avoir à enlever les arbres aussi.
Si nous regardons dans forest.c, nous avons notre mkforest, qui est comme nous le prévoyons.
Nous malloc choses.
On initialise la première parcelle dans la forêt comme NULL car elle est vide, pour commencer,
alors nous voyons choix, qui renvoie l'arbre avec le poids le plus faible, la fréquence la plus basse,
puis obtient débarrasser de ce noeud particulier qui pointe vers cet arbre et le prochain,
donc il faut que, sur la liste chaînée de la forêt.
Et puis, nous avons ici des plantes, qui insère un arbre dans la liste chaînée.
Quelle forêt ne tient-il joliment triées pour nous.
Et puis finalement, nous avons rmforest et, comme prévu, nous avons rmtree appelé là-bas.
>> En regardant le code de distribution à ce jour, huffile.c était probablement de loin le plus difficile à comprendre,
alors que les autres fichiers eux-mêmes étaient assez simples à suivre.
Grâce à notre connaissance des pointeurs et les listes chaînées et autres,
nous avons pu suivre assez bien.
Mais tout ce que nous devons vraiment faire en sorte que nous comprenons parfaitement ce sont les fichiers. H
parce que vous devez être appeler ces fonctions, traiter avec ces valeurs de retour,
alors assurez-vous de bien comprendre ce que l'action va être effectuée
chaque fois que vous appelez l'une de ces fonctions.
Mais en réalité, la compréhension à l'intérieur de celui-ci n'est pas tout à fait nécessaire parce que nous avons les fichiers. H.
Nous avons 2 fichiers plus laissés dans notre code de distribution.
>> Regardons décharge.
Dump par son commentaire ici prend un fichier compressé Huffman
puis traduit et dépôts de tous de son contenu à l'extérieur.
Ici, nous voyons qu'il appelle hfopen.
C'est une sorte de miroir de déposer entrée * = fopen,
puis vous passez à l'information.
Il est presque identique sauf qu'au lieu d'un fichier * vous êtes de passage dans un Huffile;
au lieu de fopen vous êtes de passage dans hfopen.
Ici, nous lisons dans le premier en-tête, ce qui est assez similaire à la façon dont nous lisons dans l'en-tête
pour un fichier bitmap.
Ce que nous faisons ici est de vérifier pour voir si les informations d'en-tête
contient le nombre magique droite qui indique que c'est un fichier réel Huff,
puis toutes ces vérifications afin de s'assurer que le fichier que nous est ouvert un fichier réel souffla ou non.
Que cela ne se fait-il émet les fréquences de tous les symboles que nous pouvons voir
sein d'un terminal dans un tableau graphique.
Cette partie va être utile.
Il a un peu et lit peu à peu dans le binaire variable et imprime ensuite sur.
Donc, si je devais appeler décharge sur hth.bin, qui est le résultat de sniffer un fichier
l'aide de la solution de personnel, je voudrais obtenir cela.
C'est la sortie de tous ces personnages et en mettant ensuite la fréquence à laquelle ils apparaissent.
Si l'on regarde, la plupart d'entre eux sont des 0 sauf pour ceci: H, qui apparaît deux fois,
puis T, qui apparaît une fois.
Et puis, nous avons ici le message réel en 0 et de 1.
Si nous regardons hth.txt, qui est sans doute le message original qui a été souffla,
nous nous attendons à voir Hs et Ts là-dedans.
Plus précisément, nous nous attendons à seulement 1 T et 2 Hs.
Ici, nous sommes dans hth.txt. Il a en effet HTH.
Inclus là-dedans, même si nous ne pouvons pas le voir, est un caractère de nouvelle ligne.
Le fichier hth.bin Huff est également codant pour le caractère de nouvelle ligne aussi bien.
Ici, parce que nous savons que l'ordre est HTH, puis retour à la ligne,
nous pouvons voir que, probablement, le H est représenté par un simple 1 lit simple
puis la T 01 est probablement puis la prochaine H est 1 et
et puis nous avons un retour à la ligne indiquée par deux 0.
Cool.
>> Et puis, enfin, parce que nous traitons multiple. C et les fichiers. H,
nous allons avoir un argument assez complexe pour le compilateur,
et donc nous avons ici un Makefile qui permet de vidage pour vous.
Mais en réalité, il faut s'y prendre pour faire votre propre fichier puff.c.
Le fichier Makefile ne fait pas face à puff.c faire pour vous.
Nous partons ce à vous de modifier le fichier Makefile.
Lorsque vous entrez une commande similaire à faire tous, par exemple, il fera tous pour vous.
N'hésitez pas à regarder les exemples de Makefile à partir du passé pset
ainsi que d'aller hors de celui-ci pour voir comment vous pourriez être en mesure de rendre votre fichier de Puff
en éditant ce Makefile.
C'est à ce sujet pour notre code de distribution.
>> Une fois que nous avons obtenu grâce à cela, alors voici juste un autre rappel
de la façon dont nous allons avoir affaire à des nœuds de Huffman.
Nous n'allons pas à les appeler nœuds plus, nous allons appeler les arbres
où nous allons représenter leur symbole avec un char,
leur fréquence, le nombre d'occurrences, d'un nombre entier.
Nous utilisons ce que parce qu'il est plus précise que celle d'un flotteur.
Et puis nous avons un autre pointeur vers le fils gauche ainsi que l'enfant le droit.
Une forêt, comme nous l'avons vu, est tout simplement une liste chaînée des arbres.
En fin de compte, lorsque nous construisons notre fichier Huff,
nous voulons que notre forêt pour contenir seulement 1 arbre -
1 arbre, 1 racine avec plusieurs enfants.
Un peu plus tôt, lorsque nous étions juste de rendre nos arbres Huffman,
nous avons commencé par placer tous les nœuds sur notre écran
et dire que nous allons avoir ces nœuds,
finalement, ils vont être les feuilles, ce qui est leur symbole, c'est leur fréquence.
Dans nos forêts si nous avons juste 3 lettres, c'est une forêt de 3 arbres.
Et puis, à mesure que nous, quand nous avons ajouté le premier parent,
nous avons fait une forêt de 2 arbres.
Nous avons supprimé 2 de ces enfants de notre forêt et l'a remplacé par un nœud parent
qui a eu ces 2 nœuds que les enfants.
Et puis enfin, notre dernière étape à faire de notre exemple avec l'As, Bs, Cs et
serait de rendre le parent finale,
et si alors ce serait apporter notre nombre total d'arbres dans la forêt à 1.
Est-ce que tout le monde voir comment vous commencez avec plusieurs arbres dans votre forêt
et se retrouvent avec 1? D'accord. Cool.
>> Que devons-nous faire pour Puff?
Ce que nous devons faire est de s'assurer que, comme toujours, ils nous donnent le bon type d'entrée
afin que nous puissions réellement exécuter le programme.
Dans ce cas, ils vont être nous donner après leur premier argument de la ligne de commande
2 plus: le fichier que l'on veut décompresser et la sortie du fichier décompressé.
Mais une fois que nous nous assurons qu'ils nous passent dans la bonne quantité de valeurs,
nous voulons nous assurer que l'entrée est un fichier Huff ou non.
Et puis une fois que nous garantissons qu'il s'agit d'un fichier Huff, alors que nous voulons construire notre arbre,
construire l'arbre de telle sorte qu'il épouse l'arbre que la personne qui a envoyé le message construit.
Puis, après nous construisons l'arbre, alors nous pouvons faire face à la, 0 et de 1 qui ils ont passé en
suivre ceux le long de notre arbre, car il est identique,
puis d'écrire ce message, interpréter les bits de nouveau dans les caractères.
Et puis à la fin, parce que nous avons affaire ici avec des pointeurs,
nous voulons nous assurer que nous n'avons pas de fuites de mémoire
et que nous tout gratuitement.
>> Assurer le bon usage est vieux chapeau pour nous maintenant.
Nous prenons en entrée, ce qui va être le nom du fichier à gonfler,
puis nous spécifions une sortie,
si le nom du fichier pour la sortie soufflé, qui est le fichier de texte.
C'est l'usage. Et maintenant, nous voulons nous assurer que l'entrée est souffla ou non.
En y repensant, c'était il ya quelque chose dans le code de distribution qui pourrait nous aider
à comprendre si un fichier est souffla ou non?
Il y avait des informations au sujet de la huffile.c Huffeader.
Nous savons que chaque fichier Huff a une Huffeader qui lui est associé avec un nombre magique
ainsi que d'un tableau de fréquences pour chaque symbole
ainsi que d'une somme de contrôle.
Nous le savons, mais nous avons aussi pris un coup d'oeil à dump.c,
dans lequel il a été lu dans un fichier Huff.
Et donc pour ce faire, il fallait vérifier si elle était vraiment souffla ou non.
Alors peut-être que nous pourrions utiliser dump.c comme une structure pour notre puff.c.
Retour à pset 4 lorsque nous avons eu l'copy.c fichier copié dans les triplets RGB
et nous avons interprété que pour Whodunit et de redimensionnement,
de même, ce que vous pourriez faire est de simplement exécuter la commande comme cp dump.c puff.c
et utiliser une partie du code là-bas.
Cependant, il ne va pas être aussi simple d'un processus
pour la traduction de votre dump.c en puff.c,
mais au moins il vous donne un endroit pour commencer
sur la façon de faire en sorte que l'entrée est effectivement ou non huffed
ainsi que quelques autres choses.
Nous avons veillé à l'utilisation appropriée et veiller à ce que l'entrée est souffla.
Chaque fois que nous avons fait ce que nous avons fait notre vérification d'erreur appropriée,
afin de retourner et quitter la fonction si une défaillance se produit, si il ya un problème.
>> Maintenant, ce que nous voulons faire est de construire l'arbre réel.
Si nous regardons dans la forêt, il ya 2 fonctions principales
que nous allons vouloir devenir très familier avec.
Il ya l'usine de fonction booléenne qui plante un arbre de fréquence non-0 à l'intérieur de notre forêt.
Et alors là vous passez un pointeur vers une forêt et un pointeur vers un arbre.
Petite question: Combien de forêts que vous avez quand vous construisez un arbre de Huffman?
Notre forêt est comme notre toile, non?
Donc, nous allons seulement avoir 1 forêt, mais nous allons avoir plusieurs arbres.
Alors avant de vous appeler usine, vous êtes sans doute allez avoir à faire de votre forêt.
Il existe une commande pour que, si vous regardez dans forest.h sur la façon dont vous pouvez faire une forêt.
Vous pouvez planter un arbre. Nous savons comment le faire.
Et puis, vous pouvez aussi choisir un arbre de la forêt,
la suppression d'un arbre avec le moins de poids et en vous donnant le pointeur à cela.
En repensant au moment où nous faisions les exemples nous-mêmes,
quand nous avons été le tirer, il suffit juste d'ajouter les liens.
Mais ici, au lieu de simplement ajouter des liens,
pense qu'il est plus que vous retirez 2 de ces nœuds, puis le remplacer par un autre.
Pour exprimer cela en termes de récolte et de plantation,
vous vous en prenez 2 arbres et la plantation d'un autre arbre
qui a ces 2 arbres que vous avez sélectionnés comme des enfants.
Pour construire l'arbre de Huffman, vous pouvez lire dans les symboles et les fréquences afin
parce que le Huffeader donne que pour vous,
vous donne un tableau des fréquences.
Ainsi, vous pouvez aller de l'avant et simplement ignorer quoi que ce soit avec le 0 dans l'
parce que nous ne voulons pas 256 feuilles à la fin de celui-ci.
Nous voulons seulement le nombre de feuilles qui sont des caractères
qui sont effectivement utilisées dans le fichier.
Vous pouvez lire ces symboles, et chacun de ces symboles qui ont des fréquences-0,
ceux qui vont être les arbres.
Ce que vous pouvez faire, c'est à chaque fois que vous lisez dans un symbole de fréquence non-0,
vous pouvez planter cet arbre dans la forêt.
Une fois que vous planter les arbres dans la forêt, vous pouvez joindre ces arbres comme frères et sœurs,
Pour en revenir à la plantation et la cueillette où vous choisissez 2, puis l'usine 1,
où ce 1 que vous avez usine est la mère des 2 enfants que vous avez sélectionnés.
Alors votre résultat final va être un seul arbre dans votre forêt.
C'est ainsi que vous construisez votre arbre.
>> Il ya plusieurs choses qui pourraient aller mal ici
parce que nous avons affaire à faire de nouveaux arbres et de traiter avec des pointeurs et des choses comme ça.
Avant, quand nous avions affaire à des pointeurs,
chaque fois que nous malloc nous voulions pour s'assurer qu'il n'avait pas de nous retourner une valeur de pointeur NULL.
Ainsi, à plusieurs étapes dans ce processus, il va y avoir plusieurs cas
où votre programme risque d'échouer.
Qu'est-ce que vous voulez faire, c'est que vous voulez vous assurer que vous manipulez ces erreurs,
et dans les spécifications il est dit de les manipuler avec élégance,
si semblable à imprimer un message à l'utilisateur de leur dire pourquoi le programme doit quitter
puis rapidement le quitter.
Pour ce faire, la gestion des erreurs, n'oubliez pas que vous voulez le vérifier
chaque fois qu'il pourrait y avoir un échec.
Chaque fois que vous faites un nouveau pointeur
vous voulez vous assurer que c'est réussi.
Avant que nous l'habitude de faire, c'est de faire un nouveau pointeur et malloc il,
puis nous vérifions si ce pointeur est NULL.
Donc, il va y avoir des cas où il vous suffit de le faire,
mais parfois vous êtes en train d'appeler une fonction
et, dans cette fonction, c'est celui qui fait le allouer de.
Dans ce cas, si nous regardons en arrière à certains des fonctions dans le code,
certains d'entre eux sont des fonctions booléennes.
Dans le cas abstrait si nous avons une fonction booléenne appelée foo,
fondamentalement, on peut supposer que, en plus de faire tout ce qui ne foo,
puisque c'est une fonction booléenne, elle retourne vrai ou faux -
vrai en cas de succès, false sinon.
Donc, nous voulons vérifier si la valeur de retour de toto est vraie ou fausse.
Si elle est fausse, cela signifie que nous allons souhaitez imprimer une sorte de message
puis quittez le programme.
Ce que nous voulons faire est de vérifier la valeur de retour de foo.
Si foo renvoie false, alors nous savons que nous avons rencontré un certain genre d'erreur
et nous devons quitter notre programme.
Une façon de le faire est d'avoir un état où la fonction elle-même est votre état de santé.
Dites foo prend en x.
Nous pouvons avoir en tant que condition if (foo (x)).
Fondamentalement, cela signifie que si à la fin de l'exécution de foo elle renvoie true,
alors nous pouvons le faire parce que la fonction doit évaluer foo
afin d'évaluer l'état entier.
Alors c'est comme ça que vous pouvez faire quelque chose si la fonction renvoie true et est couronnée de succès.
Mais quand vous êtes vérification des erreurs, vous ne voulez cesser de fumer si votre fonction retourne false.
Qu'est-ce que vous pourriez faire est de simplement ajouter un == false ou tout simplement ajouter un coup en face d'elle
et puis vous avez if (! foo).
Au sein de ce corps d'état qui vous aurait tout de la gestion des erreurs,
si semblable, "Impossible de créer cet arbre", puis retourner 1 ou quelque chose comme ça.
Qu'est-ce qui fait, cependant, c'est que même si foo a retourné false -
Dites foo retourne true.
Ensuite, vous n'avez pas à appeler foo nouveau. C'est une idée fausse très répandue.
Parce que c'était dans votre état, il est déjà évaluée,
si vous avez déjà le résultat si vous utilisez rendre arbre ou quelque chose comme ça
des végétaux ou des choix ou quelque chose.
Il a déjà cette valeur. Il est déjà exécuté.
Il est donc utile d'utiliser des fonctions booléennes comme la condition
car si on fait exécuter le corps de la boucle,
il exécute la fonction de toute façon.
>> Notre deuxième à la dernière étape est la rédaction du message dans le fichier.
Une fois que nous construisons l'arbre de Huffman, puis écrire le message dans le fichier est assez simple.
C'est assez simple maintenant il suffit de suivre le 0 et de 1.
Et donc, par convention, nous savons que dans un arbre de Huffman les 0 indiquent gauche
et les 1 indiquent droite.
Alors, si vous avez lu dans peu à peu, à chaque fois que vous obtenez un 0
vous suivez la branche gauche, puis à chaque fois que vous avez lu dans un 1
vous allez suivre la branche droite.
Et puis vous allez continuer jusqu'à ce que vous appuyez sur une feuille
parce que les feuilles vont être à l'extrémité des branches.
Comment pouvons-nous dire si nous avons touché une feuille ou pas?
Nous l'avons dit auparavant.
[L'élève] Si les pointeurs sont NULL. Ouais >>.
Nous ne pouvons dire si nous avons touché une feuille si les pointeurs vers les arbres à la fois la gauche et de droite sont NULL.
Parfait.
Nous savons que nous voulons lire dans peu à peu dans notre fichier Huff.
Comme nous l'avons vu dans dump.c, ce qu'ils ont fait est qu'ils ont lu dans peu à peu dans le fichier Huff
et vient d'être imprimée sur ce que ces morceaux étaient.
Nous n'allons pas faire cela. Nous allons faire quelque chose qui est un peu plus complexe.
Mais ce que nous pouvons faire, c'est que nous pouvons prendre que peu de code qui lit le bit.
Ici, nous avons le bit entier représentant le bit courant que nous sommes.
Cela prend soin d'itérer tous les bits dans le fichier jusqu'à ce que vous atteignez la fin du fichier.
Sur cette base, alors vous allez vouloir avoir une sorte d'itérateur
pour parcourir votre arborescence.
Puis, selon que le bit est 0 ou 1,
vous allez avoir à se déplacer soit que itérateur vers la gauche ou vers la droite
tout le chemin jusqu'à ce que vous appuyez sur une feuille, donc tout le chemin jusqu'à ce que le noeud que vous êtes sur
ne dirigez pas vers les ganglions, pas plus.
Pourquoi peut-on faire avec un fichier de Huffman mais pas le code Morse?
Parce que dans le code Morse, il ya un peu d'ambiguïté.
Nous pourrions être comme, oh wait, nous avons touché une lettre le long du chemin, donc c'est peut-être notre lettre,
tandis que si nous avons continué un peu plus longtemps, nous aurions atteint une autre lettre.
Mais cela ne va pas se produire dans le codage de Huffman,
si nous pouvons être assurés que la seule façon que nous allons frapper un caractère
est de savoir si les enfants gauche et à droite de ce nœud sont NULL.
>> Enfin, nous voulons libérer l'ensemble de notre mémoire.
Nous voulons à la fois proche du dossier Huff que nous avons eu affaire à
ainsi que de supprimer tous les arbres de notre forêt.
Selon votre application, vous allez probablement vouloir appeler retirer la forêt
au lieu de réellement passer par tous les arbres vous-même.
Mais si vous avez effectué des arbres temporaires, vous aurez envie de libérer ça.
Vous savez que votre meilleur code, si vous savez où vous allouez de la mémoire.
Et si vous y aller, commencer par f'ing même contrôle pour malloc,
voir chaque fois que vous malloc et faire en sorte que vous libérer de tout cela
mais alors juste en passant par votre code,
comprendre où vous pourriez avoir la mémoire allouée.
Habituellement, vous pourriez dire: «A la fin d'un fichier, je vais juste enlever la forêt sur ma forêt»,
Donc, fondamentalement, effacer cette mémoire, sans que,
»Et puis je vais aussi fermez le fichier, puis mon programme va quitter."
Mais est-ce la seule fois que votre programme se termine?
Non, parce que parfois il peut y avoir eu une erreur qui s'est produite.
Peut-être que nous ne pouvions pas ouvrir un fichier ou nous ne pouvions pas faire un autre arbre
ou une sorte d'erreur qui s'est passé dans le processus d'allocation de mémoire et il a retourné NULL.
Une erreur s'est produite, puis nous sommes rentrés et quitter.
Alors, vous voulez vous assurer que chaque fois que possible que votre programme peut cesser de fumer,
vous voulez libérer toute votre mémoire là-bas.
Ce n'est pas seulement va être à la fin de la fonction principale que vous quittez votre code.
Vous voulez regarder en arrière à chaque fois que votre code potentiellement pourraient rentrer prématurément
et puis libérer toute la mémoire du sens.
Dites que vous l'aviez appelé make forêt et qui a retourné false.
Ensuite, vous n'aurez probablement pas besoin de retirer votre forêt
parce que vous n'avez pas encore une forêt.
Mais à chaque point dans le code où vous pourriez rentrer prématurément
vous voulez vous assurer que vous libérer de la mémoire possible.
>> Alors, quand nous avons affaire à libérer de la mémoire et ayant des fuites potentielles,
nous voulons non seulement d'utiliser notre jugement et notre logique
mais aussi utiliser Valgrind pour déterminer si nous avons libéré l'ensemble de notre mémoire correctement ou non.
Vous pouvez soit exécuter Valgrind sur Puff puis vous devez également passer
le bon nombre de ligne de commande arguments pour Valgrind.
Vous pouvez exécuter, mais le résultat est un peu cryptique.
Nous avons obtenu un peu habitués à Speller, mais nous avons encore besoin d'une aide un peu plus,
donc il fonctionne avec quelques drapeaux plus comme la fuite-check = plein,
qui va probablement nous donner une sortie plus utile sur Valgrind.
>> Puis une autre astuce utile lorsque vous déboguez est la commande diff.
Vous pouvez accéder à la mise en œuvre du personnel de Huff, l'exécuter sur un fichier texte,
puis une sortie vers un fichier binaire, un fichier binaire Huff, pour être précis.
Alors, si vous exécutez votre propre souffle sur ce fichier binaire,
puis idéalement, votre fichier texte fourni en sortie va être identiques
à celui d'origine que vous avez passé po
Ici, j'utilise hth.txt comme exemple, et c'est celui parlé dans votre spec.
C'est littéralement juste HTH, puis un retour à la ligne.
Mais certainement se sentir libre et vous êtes certainement encouragés à utiliser plus d'exemples
pour votre fichier texte.
>> Vous pouvez même prendre une photo à la compression et peut-être puis décompresser
certains des fichiers que vous avez utilisés dans Speller comme Guerre et Paix
ou Jane Austen ou quelque chose comme ça - ce serait plutôt cool - ou Austin Powers,
sorte de traiter des fichiers plus volumineux, car nous ne descende pas pour elle
si nous avons utilisé l'outil suivant ici, ls-l.
Nous sommes habitués à ls, qui répertorie tous les contenus essentiellement dans notre répertoire courant.
En passant le drapeau-l affiche en fait la taille de ces fichiers.
Si vous passez par la spécification pset, il marche en fait, vous en créant le fichier binaire,
de lui soufflant, et vous voyez que pour de très petits fichiers
le coût de l'espace en le comprimant et la traduction de l'ensemble de ces informations
de toutes les fréquences et les choses comme ça l'emporte sur le bénéfice réel
de compression du fichier, en premier lieu.
Mais si vous l'exécutez sur des fichiers texte plus long, alors vous pourriez voir que vous commencez à obtenir un certain avantage
en comprimant les fichiers.
>> Et puis finalement, nous avons notre GDB vieux copain, qui va certainement venir dans maniable aussi.
>> Avons-nous des questions sur les arbres Huff ou le processus peut-être de rendre les arbres
ou d'autres questions sur Puff Huff'n?
D'accord. Je vais rester autour pour un peu.
>> Merci à tous. Ce fut Procédure pas à pas 6. Et bonne chance.
>> [CS50.TV]