1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Procédure pas à pas - 6 Set problème]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Université de Harvard]

3
00:00:04,810 --> 00:00:07,240
[C'est CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Bonjour à tous et bienvenue dans Procédure pas à pas 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
En Puff Huff'n ce que nous faisons va avoir affaire à un fichier compressé Huffman

6
00:00:17,440 --> 00:00:20,740
puis souffler en arrière, donc le décompresser,

7
00:00:20,740 --> 00:00:25,810
afin que nous puissions traduire du 0 et de 1 que l'utilisateur envoie-nous

8
00:00:25,810 --> 00:00:30,660
et le reconvertir dans le texte original.

9
00:00:30,660 --> 00:00:34,360
Pset 6 va être assez cool parce que vous allez voir quelques-uns des outils

10
00:00:34,360 --> 00:00:41,730
que vous avez utilisé dans pset pset 4 et 5 et sorte de les combiner en 1 concept très soigné

11
00:00:41,730 --> 00:00:43,830
quand vous venez d'y penser.

12
00:00:43,830 --> 00:00:50,110
>> De plus, sans doute, pset 4 et 5 sont les plus difficiles psets que nous avions à offrir.

13
00:00:50,110 --> 00:00:53,950
A partir de maintenant, nous avons cette pset 1 plus dans C,

14
00:00:53,950 --> 00:00:56,480
puis, après que nous sommes sur la programmation web.

15
00:00:56,480 --> 00:01:02,310
Alors vous féliciter pour avoir surmonté le plus dur bosse CS50.

16
00:01:03,630 --> 00:01:09,760
>> Passant pour Puff Huff'n, notre boîte à outils pour ce pset vont être les arbres de Huffman,

17
00:01:09,760 --> 00:01:14,700
afin de comprendre non seulement comment le travail arbres binaires, mais aussi en particulier des arbres de Huffman,

18
00:01:14,700 --> 00:01:16,240
comment ils sont construits.

19
00:01:16,240 --> 00:01:20,210
Et puis nous allons avoir beaucoup de code de la distribution dans ce jeu de processeurs,

20
00:01:20,210 --> 00:01:22,480
et nous viendrons à voir ce que fait une partie du code

21
00:01:22,480 --> 00:01:24,670
nous pourrions ne pas être en mesure de bien comprendre encore,

22
00:01:24,670 --> 00:01:30,080
et si ceux-ci seront les fichiers. c, mais qui les accompagnent. h dossiers

23
00:01:30,080 --> 00:01:34,300
nous donnera assez de compréhension que nous avons besoin afin que nous sachions comment ces fonctions sont

24
00:01:34,300 --> 00:01:38,100
ou du moins ce qu'ils sont censés faire - leurs entrées et sorties -

25
00:01:38,100 --> 00:01:40,760
même si nous ne savons pas ce qui se passe dans la boîte noire

26
00:01:40,760 --> 00:01:44,090
ou ne comprennent pas ce qui se passe dans la boîte noire à l'intérieur.

27
00:01:44,090 --> 00:01:49,400
Et puis finalement, comme d'habitude, nous avons affaire à des structures de données nouvelles,

28
00:01:49,400 --> 00:01:51,840
certains types de nœuds qui pointent vers certaines choses,

29
00:01:51,840 --> 00:01:56,080
et voici donc avoir un stylo et du papier, non seulement pour le processus de conception

30
00:01:56,080 --> 00:01:58,470
et quand vous êtes à essayer de comprendre comment votre pset devrait fonctionner

31
00:01:58,470 --> 00:02:00,520
mais aussi pendant le débogage.

32
00:02:00,520 --> 00:02:06,140
Vous pouvez avoir GDB à côté de votre stylo et du papier pendant que vous prenez vers le bas quelles sont les valeurs,

33
00:02:06,140 --> 00:02:09,320
où vos flèches pointent, et des choses comme ça.

34
00:02:09,320 --> 00:02:13,720
>> Premièrement, regardons les arbres de Huffman.

35
00:02:13,720 --> 00:02:19,600
Arbres Huffman sont des arbres binaires, ce qui signifie que chaque nœud possède seulement 2 enfants.

36
00:02:19,600 --> 00:02:24,870
Dans les arbres de Huffman la caractéristique est que les valeurs les plus fréquentes

37
00:02:24,870 --> 00:02:27,140
sont représentés par le plus petit nombre de bits.

38
00:02:27,140 --> 00:02:32,690
Nous avons vu dans les exemples de cours de code Morse, qui sorte de synthèse des lettres.

39
00:02:32,690 --> 00:02:38,030
Si vous essayez de traduire un A ou un E, par exemple,

40
00:02:38,030 --> 00:02:43,940
vous traduisez que souvent, au lieu d'avoir à utiliser l'ensemble de bits

41
00:02:43,940 --> 00:02:48,640
alloué pour ce type d'habitude les données, vous le compresser jusqu'à moins,

42
00:02:48,640 --> 00:02:53,730
puis ces lettres qui sont représentés sont moins souvent représenté avec plus de bits

43
00:02:53,730 --> 00:02:59,840
parce que vous pouvez vous permettre que lorsque vous pesez sur les fréquences que ces lettres apparaissent.

44
00:02:59,840 --> 00:03:03,020
Nous avons la même idée ici dans les arbres de Huffman

45
00:03:03,020 --> 00:03:12,360
où nous faisons une chaîne, une sorte de chemin pour arriver aux certains caractères.

46
00:03:12,360 --> 00:03:14,470
Et puis les personnages qui ont le plus de fréquence

47
00:03:14,470 --> 00:03:17,940
vont être représenté avec le moins de bits.

48
00:03:17,940 --> 00:03:22,020
>> La façon dont vous construisez un arbre de Huffman

49
00:03:22,020 --> 00:03:27,430
est de placer tous les personnages qui apparaissent dans le texte

50
00:03:27,430 --> 00:03:30,630
et le calcul de leur fréquence, combien de fois ils apparaissent.

51
00:03:30,630 --> 00:03:33,880
Il peut s'agir d'un compte de combien de fois ces lettres apparaissent

52
00:03:33,880 --> 00:03:40,270
ou peut-être un pourcentage de rupture de tous les caractères combien chacun apparaît.

53
00:03:40,270 --> 00:03:44,270
Et qu'est-ce que vous faites est une fois que vous avez tout cela sur cartographiés,

54
00:03:44,270 --> 00:03:49,060
puis vous regardez pour les 2 fréquences les plus basses, puis de les rejoindre en tant que frères et sœurs

55
00:03:49,060 --> 00:03:55,660
où le noeud parent a une fréquence qui est la somme de ses 2 enfants.

56
00:03:55,660 --> 00:04:00,870
Et puis vous dire que, par convention, le noeud gauche,

57
00:04:00,870 --> 00:04:03,770
que vous suivez par la suite la branche 0,

58
00:04:03,770 --> 00:04:08,140
puis le nœud le plus à droite est la branche 1.

59
00:04:08,140 --> 00:04:16,040
Comme nous l'avons vu dans le code Morse, le gotcha-ci était que si vous aviez juste un bip et le bip

60
00:04:16,040 --> 00:04:18,120
il était ambiguë.

61
00:04:18,120 --> 00:04:22,430
Elle peut soit être une lettre ou il pourrait s'agir d'une séquence de 2 lettres.

62
00:04:22,430 --> 00:04:27,790
Et qu'est-ce Huffman arbres ne c'est parce que, par nature, des personnages

63
00:04:27,790 --> 00:04:34,140
ou finaux nos personnages réels étant les derniers noeuds sur la branche -

64
00:04:34,140 --> 00:04:39,300
nous nous référons à ceux que les feuilles - en vertu de cela, il ne peut pas y avoir d'ambiguïté

65
00:04:39,300 --> 00:04:45,160
aux termes de laquelle la lettre que vous essayez d'encoder avec la suite de bits

66
00:04:45,160 --> 00:04:50,670
parce que nulle part le long des bits qui représentent 1 lettre

67
00:04:50,670 --> 00:04:55,960
vous rencontrez une autre lettre ensemble, et il n'y aura pas de confusion.

68
00:04:55,960 --> 00:04:58,430
Mais nous irons dans des exemples que vous les gars pouvez réellement voir ce que

69
00:04:58,430 --> 00:05:02,120
au lieu de nous juste vous dire que c'est vrai.

70
00:05:02,120 --> 00:05:06,390
>> Voyons un exemple simple d'un arbre de Huffman.

71
00:05:06,390 --> 00:05:09,380
J'ai ici une chaîne qui est de 12 caractères.

72
00:05:09,380 --> 00:05:14,010
Comme j'ai 4, 6 chambres et 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Ma première étape serait de compter.

74
00:05:17,270 --> 00:05:20,760
Combien de fois ne semblent Une? Il apparaît 4 fois dans la chaîne.

75
00:05:20,760 --> 00:05:25,060
B apparaît 6 fois, et C apparaît 2 fois.

76
00:05:25,060 --> 00:05:28,970
Naturellement, je vais dire que je suis l'aide de B le plus souvent,

77
00:05:28,970 --> 00:05:35,970
si je veux représenter B avec le plus petit nombre de bits, le nombre minimum de 0 et de 1.

78
00:05:35,970 --> 00:05:42,600
Et puis je vais aussi s'attendre C à exiger la plus grande quantité de 0 et de 1 aussi.

79
00:05:42,600 --> 00:05:48,550
D'abord ce que j'ai fait ici est je les ai mis dans l'ordre croissant en termes de fréquence.

80
00:05:48,550 --> 00:05:52,710
Nous voyons que la C et A, ce sont nos 2 fréquences les plus basses.

81
00:05:52,710 --> 00:06:00,290
Nous créons un noeud parent, et ce nœud parent n'a pas une lettre qui lui est associée,

82
00:06:00,290 --> 00:06:05,070
mais il a une fréquence qui est la somme.

83
00:06:05,070 --> 00:06:08,780
La somme devient 2 + 4, qui est la 6.

84
00:06:08,780 --> 00:06:10,800
Puis nous suivons la branche gauche.

85
00:06:10,800 --> 00:06:14,970
Si nous étions à ce noeud 6, puis nous suivrons 0 pour obtenir à C

86
00:06:14,970 --> 00:06:17,450
puis 1 pour se rendre à A.

87
00:06:17,450 --> 00:06:20,300
Nous avons donc maintenant 2 noeuds.

88
00:06:20,300 --> 00:06:23,920
Nous avons la valeur 6, puis nous avons aussi un autre nœud avec la valeur 6.

89
00:06:23,920 --> 00:06:28,550
Et si les 2 ne sont pas seulement le plus bas 2, mais aussi tout simplement les 2 qui restent,

90
00:06:28,550 --> 00:06:33,820
C'est pourquoi, avec celles de l'autre parent, avec la somme de 12.

91
00:06:33,820 --> 00:06:36,300
Nous avons donc ici notre arbre de Huffman

92
00:06:36,300 --> 00:06:40,020
où se rendre à B, qui ne serait que le bit 1

93
00:06:40,020 --> 00:06:45,430
et puis vous rendre à nous aurions 01 puis C ayant 00.

94
00:06:45,430 --> 00:06:51,300
Donc, ici, nous voyons que, fondamentalement, nous représentons ces caractères avec 1 ou 2 bits

95
00:06:51,300 --> 00:06:55,160
où le B, comme prévu, a tout le moins.

96
00:06:55,160 --> 00:07:01,730
Et puis nous nous attendions à C comptent le plus, mais puisque c'est comme un petit arbre de Huffman,

97
00:07:01,730 --> 00:07:06,020
puis l'un est aussi représenté par 2 bits au lieu de quelque part au milieu.

98
00:07:07,820 --> 00:07:11,070
>> Juste pour revenir sur un autre exemple simple de l'arbre de Huffman,

99
00:07:11,070 --> 00:07:19,570
dire que vous avez la chaîne "Bonjour".

100
00:07:19,570 --> 00:07:25,360
Ce que vous faites est d'abord vous dire combien de fois ne H apparaissent dans cette?

101
00:07:25,360 --> 00:07:34,200
H apparaît une fois et puis e apparaît une fois et puis nous avons l apparaissant deux fois

102
00:07:34,200 --> 00:07:36,580
o et apparaissant une fois.

103
00:07:36,580 --> 00:07:44,310
Et alors nous nous attendons à laquelle la lettre doit être représenté par le plus petit nombre de bits?

104
00:07:44,310 --> 00:07:47,450
[L'élève] l. L >>. Ouais. l est à droite.

105
00:07:47,450 --> 00:07:50,730
Nous nous attendons l d'être représentés par le plus petit nombre de bits

106
00:07:50,730 --> 00:07:55,890
parce que l est le plus utilisé dans la chaîne "Bonjour".

107
00:07:55,890 --> 00:08:04,280
Ce que je vais faire maintenant est de faire ressortir ces nœuds.

108
00:08:04,280 --> 00:08:15,580
J'ai 1, qui est H, puis une autre 1, qui est e, puis un 1, qui est o -

109
00:08:15,580 --> 00:08:23,410
en ce moment je leur mise au point - puis 2, qui est l.

110
00:08:23,410 --> 00:08:32,799
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

111
00:08:32,799 --> 00:08:38,010
et de les rendre frères et sœurs en créant un nœud parent.

112
00:08:38,010 --> 00:08:41,850
Ici, nous avons 3 noeuds avec la plus basse fréquence. Ils sont tous 1.

113
00:08:41,850 --> 00:08:50,620
Nous voilà donc choisir celui qui nous allons relier premier.

114
00:08:50,620 --> 00:08:54,850
Disons que je choisis le H et le e.

115
00:08:54,850 --> 00:09:01,150
La somme de 1 + 1 = 2, mais ce noeud n'a pas de lettre qui lui est associée.

116
00:09:01,150 --> 00:09:04,440
Il détient un peu la valeur.

117
00:09:04,440 --> 00:09:10,950
Maintenant, nous regardons les 2 prochaines fréquences les plus basses.

118
00:09:10,950 --> 00:09:15,590
Ce sont 2 et 1. Cela pourrait être l'un de ceux 2, mais je vais choisir celui-ci.

119
00:09:15,590 --> 00:09:18,800
La somme est 3.

120
00:09:18,800 --> 00:09:26,410
Et puis finalement, je n'ai que 2 à gauche, si cela devient 5.

121
00:09:26,410 --> 00:09:32,010
Alors voilà, comme prévu, si je remplis dans le codage pour cela,

122
00:09:32,010 --> 00:09:37,480
1s sont toujours la branche de droite et de 0 sont celle de gauche.

123
00:09:37,480 --> 00:09:45,880
Ensuite, nous avons l représentée par seulement 1 bit, puis le joint de 2

124
00:09:45,880 --> 00:09:52,360
et ensuite la 2 e par le H puis retombe à 3 bits.

125
00:09:52,360 --> 00:09:59,750
Ainsi, vous pouvez transmettre ce message "Bonjour" au lieu d'utiliser effectivement les caractères

126
00:09:59,750 --> 00:10:02,760
simplement en 0 et de 1.

127
00:10:02,760 --> 00:10:07,910
Cependant, rappelez-vous que dans plusieurs cas nous avons eu des liens avec notre fréquence.

128
00:10:07,910 --> 00:10:11,900
Nous aurions pu soit rejoint le H et le premier peut-être o.

129
00:10:11,900 --> 00:10:15,730
Ou alors plus tard, quand nous avons eu la l représenté par 2

130
00:10:15,730 --> 00:10:19,410
ainsi que le joint représenté par une 2, on aurait pu liés soit une.

131
00:10:19,410 --> 00:10:23,630
>> Et donc quand vous envoyez le 0 et de 1, cela ne fait pas une garantie

132
00:10:23,630 --> 00:10:27,090
que le destinataire peut lire entièrement votre message dès le départ

133
00:10:27,090 --> 00:10:30,490
car ils risquent de ne pas savoir quelle décision que vous avez fait.

134
00:10:30,490 --> 00:10:34,920
Alors, quand nous avons affaire à une compression de Huffman,

135
00:10:34,920 --> 00:10:40,090
en quelque sorte, nous devons informer le destinataire de notre message que nous avons décidé -

136
00:10:40,090 --> 00:10:43,470
Ils ont besoin de savoir un certain genre d'information supplémentaire

137
00:10:43,470 --> 00:10:46,580
en plus du message compressé.

138
00:10:46,580 --> 00:10:51,490
Ils ont besoin de comprendre ce que l'arbre ressemble réellement,

139
00:10:51,490 --> 00:10:55,450
comment nous pris ces décisions.

140
00:10:55,450 --> 00:10:59,100
>> Ici, nous ne faisions que des exemples basés sur le nombre réel,

141
00:10:59,100 --> 00:11:01,550
mais parfois vous pouvez aussi avoir un arbre de Huffman

142
00:11:01,550 --> 00:11:05,760
basée sur la fréquence à laquelle les lettres apparaissent, et c'est le même processus.

143
00:11:05,760 --> 00:11:09,090
Ici, je vais l'exprimer en termes de pourcentage ou une fraction,

144
00:11:09,090 --> 00:11:11,290
et voici donc exactement la même chose.

145
00:11:11,290 --> 00:11:15,300
Je trouve la plus faible 2, les résumer, les 2 plus basse suivante, les résumer,

146
00:11:15,300 --> 00:11:19,390
jusqu'à ce que j'aie un arbre complet.

147
00:11:19,390 --> 00:11:23,610
Même si nous pourrions le faire de toute façon, quand nous traitons avec des pourcentages,

148
00:11:23,610 --> 00:11:27,760
cela signifie que nous sommes diviser les choses et de traiter avec des décimales ou plutôt flotte

149
00:11:27,760 --> 00:11:30,900
si nous pensons à des structures de données d'une tête.

150
00:11:30,900 --> 00:11:32,540
Que savons-nous sur les flotteurs?

151
00:11:32,540 --> 00:11:35,180
Qu'est-ce qu'un problème commun quand nous traitons avec des flotteurs?

152
00:11:35,180 --> 00:11:38,600
[L'élève] arithmétique imprécise. Ouais >>. L'imprécision.

153
00:11:38,600 --> 00:11:43,760
En raison de l'imprécision virgule flottante, pour ce pset afin que nous nous assurions

154
00:11:43,760 --> 00:11:49,450
que nous ne perdons pas toutes les valeurs, alors nous allons en fait avoir affaire avec le comte.

155
00:11:49,450 --> 00:11:54,880
Donc, si vous deviez penser à un nœud de Huffman, si vous regardez en arrière à la structure ici,

156
00:11:54,880 --> 00:12:01,740
si vous regardez les verts il a une fréquence qui lui est associé

157
00:12:01,740 --> 00:12:08,760
aussi bien qu'il pointe vers un nœud à sa gauche, ainsi que d'un noeud à sa droite.

158
00:12:08,760 --> 00:12:13,970
Et puis il ya les rouges ont également un caractère qui leur est associée.

159
00:12:13,970 --> 00:12:18,900
Nous n'allons pas faire de séparés pour les parents, puis les nœuds finaux,

160
00:12:18,900 --> 00:12:23,680
que nous appelons les feuilles, mais plutôt ceux qui vont juste avoir la valeur NULL.

161
00:12:23,680 --> 00:12:31,050
Pour chaque nœud, nous aurons un caractère, le symbole que représente ce nœud,

162
00:12:31,050 --> 00:12:40,490
alors une fréquence, ainsi qu'un pointeur vers son enfant gauche et droite de son enfant.

163
00:12:40,490 --> 00:12:45,680
Les feuilles, qui sont tout en bas, aurait également pointeurs de noeuds

164
00:12:45,680 --> 00:12:49,550
à leur gauche et à leur droite, mais puisque ces valeurs ne sont pas orientées vers des noeuds réels,

165
00:12:49,550 --> 00:12:53,970
quelle serait leur valeur soit? >> [L'élève] NULL. NULL >>. Exactement.

166
00:12:53,970 --> 00:12:58,430
Voici un exemple de la façon dont vous pouvez représenter la fréquence de flotteurs,

167
00:12:58,430 --> 00:13:02,130
mais nous allons y faire face avec des nombres entiers,

168
00:13:02,130 --> 00:13:06,780
donc tout ce que je fait est de changer le type de données là-bas.

169
00:13:06,780 --> 00:13:09,700
>> Passons maintenant à un peu plus d'un exemple complexe.

170
00:13:09,700 --> 00:13:13,360
Mais maintenant que nous avons fait les plus simples, c'est juste le même processus.

171
00:13:13,360 --> 00:13:20,290
Vous trouverez les 2 fréquences les plus basses, la somme des fréquences

172
00:13:20,290 --> 00:13:22,450
et c'est la nouvelle fréquence de votre noeud parent,

173
00:13:22,450 --> 00:13:29,310
qui pointe alors à sa gauche avec la branche 0 et le droit à la branche 1.

174
00:13:29,310 --> 00:13:34,200
Si nous avons la chaîne "C'est CS50", alors nous compter combien de fois est mentionnée T,

175
00:13:34,200 --> 00:13:38,420
h mentionné, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Alors qu'est-ce que j'ai fait ici est avec les nœuds rouges que je viens plantés,

177
00:13:42,010 --> 00:13:48,530
J'ai dit que je vais avoir fini ces caractères au bas de mon arbre.

178
00:13:48,530 --> 00:13:51,740
Ceux vont être toutes les feuilles.

179
00:13:51,740 --> 00:13:58,200
Ensuite, ce que j'ai fait, c'est que je les trier par fréquence en ordre croissant,

180
00:13:58,200 --> 00:14:02,950
et c'est en fait la façon dont le code pset il ne

181
00:14:02,950 --> 00:14:07,550
est-ce qu'il trie par fréquence puis par ordre alphabétique.

182
00:14:07,550 --> 00:14:13,870
Ainsi, il a les chiffres d'abord, puis par ordre alphabétique de la fréquence.

183
00:14:13,870 --> 00:14:18,520
Alors qu'est-ce que je ferais, c'est que je ne trouve plus bas 2. C'est 0 et 5.

184
00:14:18,520 --> 00:14:22,390
Je les résume, et c'est 2. Ensuite, je voudrais continuer, trouver les 2 prochaines bas.

185
00:14:22,390 --> 00:14:26,100
Ce sont les 1 deux, puis ceux-ci deviennent 2 ainsi.

186
00:14:26,100 --> 00:14:31,570
Maintenant je sais que ma prochaine étape va être de rejoindre le plus petit nombre,

187
00:14:31,570 --> 00:14:41,380
qui est le T, le 1, puis en choisissant l'un des noeuds qui a la fréquence 2.

188
00:14:41,380 --> 00:14:44,560
Nous avons donc ici 3 options.

189
00:14:44,560 --> 00:14:47,980
Ce que je vais faire pour la diapositive est juste visuellement les réorganiser pour vous

190
00:14:47,980 --> 00:14:51,790
afin que vous puissiez voir comment je suis en train de construire.

191
00:14:51,790 --> 00:14:59,040
Ce que le code et le code de distribution va faire serait rejoindre le T

192
00:14:59,040 --> 00:15:01,410
avec le noeud 0 et 5.

193
00:15:01,410 --> 00:15:05,060
Alors que des sommes à 3, puis nous continuons le processus.

194
00:15:05,060 --> 00:15:08,660
Le 2 et le 2 maintenant sont les plus bas, oui, alors ceux somme de 4.

195
00:15:08,660 --> 00:15:12,560
Tout le monde suit ce jour? D'accord.

196
00:15:12,560 --> 00:15:16,410
Puis, après que nous avons le 3 et le 3 qui doivent être additionnés,

197
00:15:16,410 --> 00:15:21,650
donc encore une fois je ne fais que passer afin que vous puissiez voir visuellement afin qu'il ne soit pas trop salissant.

198
00:15:21,650 --> 00:15:25,740
Ensuite, nous avons un 6, et alors notre dernière étape consiste maintenant que nous n'avons que 2 nœuds

199
00:15:25,740 --> 00:15:30,440
nous résumons les faire à la racine de notre arbre, qui est de 10.

200
00:15:30,440 --> 00:15:34,100
Et le numéro 10 a un sens parce que chaque nœud représenté,

201
00:15:34,100 --> 00:15:40,750
leur valeur, leur numéro de fréquence, c'était combien de fois ils sont apparus dans la chaîne,

202
00:15:40,750 --> 00:15:46,350
puis nous avons 5 personnages de notre chaîne, donc cela fait sens.

203
00:15:48,060 --> 00:15:52,320
Si nous regardons la façon dont nous aurions fait l'encoder,

204
00:15:52,320 --> 00:15:56,580
comme prévu, le i et le s, qui apparaissent le plus souvent

205
00:15:56,580 --> 00:16:01,350
sont représentés par le plus petit nombre de bits.

206
00:16:03,660 --> 00:16:05,660
>> Faites attention ici.

207
00:16:05,660 --> 00:16:09,780
Dans le cas des arbres de Huffman importe réellement.

208
00:16:09,780 --> 00:16:13,670
Un S majuscule est différent d'un s minuscule.

209
00:16:13,670 --> 00:16:21,260
Si nous avions «C'est CS50" avec des majuscules, minuscules, puis le s ne semblent deux fois,

210
00:16:21,260 --> 00:16:27,120
serait un nœud avec 2 comme valeur, puis majuscule S ne serait qu'une seule fois.

211
00:16:27,120 --> 00:16:33,440
Alors votre arbre allait changer les structures, car vous avez réellement une feuille supplémentaire ici.

212
00:16:33,440 --> 00:16:36,900
Mais la somme serait encore 10.

213
00:16:36,900 --> 00:16:39,570
C'est ce que nous allons en fait être l'appel de la somme de contrôle,

214
00:16:39,570 --> 00:16:44,060
l'addition de tous les chefs d'accusation.

215
00:16:46,010 --> 00:16:50,990
>> Maintenant que nous avons couvert des arbres de Huffman, on peut plonger dans Puff Huff'n, le pset.

216
00:16:50,990 --> 00:16:52,900
Nous allons commencer avec une section de questions,

217
00:16:52,900 --> 00:16:57,990
et ce qui se passe pour vous l'habitude d'arbres binaires et comment fonctionnent autour de ce qui suit:

218
00:16:57,990 --> 00:17:03,230
nœuds de dessin, créez votre propre struct typedef pour un nœud,

219
00:17:03,230 --> 00:17:07,230
et de voir comment vous pouvez insérer dans un arbre binaire, celui qui est triée,

220
00:17:07,230 --> 00:17:09,050
traversant, et des choses comme ça.

221
00:17:09,050 --> 00:17:14,560
Cette connaissance va certainement vous aider lorsque vous plongez dans la partie Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
de la pset.

223
00:17:19,150 --> 00:17:26,329
Dans l'édition standard du jeu de processeurs, votre tâche est de mettre en œuvre Puff,

224
00:17:26,329 --> 00:17:30,240
et dans la version pirate votre tâche est de mettre en œuvre Huff.

225
00:17:30,240 --> 00:17:38,490
Qu'est-ce Huff fait est qu'il faut texte, puis elle se traduit par des 0 et des 1,

226
00:17:38,490 --> 00:17:41,990
de sorte que le processus que nous avons fait ci-dessus où nous avons compté les fréquences

227
00:17:41,990 --> 00:17:50,970
et ensuite l'arbre et dit alors: «Comment puis-je obtenir T?"

228
00:17:50,970 --> 00:17:54,840
T est représenté par 100, des choses comme ça,

229
00:17:54,840 --> 00:17:58,860
puis Huff prendrait le texte, puis sortie binaire.

230
00:17:58,860 --> 00:18:04,920
Mais aussi parce que nous savons que nous voulons permettre à nos destinataire du message

231
00:18:04,920 --> 00:18:11,790
pour recréer l'arbre exactement le même, il comprend également des informations sur les comptes de fréquence.

232
00:18:11,790 --> 00:18:17,980
Puis, avec Puff on nous donne un fichier binaire de 0 et de 1

233
00:18:17,980 --> 00:18:21,740
et compte tenu également de l'information sur les fréquences.

234
00:18:21,740 --> 00:18:26,740
Nous traduisons tous ceux qui reviennent 0 et de 1 dans le message original qui a été,

235
00:18:26,740 --> 00:18:29,350
Nous sommes donc décompresser cela.

236
00:18:29,350 --> 00:18:36,450
Si vous faites l'édition standard, vous n'avez pas besoin de mettre en œuvre Huff,

237
00:18:36,450 --> 00:18:39,290
alors vous pouvez simplement utiliser l'application personnel de Huff.

238
00:18:39,290 --> 00:18:42,080
Il ya des instructions dans les spécifications sur la façon de le faire.

239
00:18:42,080 --> 00:18:48,780
Vous pouvez exécuter l'application personnel de Huff sur un fichier texte certain

240
00:18:48,780 --> 00:18:53,270
et ensuite utiliser cette sortie comme entrée de Puff.

241
00:18:53,270 --> 00:18:59,330
>> Comme je l'ai mentionné précédemment, nous avons une grande quantité de code de distribution de celui-ci.

242
00:18:59,330 --> 00:19:01,810
Je vais commencer à aller à travers elle.

243
00:19:01,810 --> 00:19:04,400
Je vais passer la plupart du temps sur le fichiers. H

244
00:19:04,400 --> 00:19:07,660
parce que dans les fichiers de c., parce que nous avons l'h.

245
00:19:07,660 --> 00:19:11,650
et qui nous fournit les prototypes des fonctions,

246
00:19:11,650 --> 00:19:15,520
nous ne sommes pas totalement besoin de comprendre exactement -

247
00:19:15,520 --> 00:19:20,280
Si vous ne comprenez pas ce qui se passe dans les fichiers de c., Alors ne vous inquiétez pas trop,

248
00:19:20,280 --> 00:19:23,600
mais certainement essayer de faire un tour car il pourrait donner quelques conseils

249
00:19:23,600 --> 00:19:29,220
et il est utile de s'habituer à la lecture de code d'autres personnes.

250
00:19:38,940 --> 00:19:48,270
>> En regardant huffile.h, dans les commentaires qu'il déclare une couche d'abstraction pour Huffman codés fichiers.

251
00:19:48,270 --> 00:20:01,660
Si nous descendons, nous voyons qu'il ya un maximum de 256 symboles que nous pourrions avoir besoin pour les codes.

252
00:20:01,660 --> 00:20:05,480
Cela comprend toutes les lettres de l'alphabet en majuscules et minuscules - -

253
00:20:05,480 --> 00:20:08,250
et puis symboles et des chiffres, etc

254
00:20:08,250 --> 00:20:11,930
Ensuite, nous avons ici un nombre magique identifier un fichier codé Huffman.

255
00:20:11,930 --> 00:20:15,890
Au sein d'un code de Huffman ils vont avoir un nombre magique certaine

256
00:20:15,890 --> 00:20:18,560
associée à l'en-tête.

257
00:20:18,560 --> 00:20:21,110
Cela pourrait ressembler à un simple numéro de magie aléatoire,

258
00:20:21,110 --> 00:20:27,160
mais si vous avez réellement le traduire en ASCII, il énonce effectivement sur HUFF.

259
00:20:27,160 --> 00:20:34,290
Ici, nous avons une structure d'un fichier codé Huffman.

260
00:20:34,290 --> 00:20:39,670
Il ya toutes ces caractéristiques associées à un fichier Huff.

261
00:20:39,670 --> 00:20:47,080
Alors ici nous avons l'en-tête d'un fichier Huff, afin que nous appelons Huffeader

262
00:20:47,080 --> 00:20:50,810
au lieu d'ajouter l'h supplémentaire, car il sonne de la même façon.

263
00:20:50,810 --> 00:20:52,720
Cute.

264
00:20:52,720 --> 00:20:57,790
Nous avons un nombre magique qui lui est associé.

265
00:20:57,790 --> 00:21:09,040
Si c'est un fichier réel Huff, ça va être le nombre au-dessus, celui-ci magie.

266
00:21:09,040 --> 00:21:14,720
Et puis il aura un tableau.

267
00:21:14,720 --> 00:21:18,750
Ainsi, pour chaque symbole, dont il existe 256,

268
00:21:18,750 --> 00:21:24,760
il va lister ce que la fréquence de ces symboles se trouvent dans le fichier Huff.

269
00:21:24,760 --> 00:21:28,090
Et puis enfin, nous avons une somme de contrôle pour les fréquences,

270
00:21:28,090 --> 00:21:32,160
qui devrait être la somme de ces fréquences.

271
00:21:32,160 --> 00:21:36,520
C'est donc ce qui est un Huffeader.

272
00:21:36,520 --> 00:21:44,600
Ensuite, nous avons quelques fonctions qui retournent le bit suivant dans le fichier Huff

273
00:21:44,600 --> 00:21:52,580
ainsi que le transcrit dans le fichier Huff, puis cette fonction ici, hfclose,

274
00:21:52,580 --> 00:21:54,650
qui ferme le fichier Huff.

275
00:21:54,650 --> 00:21:57,290
Avant, nous avions affaire à droite juste fclose,

276
00:21:57,290 --> 00:22:01,190
mais quand vous avez un fichier Huff, au lieu de le fclosing

277
00:22:01,190 --> 00:22:06,080
ce que vous allez réellement faire est hfclose et hfopen.

278
00:22:06,080 --> 00:22:13,220
Ce sont des fonctions spécifiques aux fichiers Huff que nous allons être confrontés.

279
00:22:13,220 --> 00:22:19,230
Alors voilà, nous lisons dans l'en-tête, puis d'écrire l'en-tête.

280
00:22:19,230 --> 00:22:25,700
>> Juste en lisant le fichier. H nous pouvons sorte de se faire une idée de ce qu'est un fichier Huff peut-être,

281
00:22:25,700 --> 00:22:32,480
quelles sont les caractéristiques qu'il possède, sans pour autant entrer dans le huffile.c,

282
00:22:32,480 --> 00:22:36,750
qui, si nous plonger, va être un peu plus complexe.

283
00:22:36,750 --> 00:22:41,270
Il dispose de tous les fichiers I / O affaire ici avec des pointeurs.

284
00:22:41,270 --> 00:22:48,010
Ici, nous voyons que lorsque nous appelons hfread, par exemple, il est toujours aux prises avec fread.

285
00:22:48,010 --> 00:22:53,050
Nous ne sommes pas de se débarrasser de ces fonctions tout à fait, mais nous envoyons ceux qui doivent être pris en charge

286
00:22:53,050 --> 00:22:59,760
dans le fichier Huff au lieu de faire tout nous-mêmes.

287
00:22:59,760 --> 00:23:02,300
Vous pouvez, n'hésitez pas à parcourir si vous êtes curieux

288
00:23:02,300 --> 00:23:08,410
et d'aller peler la couche arrière un peu.

289
00:23:20,650 --> 00:23:24,060
>> Le prochain dossier que nous allons regarder est tree.h.

290
00:23:24,060 --> 00:23:30,210
Avant Procédure pas à pas dans la glisse, nous avons dit nous nous attendons à un nœud de Huffman

291
00:23:30,210 --> 00:23:32,960
et nous avons fait un nœud typedef struct.

292
00:23:32,960 --> 00:23:38,360
Nous nous attendons à avoir un symbole, une fréquence, puis 2 étoiles nœud.

293
00:23:38,360 --> 00:23:41,870
Dans ce cas, ce que nous faisons, c'est que c'est essentiellement la même

294
00:23:41,870 --> 00:23:46,880
sauf qu'au lieu de nœud, nous allons appeler les arbres.

295
00:23:48,790 --> 00:23:56,760
Nous avons une fonction que lorsque vous appelez make arbre, il vous renvoie un pointeur arbre.

296
00:23:56,760 --> 00:24:03,450
Retour vers Speller, lorsque vous faisiez un nouveau nœud

297
00:24:03,450 --> 00:24:11,410
vous avez dit noeud * nouveau mot = malloc (sizeof) et des choses comme ça.

298
00:24:11,410 --> 00:24:17,510
Fondamentalement, mktree va avoir affaire à cela pour vous.

299
00:24:17,510 --> 00:24:20,990
De même, lorsque vous souhaitez supprimer un arbre,

300
00:24:20,990 --> 00:24:24,810
donc c'est essentiellement en libérant l'arbre lorsque vous avez terminé avec lui,

301
00:24:24,810 --> 00:24:33,790
au lieu de d'appeler explicitement gratuitement sur cela, vous êtes en fait juste l'intention d'utiliser la fonction rmtree

302
00:24:33,790 --> 00:24:40,360
où vous passez le pointeur sur cet arbre, puis tree.c prendra soin de cela pour vous.

303
00:24:40,360 --> 00:24:42,490
>> Nous nous penchons sur tree.c.

304
00:24:42,490 --> 00:24:47,240
Nous attendons les mêmes fonctions, sauf pour voir la mise en œuvre aussi bien.

305
00:24:47,240 --> 00:24:57,720
Comme on s'y attendait, lorsque vous appelez mktree il mallocs la taille d'un arbre dans un pointeur,

306
00:24:57,720 --> 00:25:03,190
initialise toutes les valeurs à la valeur NULL, donc 0 ou NULL,

307
00:25:03,190 --> 00:25:08,280
puis retourne le pointeur vers cet arbre que vous venez de malloc pour vous.

308
00:25:08,280 --> 00:25:13,340
Ici, lorsque vous appelez enlever un arbre il fait d'abord s'assurer que vous n'êtes pas à double libération.

309
00:25:13,340 --> 00:25:18,320
Il permet de s'assurer que vous avez réellement un arbre que vous souhaitez supprimer.

310
00:25:18,320 --> 00:25:23,330
Ici, à cause d'un arbre comprend également ses enfants,

311
00:25:23,330 --> 00:25:29,560
ce que cela ne se fait-il s'appelle récursivement enlever un arbre sur le noeud de gauche de l'arbre

312
00:25:29,560 --> 00:25:31,650
ainsi que le noeud de droite.

313
00:25:31,650 --> 00:25:37,790
Avant cela libère le parent, il doit libérer les enfants aussi.

314
00:25:37,790 --> 00:25:42,770
Parent est également interchangeable avec la racine.

315
00:25:42,770 --> 00:25:46,500
Le parent première fois, donc comme le grand-grand-grand-grand-père

316
00:25:46,500 --> 00:25:52,130
ou un arbre grand-mère, il faut d'abord libérer le bas les niveaux d'abord.

317
00:25:52,130 --> 00:25:58,490
Donc, traverser vers le bas, sans ceux-ci, et puis revenir, sans ceux-ci, etc

318
00:26:00,400 --> 00:26:02,210
Donc, c'est l'arbre.

319
00:26:02,210 --> 00:26:04,240
>> Maintenant, nous regardons la forêt.

320
00:26:04,240 --> 00:26:09,860
Forest est où vous placez tous vos arbres Huffman.

321
00:26:09,860 --> 00:26:12,910
C'est dire que nous allons avoir quelque chose qui s'appelle un complot

322
00:26:12,910 --> 00:26:22,320
qui contient un pointeur sur un arbre, ainsi qu'un pointeur vers une parcelle suivante appelée.

323
00:26:22,320 --> 00:26:28,480
Quelle est la structure fait ce genre de ressembler?

324
00:26:29,870 --> 00:26:32,490
Il sorte de qu'il dit là-bas.

325
00:26:34,640 --> 00:26:36,700
Par ici.

326
00:26:37,340 --> 00:26:39,170
Une liste chaînée.

327
00:26:39,170 --> 00:26:44,590
Nous voyons que lorsque nous avons un terrain, c'est comme une liste chaînée de parcelles.

328
00:26:44,590 --> 00:26:53,020
Une forêt est défini comme une liste chaînée de parcelles,

329
00:26:53,020 --> 00:26:58,100
et si la structure de la forêt, c'est que nous allons juste d'avoir un pointeur vers notre première parcelle

330
00:26:58,100 --> 00:27:02,740
et que la parcelle a un arbre en son sein ou fait plutôt à un arbre

331
00:27:02,740 --> 00:27:06,190
et pointe alors vers la parcelle suivante, ainsi de suite et ainsi de suite.

332
00:27:06,190 --> 00:27:11,100
Pour faire une forêt que nous appelons mkforest.

333
00:27:11,100 --> 00:27:14,930
Ensuite, nous avons quelques fonctions très utiles ici.

334
00:27:14,930 --> 00:27:23,240
Nous avons choisir où vous passez dans une forêt, puis la valeur de retour est un * Arbre,

335
00:27:23,240 --> 00:27:25,210
un pointeur vers un arbre.

336
00:27:25,210 --> 00:27:29,370
Qu'est-ce médiator vous faire, c'est de se rendre dans la forêt que vous pointez

337
00:27:29,370 --> 00:27:35,240
puis retirer un arbre avec la fréquence la plus basse de cette forêt

338
00:27:35,240 --> 00:27:38,330
et puis vous donner le pointeur vers cet arbre.

339
00:27:38,330 --> 00:27:43,030
Une fois que vous l'interception, l'arbre n'existe pas dans la forêt plus,

340
00:27:43,030 --> 00:27:48,550
mais la valeur de retour est le pointeur vers cet arbre.

341
00:27:48,550 --> 00:27:50,730
Ensuite, vous avez des plantes.

342
00:27:50,730 --> 00:27:57,420
Pourvu que vous passez un pointeur vers un arbre qui a une fréquence non-0,

343
00:27:57,420 --> 00:28:04,040
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.

344
00:28:04,040 --> 00:28:06,370
Ici, nous avons rmforest.

345
00:28:06,370 --> 00:28:11,480
Semblable à enlever un arbre, qui, fondamentalement, libéré de tous nos arbres pour nous,

346
00:28:11,480 --> 00:28:16,600
retirer la forêt sera tout libre contenue dans cette forêt.

347
00:28:16,600 --> 00:28:24,890
>> Si nous regardons dans forest.c, nous allons attendre de voir au moins 1 commande rmtree là-dedans,

348
00:28:24,890 --> 00:28:30,090
parce que, pour libérer de la mémoire dans la forêt si une forêt a des arbres qui s'y trouvent,

349
00:28:30,090 --> 00:28:32,930
puis finalement vous allez avoir à enlever les arbres aussi.

350
00:28:32,930 --> 00:28:41,020
Si nous regardons dans forest.c, nous avons notre mkforest, qui est comme nous le prévoyons.

351
00:28:41,020 --> 00:28:42,890
Nous malloc choses.

352
00:28:42,890 --> 00:28:51,740
On initialise la première parcelle dans la forêt comme NULL car elle est vide, pour commencer,

353
00:28:51,740 --> 00:29:05,940
alors nous voyons choix, qui renvoie l'arbre avec le poids le plus faible, la fréquence la plus basse,

354
00:29:05,940 --> 00:29:13,560
puis obtient débarrasser de ce noeud particulier qui pointe vers cet arbre et le prochain,

355
00:29:13,560 --> 00:29:16,760
donc il faut que, sur la liste chaînée de la forêt.

356
00:29:16,760 --> 00:29:24,510
Et puis, nous avons ici des plantes, qui insère un arbre dans la liste chaînée.

357
00:29:24,510 --> 00:29:29,960
Quelle forêt ne tient-il joliment triées pour nous.

358
00:29:29,960 --> 00:29:37,910
Et puis finalement, nous avons rmforest et, comme prévu, nous avons rmtree appelé là-bas.

359
00:29:46,650 --> 00:29:55,440
>> En regardant le code de distribution à ce jour, huffile.c était probablement de loin le plus difficile à comprendre,

360
00:29:55,440 --> 00:29:59,990
alors que les autres fichiers eux-mêmes étaient assez simples à suivre.

361
00:29:59,990 --> 00:30:03,090
Grâce à notre connaissance des pointeurs et les listes chaînées et autres,

362
00:30:03,090 --> 00:30:04,860
nous avons pu suivre assez bien.

363
00:30:04,860 --> 00:30:10,500
Mais tout ce que nous devons vraiment faire en sorte que nous comprenons parfaitement ce sont les fichiers. H

364
00:30:10,500 --> 00:30:15,840
parce que vous devez être appeler ces fonctions, traiter avec ces valeurs de retour,

365
00:30:15,840 --> 00:30:20,590
alors assurez-vous de bien comprendre ce que l'action va être effectuée

366
00:30:20,590 --> 00:30:24,290
chaque fois que vous appelez l'une de ces fonctions.

367
00:30:24,290 --> 00:30:33,020
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.

368
00:30:35,170 --> 00:30:39,490
Nous avons 2 fichiers plus laissés dans notre code de distribution.

369
00:30:39,490 --> 00:30:41,640
>> Regardons décharge.

370
00:30:41,640 --> 00:30:47,230
Dump par son commentaire ici prend un fichier compressé Huffman

371
00:30:47,230 --> 00:30:55,580
puis traduit et dépôts de tous de son contenu à l'extérieur.

372
00:31:01,010 --> 00:31:04,260
Ici, nous voyons qu'il appelle hfopen.

373
00:31:04,260 --> 00:31:10,770
C'est une sorte de miroir de déposer entrée * = fopen,

374
00:31:10,770 --> 00:31:13,500
puis vous passez à l'information.

375
00:31:13,500 --> 00:31:18,240
Il est presque identique sauf qu'au lieu d'un fichier * vous êtes de passage dans un Huffile;

376
00:31:18,240 --> 00:31:22,030
au lieu de fopen vous êtes de passage dans hfopen.

377
00:31:22,030 --> 00:31:29,280
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

378
00:31:29,280 --> 00:31:33,580
pour un fichier bitmap.

379
00:31:33,580 --> 00:31:38,000
Ce que nous faisons ici est de vérifier pour voir si les informations d'en-tête

380
00:31:38,000 --> 00:31:44,330
contient le nombre magique droite qui indique que c'est un fichier réel Huff,

381
00:31:44,330 --> 00:31:53,610
puis toutes ces vérifications afin de s'assurer que le fichier que nous est ouvert un fichier réel souffla ou non.

382
00:31:53,610 --> 00:32:05,330
Que cela ne se fait-il émet les fréquences de tous les symboles que nous pouvons voir

383
00:32:05,330 --> 00:32:09,790
sein d'un terminal dans un tableau graphique.

384
00:32:09,790 --> 00:32:15,240
Cette partie va être utile.

385
00:32:15,240 --> 00:32:24,680
Il a un peu et lit peu à peu dans le binaire variable et imprime ensuite sur.

386
00:32:28,220 --> 00:32:35,430
Donc, si je devais appeler décharge sur hth.bin, qui est le résultat de sniffer un fichier

387
00:32:35,430 --> 00:32:39,490
l'aide de la solution de personnel, je voudrais obtenir cela.

388
00:32:39,490 --> 00:32:46,000
C'est la sortie de tous ces personnages et en mettant ensuite la fréquence à laquelle ils apparaissent.

389
00:32:46,000 --> 00:32:51,180
Si l'on regarde, la plupart d'entre eux sont des 0 sauf pour ceci: H, qui apparaît deux fois,

390
00:32:51,180 --> 00:32:54,820
puis T, qui apparaît une fois.

391
00:32:54,820 --> 00:33:07,860
Et puis, nous avons ici le message réel en 0 et de 1.

392
00:33:07,860 --> 00:33:15,450
Si nous regardons hth.txt, qui est sans doute le message original qui a été souffla,

393
00:33:15,450 --> 00:33:22,490
nous nous attendons à voir Hs et Ts là-dedans.

394
00:33:22,490 --> 00:33:28,720
Plus précisément, nous nous attendons à seulement 1 T et 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Ici, nous sommes dans hth.txt. Il a en effet HTH.

396
00:33:37,440 --> 00:33:41,270
Inclus là-dedans, même si nous ne pouvons pas le voir, est un caractère de nouvelle ligne.

397
00:33:41,270 --> 00:33:53,190
Le fichier hth.bin Huff est également codant pour le caractère de nouvelle ligne aussi bien.

398
00:33:55,680 --> 00:34:01,330
Ici, parce que nous savons que l'ordre est HTH, puis retour à la ligne,

399
00:34:01,330 --> 00:34:07,340
nous pouvons voir que, probablement, le H est représenté par un simple 1 lit simple

400
00:34:07,340 --> 00:34:17,120
puis la T 01 est probablement puis la prochaine H est 1 et

401
00:34:17,120 --> 00:34:21,139
et puis nous avons un retour à la ligne indiquée par deux 0.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> Et puis, enfin, parce que nous traitons multiple. C et les fichiers. H,

404
00:34:31,600 --> 00:34:36,350
nous allons avoir un argument assez complexe pour le compilateur,

405
00:34:36,350 --> 00:34:40,460
et donc nous avons ici un Makefile qui permet de vidage pour vous.

406
00:34:40,460 --> 00:34:47,070
Mais en réalité, il faut s'y prendre pour faire votre propre fichier puff.c.

407
00:34:47,070 --> 00:34:54,330
Le fichier Makefile ne fait pas face à puff.c faire pour vous.

408
00:34:54,330 --> 00:34:59,310
Nous partons ce à vous de modifier le fichier Makefile.

409
00:34:59,310 --> 00:35:05,930
Lorsque vous entrez une commande similaire à faire tous, par exemple, il fera tous pour vous.

410
00:35:05,930 --> 00:35:10,760
N'hésitez pas à regarder les exemples de Makefile à partir du passé pset

411
00:35:10,760 --> 00:35:17,400
ainsi que d'aller hors de celui-ci pour voir comment vous pourriez être en mesure de rendre votre fichier de Puff

412
00:35:17,400 --> 00:35:20,260
en éditant ce Makefile.

413
00:35:20,260 --> 00:35:22,730
C'est à ce sujet pour notre code de distribution.

414
00:35:22,730 --> 00:35:28,380
>> Une fois que nous avons obtenu grâce à cela, alors voici juste un autre rappel

415
00:35:28,380 --> 00:35:30,980
de la façon dont nous allons avoir affaire à des nœuds de Huffman.

416
00:35:30,980 --> 00:35:35,400
Nous n'allons pas à les appeler nœuds plus, nous allons appeler les arbres

417
00:35:35,400 --> 00:35:39,260
où nous allons représenter leur symbole avec un char,

418
00:35:39,260 --> 00:35:43,340
leur fréquence, le nombre d'occurrences, d'un nombre entier.

419
00:35:43,340 --> 00:35:47,370
Nous utilisons ce que parce qu'il est plus précise que celle d'un flotteur.

420
00:35:47,370 --> 00:35:52,980
Et puis nous avons un autre pointeur vers le fils gauche ainsi que l'enfant le droit.

421
00:35:52,980 --> 00:35:59,630
Une forêt, comme nous l'avons vu, est tout simplement une liste chaînée des arbres.

422
00:35:59,630 --> 00:36:04,670
En fin de compte, lorsque nous construisons notre fichier Huff,

423
00:36:04,670 --> 00:36:07,580
nous voulons que notre forêt pour contenir seulement 1 arbre -

424
00:36:07,580 --> 00:36:12,420
1 arbre, 1 racine avec plusieurs enfants.

425
00:36:12,420 --> 00:36:20,840
Un peu plus tôt, lorsque nous étions juste de rendre nos arbres Huffman,

426
00:36:20,840 --> 00:36:25,360
nous avons commencé par placer tous les nœuds sur notre écran

427
00:36:25,360 --> 00:36:27,790
et dire que nous allons avoir ces nœuds,

428
00:36:27,790 --> 00:36:32,920
finalement, ils vont être les feuilles, ce qui est leur symbole, c'est leur fréquence.

429
00:36:32,920 --> 00:36:42,070
Dans nos forêts si nous avons juste 3 lettres, c'est une forêt de 3 arbres.

430
00:36:42,070 --> 00:36:45,150
Et puis, à mesure que nous, quand nous avons ajouté le premier parent,

431
00:36:45,150 --> 00:36:48,080
nous avons fait une forêt de 2 arbres.

432
00:36:48,080 --> 00:36:54,930
Nous avons supprimé 2 de ces enfants de notre forêt et l'a remplacé par un nœud parent

433
00:36:54,930 --> 00:36:58,820
qui a eu ces 2 nœuds que les enfants.

434
00:36:58,820 --> 00:37:05,600
Et puis enfin, notre dernière étape à faire de notre exemple avec l'As, Bs, Cs et

435
00:37:05,600 --> 00:37:08,030
serait de rendre le parent finale,

436
00:37:08,030 --> 00:37:13,190
et si alors ce serait apporter notre nombre total d'arbres dans la forêt à 1.

437
00:37:13,190 --> 00:37:18,140
Est-ce que tout le monde voir comment vous commencez avec plusieurs arbres dans votre forêt

438
00:37:18,140 --> 00:37:22,520
et se retrouvent avec 1? D'accord. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Que devons-nous faire pour Puff?

440
00:37:28,110 --> 00:37:37,110
Ce que nous devons faire est de s'assurer que, comme toujours, ils nous donnent le bon type d'entrée

441
00:37:37,110 --> 00:37:39,090
afin que nous puissions réellement exécuter le programme.

442
00:37:39,090 --> 00:37:43,130
Dans ce cas, ils vont être nous donner après leur premier argument de la ligne de commande

443
00:37:43,130 --> 00:37:53,440
2 plus: le fichier que l'on veut décompresser et la sortie du fichier décompressé.

444
00:37:53,440 --> 00:38:00,410
Mais une fois que nous nous assurons qu'ils nous passent dans la bonne quantité de valeurs,

445
00:38:00,410 --> 00:38:05,820
nous voulons nous assurer que l'entrée est un fichier Huff ou non.

446
00:38:05,820 --> 00:38:10,420
Et puis une fois que nous garantissons qu'il s'agit d'un fichier Huff, alors que nous voulons construire notre arbre,

447
00:38:10,420 --> 00:38:20,940
construire l'arbre de telle sorte qu'il épouse l'arbre que la personne qui a envoyé le message construit.

448
00:38:20,940 --> 00:38:25,840
Puis, après nous construisons l'arbre, alors nous pouvons faire face à la, 0 et de 1 qui ils ont passé en

449
00:38:25,840 --> 00:38:29,590
suivre ceux le long de notre arbre, car il est identique,

450
00:38:29,590 --> 00:38:33,510
puis d'écrire ce message, interpréter les bits de nouveau dans les caractères.

451
00:38:33,510 --> 00:38:35,880
Et puis à la fin, parce que nous avons affaire ici avec des pointeurs,

452
00:38:35,880 --> 00:38:38,110
nous voulons nous assurer que nous n'avons pas de fuites de mémoire

453
00:38:38,110 --> 00:38:41,330
et que nous tout gratuitement.

454
00:38:42,820 --> 00:38:46,430
>> Assurer le bon usage est vieux chapeau pour nous maintenant.

455
00:38:46,430 --> 00:38:51,980
Nous prenons en entrée, ce qui va être le nom du fichier à gonfler,

456
00:38:51,980 --> 00:38:56,010
puis nous spécifions une sortie,

457
00:38:56,010 --> 00:39:01,580
si le nom du fichier pour la sortie soufflé, qui est le fichier de texte.

458
00:39:03,680 --> 00:39:08,820
C'est l'usage. Et maintenant, nous voulons nous assurer que l'entrée est souffla ou non.

459
00:39:08,820 --> 00:39:16,420
En y repensant, c'était il ya quelque chose dans le code de distribution qui pourrait nous aider

460
00:39:16,420 --> 00:39:21,570
à comprendre si un fichier est souffla ou non?

461
00:39:21,570 --> 00:39:26,910
Il y avait des informations au sujet de la huffile.c Huffeader.

462
00:39:26,910 --> 00:39:33,430
Nous savons que chaque fichier Huff a une Huffeader qui lui est associé avec un nombre magique

463
00:39:33,430 --> 00:39:37,240
ainsi que d'un tableau de fréquences pour chaque symbole

464
00:39:37,240 --> 00:39:39,570
ainsi que d'une somme de contrôle.

465
00:39:39,570 --> 00:39:43,180
Nous le savons, mais nous avons aussi pris un coup d'oeil à dump.c,

466
00:39:43,180 --> 00:39:49,120
dans lequel il a été lu dans un fichier Huff.

467
00:39:49,120 --> 00:39:53,990
Et donc pour ce faire, il fallait vérifier si elle était vraiment souffla ou non.

468
00:39:53,990 --> 00:40:03,380
Alors peut-être que nous pourrions utiliser dump.c comme une structure pour notre puff.c.

469
00:40:03,380 --> 00:40:12,680
Retour à pset 4 lorsque nous avons eu l'copy.c fichier copié dans les triplets RGB

470
00:40:12,680 --> 00:40:14,860
et nous avons interprété que pour Whodunit et de redimensionnement,

471
00:40:14,860 --> 00:40:20,390
de même, ce que vous pourriez faire est de simplement exécuter la commande comme cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
et utiliser une partie du code là-bas.

473
00:40:23,600 --> 00:40:28,210
Cependant, il ne va pas être aussi simple d'un processus

474
00:40:28,210 --> 00:40:33,010
pour la traduction de votre dump.c en puff.c,

475
00:40:33,010 --> 00:40:36,160
mais au moins il vous donne un endroit pour commencer

476
00:40:36,160 --> 00:40:40,540
sur la façon de faire en sorte que l'entrée est effectivement ou non huffed

477
00:40:40,540 --> 00:40:43,240
ainsi que quelques autres choses.

478
00:40:45,930 --> 00:40:50,250
Nous avons veillé à l'utilisation appropriée et veiller à ce que l'entrée est souffla.

479
00:40:50,250 --> 00:40:53,570
Chaque fois que nous avons fait ce que nous avons fait notre vérification d'erreur appropriée,

480
00:40:53,570 --> 00:41:01,520
afin de retourner et quitter la fonction si une défaillance se produit, si il ya un problème.

481
00:41:01,520 --> 00:41:07,170
>> Maintenant, ce que nous voulons faire est de construire l'arbre réel.

482
00:41:08,840 --> 00:41:12,640
Si nous regardons dans la forêt, il ya 2 fonctions principales

483
00:41:12,640 --> 00:41:15,800
que nous allons vouloir devenir très familier avec.

484
00:41:15,800 --> 00:41:23,870
Il ya l'usine de fonction booléenne qui plante un arbre de fréquence non-0 à l'intérieur de notre forêt.

485
00:41:23,870 --> 00:41:29,250
Et alors là vous passez un pointeur vers une forêt et un pointeur vers un arbre.

486
00:41:32,530 --> 00:41:40,340
Petite question: Combien de forêts que vous avez quand vous construisez un arbre de Huffman?

487
00:41:44,210 --> 00:41:46,650
Notre forêt est comme notre toile, non?

488
00:41:46,650 --> 00:41:50,800
Donc, nous allons seulement avoir 1 forêt, mais nous allons avoir plusieurs arbres.

489
00:41:50,800 --> 00:41:57,590
Alors avant de vous appeler usine, vous êtes sans doute allez avoir à faire de votre forêt.

490
00:41:57,590 --> 00:42:04,430
Il existe une commande pour que, si vous regardez dans forest.h sur la façon dont vous pouvez faire une forêt.

491
00:42:04,430 --> 00:42:09,270
Vous pouvez planter un arbre. Nous savons comment le faire.

492
00:42:09,270 --> 00:42:11,590
Et puis, vous pouvez aussi choisir un arbre de la forêt,

493
00:42:11,590 --> 00:42:17,540
la suppression d'un arbre avec le moins de poids et en vous donnant le pointeur à cela.

494
00:42:17,540 --> 00:42:23,090
En repensant au moment où nous faisions les exemples nous-mêmes,

495
00:42:23,090 --> 00:42:27,980
quand nous avons été le tirer, il suffit juste d'ajouter les liens.

496
00:42:27,980 --> 00:42:31,680
Mais ici, au lieu de simplement ajouter des liens,

497
00:42:31,680 --> 00:42:40,630
pense qu'il est plus que vous retirez 2 de ces nœuds, puis le remplacer par un autre.

498
00:42:40,630 --> 00:42:44,200
Pour exprimer cela en termes de récolte et de plantation,

499
00:42:44,200 --> 00:42:48,840
vous vous en prenez 2 arbres et la plantation d'un autre arbre

500
00:42:48,840 --> 00:42:54,060
qui a ces 2 arbres que vous avez sélectionnés comme des enfants.

501
00:42:57,950 --> 00:43:05,280
Pour construire l'arbre de Huffman, vous pouvez lire dans les symboles et les fréquences afin

502
00:43:05,280 --> 00:43:10,790
parce que le Huffeader donne que pour vous,

503
00:43:10,790 --> 00:43:14,250
vous donne un tableau des fréquences.

504
00:43:14,250 --> 00:43:19,660
Ainsi, vous pouvez aller de l'avant et simplement ignorer quoi que ce soit avec le 0 dans l'

505
00:43:19,660 --> 00:43:23,760
parce que nous ne voulons pas 256 feuilles à la fin de celui-ci.

506
00:43:23,760 --> 00:43:27,960
Nous voulons seulement le nombre de feuilles qui sont des caractères

507
00:43:27,960 --> 00:43:31,600
qui sont effectivement utilisées dans le fichier.

508
00:43:31,600 --> 00:43:37,590
Vous pouvez lire ces symboles, et chacun de ces symboles qui ont des fréquences-0,

509
00:43:37,590 --> 00:43:40,440
ceux qui vont être les arbres.

510
00:43:40,440 --> 00:43:45,990
Ce que vous pouvez faire, c'est à chaque fois que vous lisez dans un symbole de fréquence non-0,

511
00:43:45,990 --> 00:43:50,660
vous pouvez planter cet arbre dans la forêt.

512
00:43:50,660 --> 00:43:56,620
Une fois que vous planter les arbres dans la forêt, vous pouvez joindre ces arbres comme frères et sœurs,

513
00:43:56,620 --> 00:44:01,130
Pour en revenir à la plantation et la cueillette où vous choisissez 2, puis l'usine 1,

514
00:44:01,130 --> 00:44:05,820
où ce 1 que vous avez usine est la mère des 2 enfants que vous avez sélectionnés.

515
00:44:05,820 --> 00:44:11,160
Alors votre résultat final va être un seul arbre dans votre forêt.

516
00:44:16,180 --> 00:44:18,170
C'est ainsi que vous construisez votre arbre.

517
00:44:18,170 --> 00:44:21,850
>> Il ya plusieurs choses qui pourraient aller mal ici

518
00:44:21,850 --> 00:44:26,580
parce que nous avons affaire à faire de nouveaux arbres et de traiter avec des pointeurs et des choses comme ça.

519
00:44:26,580 --> 00:44:30,450
Avant, quand nous avions affaire à des pointeurs,

520
00:44:30,450 --> 00:44:36,580
chaque fois que nous malloc nous voulions pour s'assurer qu'il n'avait pas de nous retourner une valeur de pointeur NULL.

521
00:44:36,580 --> 00:44:42,770
Ainsi, à plusieurs étapes dans ce processus, il va y avoir plusieurs cas

522
00:44:42,770 --> 00:44:45,920
où votre programme risque d'échouer.

523
00:44:45,920 --> 00:44:51,310
Qu'est-ce que vous voulez faire, c'est que vous voulez vous assurer que vous manipulez ces erreurs,

524
00:44:51,310 --> 00:44:54,580
et dans les spécifications il est dit de les manipuler avec élégance,

525
00:44:54,580 --> 00:45:00,280
si semblable à imprimer un message à l'utilisateur de leur dire pourquoi le programme doit quitter

526
00:45:00,280 --> 00:45:03,050
puis rapidement le quitter.

527
00:45:03,050 --> 00:45:09,490
Pour ce faire, la gestion des erreurs, n'oubliez pas que vous voulez le vérifier

528
00:45:09,490 --> 00:45:12,160
chaque fois qu'il pourrait y avoir un échec.

529
00:45:12,160 --> 00:45:14,660
Chaque fois que vous faites un nouveau pointeur

530
00:45:14,660 --> 00:45:17,040
vous voulez vous assurer que c'est réussi.

531
00:45:17,040 --> 00:45:20,320
Avant que nous l'habitude de faire, c'est de faire un nouveau pointeur et malloc il,

532
00:45:20,320 --> 00:45:22,380
puis nous vérifions si ce pointeur est NULL.

533
00:45:22,380 --> 00:45:25,670
Donc, il va y avoir des cas où il vous suffit de le faire,

534
00:45:25,670 --> 00:45:28,610
mais parfois vous êtes en train d'appeler une fonction

535
00:45:28,610 --> 00:45:33,100
et, dans cette fonction, c'est celui qui fait le allouer de.

536
00:45:33,100 --> 00:45:39,110
Dans ce cas, si nous regardons en arrière à certains des fonctions dans le code,

537
00:45:39,110 --> 00:45:42,260
certains d'entre eux sont des fonctions booléennes.

538
00:45:42,260 --> 00:45:48,480
Dans le cas abstrait si nous avons une fonction booléenne appelée foo,

539
00:45:48,480 --> 00:45:54,580
fondamentalement, on peut supposer que, en plus de faire tout ce qui ne foo,

540
00:45:54,580 --> 00:45:57,210
puisque c'est une fonction booléenne, elle retourne vrai ou faux -

541
00:45:57,210 --> 00:46:01,300
vrai en cas de succès, false sinon.

542
00:46:01,300 --> 00:46:06,270
Donc, nous voulons vérifier si la valeur de retour de toto est vraie ou fausse.

543
00:46:06,270 --> 00:46:10,400
Si elle est fausse, cela signifie que nous allons souhaitez imprimer une sorte de message

544
00:46:10,400 --> 00:46:14,390
puis quittez le programme.

545
00:46:14,390 --> 00:46:18,530
Ce que nous voulons faire est de vérifier la valeur de retour de foo.

546
00:46:18,530 --> 00:46:23,310
Si foo renvoie false, alors nous savons que nous avons rencontré un certain genre d'erreur

547
00:46:23,310 --> 00:46:25,110
et nous devons quitter notre programme.

548
00:46:25,110 --> 00:46:35,600
Une façon de le faire est d'avoir un état où la fonction elle-même est votre état de santé.

549
00:46:35,600 --> 00:46:39,320
Dites foo prend en x.

550
00:46:39,320 --> 00:46:43,390
Nous pouvons avoir en tant que condition if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Fondamentalement, cela signifie que si à la fin de l'exécution de foo elle renvoie true,

552
00:46:50,900 --> 00:46:57,390
alors nous pouvons le faire parce que la fonction doit évaluer foo

553
00:46:57,390 --> 00:47:00,500
afin d'évaluer l'état entier.

554
00:47:00,500 --> 00:47:06,500
Alors c'est comme ça que vous pouvez faire quelque chose si la fonction renvoie true et est couronnée de succès.

555
00:47:06,500 --> 00:47:11,800
Mais quand vous êtes vérification des erreurs, vous ne voulez cesser de fumer si votre fonction retourne false.

556
00:47:11,800 --> 00:47:16,090
Qu'est-ce que vous pourriez faire est de simplement ajouter un == false ou tout simplement ajouter un coup en face d'elle

557
00:47:16,090 --> 00:47:21,010
et puis vous avez if (! foo).

558
00:47:21,010 --> 00:47:29,540
Au sein de ce corps d'état qui vous aurait tout de la gestion des erreurs,

559
00:47:29,540 --> 00:47:36,940
si semblable, "Impossible de créer cet arbre", puis retourner 1 ou quelque chose comme ça.

560
00:47:36,940 --> 00:47:43,340
Qu'est-ce qui fait, cependant, c'est que même si foo a retourné false -

561
00:47:43,340 --> 00:47:46,980
Dites foo retourne true.

562
00:47:46,980 --> 00:47:51,060
Ensuite, vous n'avez pas à appeler foo nouveau. C'est une idée fausse très répandue.

563
00:47:51,060 --> 00:47:54,730
Parce que c'était dans votre état, il est déjà évaluée,

564
00:47:54,730 --> 00:47:59,430
si vous avez déjà le résultat si vous utilisez rendre arbre ou quelque chose comme ça

565
00:47:59,430 --> 00:48:01,840
des végétaux ou des choix ou quelque chose.

566
00:48:01,840 --> 00:48:07,460
Il a déjà cette valeur. Il est déjà exécuté.

567
00:48:07,460 --> 00:48:10,730
Il est donc utile d'utiliser des fonctions booléennes comme la condition

568
00:48:10,730 --> 00:48:13,890
car si on fait exécuter le corps de la boucle,

569
00:48:13,890 --> 00:48:18,030
il exécute la fonction de toute façon.

570
00:48:22,070 --> 00:48:27,330
>> Notre deuxième à la dernière étape est la rédaction du message dans le fichier.

571
00:48:27,330 --> 00:48:33,070
Une fois que nous construisons l'arbre de Huffman, puis écrire le message dans le fichier est assez simple.

572
00:48:33,070 --> 00:48:39,260
C'est assez simple maintenant il suffit de suivre le 0 et de 1.

573
00:48:39,260 --> 00:48:45,480
Et donc, par convention, nous savons que dans un arbre de Huffman les 0 indiquent gauche

574
00:48:45,480 --> 00:48:48,360
et les 1 indiquent droite.

575
00:48:48,360 --> 00:48:53,540
Alors, si vous avez lu dans peu à peu, à chaque fois que vous obtenez un 0

576
00:48:53,540 --> 00:48:59,100
vous suivez la branche gauche, puis à chaque fois que vous avez lu dans un 1

577
00:48:59,100 --> 00:49:02,100
vous allez suivre la branche droite.

578
00:49:02,100 --> 00:49:07,570
Et puis vous allez continuer jusqu'à ce que vous appuyez sur une feuille

579
00:49:07,570 --> 00:49:11,550
parce que les feuilles vont être à l'extrémité des branches.

580
00:49:11,550 --> 00:49:16,870
Comment pouvons-nous dire si nous avons touché une feuille ou pas?

581
00:49:19,800 --> 00:49:21,690
Nous l'avons dit auparavant.

582
00:49:21,690 --> 00:49:24,040
[L'élève] Si les pointeurs sont NULL. Ouais >>.

583
00:49:24,040 --> 00:49:32,220
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.

584
00:49:32,220 --> 00:49:34,110
Parfait.

585
00:49:34,110 --> 00:49:40,320
Nous savons que nous voulons lire dans peu à peu dans notre fichier Huff.

586
00:49:43,870 --> 00:49:51,220
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

587
00:49:51,220 --> 00:49:54,560
et vient d'être imprimée sur ce que ces morceaux étaient.

588
00:49:54,560 --> 00:49:58,430
Nous n'allons pas faire cela. Nous allons faire quelque chose qui est un peu plus complexe.

589
00:49:58,430 --> 00:50:03,620
Mais ce que nous pouvons faire, c'est que nous pouvons prendre que peu de code qui lit le bit.

590
00:50:03,620 --> 00:50:10,250
Ici, nous avons le bit entier représentant le bit courant que nous sommes.

591
00:50:10,250 --> 00:50:15,520
Cela prend soin d'itérer tous les bits dans le fichier jusqu'à ce que vous atteignez la fin du fichier.

592
00:50:15,520 --> 00:50:21,270
Sur cette base, alors vous allez vouloir avoir une sorte d'itérateur

593
00:50:21,270 --> 00:50:26,760
pour parcourir votre arborescence.

594
00:50:26,760 --> 00:50:31,460
Puis, selon que le bit est 0 ou 1,

595
00:50:31,460 --> 00:50:36,920
vous allez avoir à se déplacer soit que itérateur vers la gauche ou vers la droite

596
00:50:36,920 --> 00:50:44,080
tout le chemin jusqu'à ce que vous appuyez sur une feuille, donc tout le chemin jusqu'à ce que le noeud que vous êtes sur

597
00:50:44,080 --> 00:50:48,260
ne dirigez pas vers les ganglions, pas plus.

598
00:50:48,260 --> 00:50:54,300
Pourquoi peut-on faire avec un fichier de Huffman mais pas le code Morse?

599
00:50:54,300 --> 00:50:56,610
Parce que dans le code Morse, il ya un peu d'ambiguïté.

600
00:50:56,610 --> 00:51:04,440
Nous pourrions être comme, oh wait, nous avons touché une lettre le long du chemin, donc c'est peut-être notre lettre,

601
00:51:04,440 --> 00:51:08,150
tandis que si nous avons continué un peu plus longtemps, nous aurions atteint une autre lettre.

602
00:51:08,150 --> 00:51:13,110
Mais cela ne va pas se produire dans le codage de Huffman,

603
00:51:13,110 --> 00:51:17,540
si nous pouvons être assurés que la seule façon que nous allons frapper un caractère

604
00:51:17,540 --> 00:51:23,480
est de savoir si les enfants gauche et à droite de ce nœud sont NULL.

605
00:51:28,280 --> 00:51:32,350
>> Enfin, nous voulons libérer l'ensemble de notre mémoire.

606
00:51:32,350 --> 00:51:37,420
Nous voulons à la fois proche du dossier Huff que nous avons eu affaire à

607
00:51:37,420 --> 00:51:41,940
ainsi que de supprimer tous les arbres de notre forêt.

608
00:51:41,940 --> 00:51:46,470
Selon votre application, vous allez probablement vouloir appeler retirer la forêt

609
00:51:46,470 --> 00:51:49,780
au lieu de réellement passer par tous les arbres vous-même.

610
00:51:49,780 --> 00:51:53,430
Mais si vous avez effectué des arbres temporaires, vous aurez envie de libérer ça.

611
00:51:53,430 --> 00:51:59,060
Vous savez que votre meilleur code, si vous savez où vous allouez de la mémoire.

612
00:51:59,060 --> 00:52:04,330
Et si vous y aller, commencer par f'ing même contrôle pour malloc,

613
00:52:04,330 --> 00:52:08,330
voir chaque fois que vous malloc et faire en sorte que vous libérer de tout cela

614
00:52:08,330 --> 00:52:10,190
mais alors juste en passant par votre code,

615
00:52:10,190 --> 00:52:14,260
comprendre où vous pourriez avoir la mémoire allouée.

616
00:52:14,260 --> 00:52:21,340
Habituellement, vous pourriez dire: «A la fin d'un fichier, je vais juste enlever la forêt sur ma forêt»,

617
00:52:21,340 --> 00:52:23,850
Donc, fondamentalement, effacer cette mémoire, sans que,

618
00:52:23,850 --> 00:52:28,310
»Et puis je vais aussi fermez le fichier, puis mon programme va quitter."

619
00:52:28,310 --> 00:52:33,810
Mais est-ce la seule fois que votre programme se termine?

620
00:52:33,810 --> 00:52:37,880
Non, parce que parfois il peut y avoir eu une erreur qui s'est produite.

621
00:52:37,880 --> 00:52:42,080
Peut-être que nous ne pouvions pas ouvrir un fichier ou nous ne pouvions pas faire un autre arbre

622
00:52:42,080 --> 00:52:49,340
ou une sorte d'erreur qui s'est passé dans le processus d'allocation de mémoire et il a retourné NULL.

623
00:52:49,340 --> 00:52:56,710
Une erreur s'est produite, puis nous sommes rentrés et quitter.

624
00:52:56,710 --> 00:53:02,040
Alors, vous voulez vous assurer que chaque fois que possible que votre programme peut cesser de fumer,

625
00:53:02,040 --> 00:53:06,980
vous voulez libérer toute votre mémoire là-bas.

626
00:53:06,980 --> 00:53:13,370
Ce n'est pas seulement va être à la fin de la fonction principale que vous quittez votre code.

627
00:53:13,370 --> 00:53:20,780
Vous voulez regarder en arrière à chaque fois que votre code potentiellement pourraient rentrer prématurément

628
00:53:20,780 --> 00:53:25,070
et puis libérer toute la mémoire du sens.

629
00:53:25,070 --> 00:53:30,830
Dites que vous l'aviez appelé make forêt et qui a retourné false.

630
00:53:30,830 --> 00:53:34,230
Ensuite, vous n'aurez probablement pas besoin de retirer votre forêt

631
00:53:34,230 --> 00:53:37,080
parce que vous n'avez pas encore une forêt.

632
00:53:37,080 --> 00:53:42,130
Mais à chaque point dans le code où vous pourriez rentrer prématurément

633
00:53:42,130 --> 00:53:46,160
vous voulez vous assurer que vous libérer de la mémoire possible.

634
00:53:46,160 --> 00:53:50,020
>> Alors, quand nous avons affaire à libérer de la mémoire et ayant des fuites potentielles,

635
00:53:50,020 --> 00:53:55,440
nous voulons non seulement d'utiliser notre jugement et notre logique

636
00:53:55,440 --> 00:54:01,850
mais aussi utiliser Valgrind pour déterminer si nous avons libéré l'ensemble de notre mémoire correctement ou non.

637
00:54:01,850 --> 00:54:09,460
Vous pouvez soit exécuter Valgrind sur Puff puis vous devez également passer

638
00:54:09,460 --> 00:54:14,020
le bon nombre de ligne de commande arguments pour Valgrind.

639
00:54:14,020 --> 00:54:18,100
Vous pouvez exécuter, mais le résultat est un peu cryptique.

640
00:54:18,100 --> 00:54:21,630
Nous avons obtenu un peu habitués à Speller, mais nous avons encore besoin d'une aide un peu plus,

641
00:54:21,630 --> 00:54:26,450
donc il fonctionne avec quelques drapeaux plus comme la fuite-check = plein,

642
00:54:26,450 --> 00:54:32,040
qui va probablement nous donner une sortie plus utile sur Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Puis une autre astuce utile lorsque vous déboguez est la commande diff.

644
00:54:39,040 --> 00:54:48,520
Vous pouvez accéder à la mise en œuvre du personnel de Huff, l'exécuter sur un fichier texte,

645
00:54:48,520 --> 00:54:55,400
puis une sortie vers un fichier binaire, un fichier binaire Huff, pour être précis.

646
00:54:55,400 --> 00:54:59,440
Alors, si vous exécutez votre propre souffle sur ce fichier binaire,

647
00:54:59,440 --> 00:55:03,950
puis idéalement, votre fichier texte fourni en sortie va être identiques

648
00:55:03,950 --> 00:55:08,200
à celui d'origine que vous avez passé po

649
00:55:08,200 --> 00:55:15,150
Ici, j'utilise hth.txt comme exemple, et c'est celui parlé dans votre spec.

650
00:55:15,150 --> 00:55:21,040
C'est littéralement juste HTH, puis un retour à la ligne.

651
00:55:21,040 --> 00:55:30,970
Mais certainement se sentir libre et vous êtes certainement encouragés à utiliser plus d'exemples

652
00:55:30,970 --> 00:55:32,620
pour votre fichier texte.

653
00:55:32,620 --> 00:55:38,110
>> Vous pouvez même prendre une photo à la compression et peut-être puis décompresser

654
00:55:38,110 --> 00:55:41,600
certains des fichiers que vous avez utilisés dans Speller comme Guerre et Paix

655
00:55:41,600 --> 00:55:46,710
ou Jane Austen ou quelque chose comme ça - ce serait plutôt cool - ou Austin Powers,

656
00:55:46,710 --> 00:55:51,880
sorte de traiter des fichiers plus volumineux, car nous ne descende pas pour elle

657
00:55:51,880 --> 00:55:55,590
si nous avons utilisé l'outil suivant ici, ls-l.

658
00:55:55,590 --> 00:56:01,150
Nous sommes habitués à ls, qui répertorie tous les contenus essentiellement dans notre répertoire courant.

659
00:56:01,150 --> 00:56:07,860
En passant le drapeau-l affiche en fait la taille de ces fichiers.

660
00:56:07,860 --> 00:56:12,690
Si vous passez par la spécification pset, il marche en fait, vous en créant le fichier binaire,

661
00:56:12,690 --> 00:56:16,590
de lui soufflant, et vous voyez que pour de très petits fichiers

662
00:56:16,590 --> 00:56:23,910
le coût de l'espace en le comprimant et la traduction de l'ensemble de ces informations

663
00:56:23,910 --> 00:56:26,980
de toutes les fréquences et les choses comme ça l'emporte sur le bénéfice réel

664
00:56:26,980 --> 00:56:30,000
de compression du fichier, en premier lieu.

665
00:56:30,000 --> 00:56:37,450
Mais si vous l'exécutez sur des fichiers texte plus long, alors vous pourriez voir que vous commencez à obtenir un certain avantage

666
00:56:37,450 --> 00:56:40,930
en comprimant les fichiers.

667
00:56:40,930 --> 00:56:46,210
>> Et puis finalement, nous avons notre GDB vieux copain, qui va certainement venir dans maniable aussi.

668
00:56:48,360 --> 00:56:55,320
>> Avons-nous des questions sur les arbres Huff ou le processus peut-être de rendre les arbres

669
00:56:55,320 --> 00:56:58,590
ou d'autres questions sur Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
D'accord. Je vais rester autour pour un peu.

671
00:57:02,570 --> 00:57:06,570
>> Merci à tous. Ce fut Procédure pas à pas 6. Et bonne chance.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]