1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Проходження - Проблема Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Гарвардський університет]

3
00:00:04,810 --> 00:00:07,240
[Це CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Привіт всім, і ласкаво просимо Проходження 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
У Puff Huff'n те, що ми робимо, будемо мати справу з файлами Хаффман стисненого

6
00:00:17,440 --> 00:00:20,740
, А потім пихкаючи його назад вгору, так розпакування цього,

7
00:00:20,740 --> 00:00:25,810
так що ми можемо перекладати з 0 і 1, які користувач посилає нам

8
00:00:25,810 --> 00:00:30,660
і перетворити його назад у вихідний текст.

9
00:00:30,660 --> 00:00:34,360
Pset 6, буде дуже здорово, тому що ви побачите деякі з інструментів

10
00:00:34,360 --> 00:00:41,730
які ви використовували в PSET 4 і 5 і PSET роду об'єднання їх в 1 дуже акуратно концепції

11
00:00:41,730 --> 00:00:43,830
коли ви приходите думати про це.

12
00:00:43,830 --> 00:00:50,110
>> Крім того, можливо, PSET 4 і 5 були найбільш складних psets, що ми повинні були запропонувати.

13
00:00:50,110 --> 00:00:53,950
Таким чином, з цього моменту, у нас є це ще 1 PSET в C,

14
00:00:53,950 --> 00:00:56,480
а після цього ми на веб-програмування.

15
00:00:56,480 --> 00:01:02,310
Так що вітаю себе для отримання більш жорстким горб CS50.

16
00:01:03,630 --> 00:01:09,760
>> Переходячи до Puff Huff'n, наш інструментарій для цього PSET збираєтеся бути Huffman дерев,

17
00:01:09,760 --> 00:01:14,700
тому розуміння не тільки як двійкові дерева роботу, але і спеціально Huffman дерев,

18
00:01:14,700 --> 00:01:16,240
як вони побудовані.

19
00:01:16,240 --> 00:01:20,210
І тоді ми будемо мати багато розподілу коду в цьому PSET,

20
00:01:20,210 --> 00:01:22,480
і ми прийшли, щоб побачити, що насправді деякі з коду

21
00:01:22,480 --> 00:01:24,670
Ми не зможемо повною мірою зрозуміти все ж,

22
00:01:24,670 --> 00:01:30,080
і тому ті будуть. с файлами, але потім їх супроводжуючих. ч. файлів

23
00:01:30,080 --> 00:01:34,300
дасть нам достатньо розуміння того, що нам потрібно, так що ми знаємо, як ці функції працюють

24
00:01:34,300 --> 00:01:38,100
або принаймні те, що вони повинні робити - їх входи і виходи -

25
00:01:38,100 --> 00:01:40,760
навіть якщо ми не знаємо, що відбувається в чорному ящику

26
00:01:40,760 --> 00:01:44,090
або не розуміють, що відбувається в чорному ящику всередині.

27
00:01:44,090 --> 00:01:49,400
І, нарешті, як зазвичай, ми маємо справу з новими структурами даних,

28
00:01:49,400 --> 00:01:51,840
конкретні види вузлів, які вказують на певні речі,

29
00:01:51,840 --> 00:01:56,080
і ось що має ручку і папір не тільки для процесу проектування

30
00:01:56,080 --> 00:01:58,470
і коли ви намагаєтеся з'ясувати, як ваші PSET повинні працювати

31
00:01:58,470 --> 00:02:00,520
але і під час налагодження.

32
00:02:00,520 --> 00:02:06,140
Ви можете мати GDB разом з пером і папером в той час як ви берете те, що значення,

33
00:02:06,140 --> 00:02:09,320
де ваші стрілки вказують, тощо.

34
00:02:09,320 --> 00:02:13,720
>> Перш за все, давайте подивимося на дерева Хаффмана.

35
00:02:13,720 --> 00:02:19,600
Huffman дерев бінарні дерева, а це означає, що кожен вузол має тільки 2 дітей.

36
00:02:19,600 --> 00:02:24,870
У дерев Хаффмана характерним є те, що найбільш часті значення

37
00:02:24,870 --> 00:02:27,140
представлена ​​найменшою кількістю бітів.

38
00:02:27,140 --> 00:02:32,690
Ми бачили в лекції приклади коду Морзе, який вид консолідованого кілька листів.

39
00:02:32,690 --> 00:02:38,030
Якщо ви намагаєтеся перевести або E, наприклад,

40
00:02:38,030 --> 00:02:43,940
ви перекладаєте, що часто, так що замість того, щоб використовувати весь набір бітів

41
00:02:43,940 --> 00:02:48,640
виділено на що звичайний тип даних, стискати його до менше,

42
00:02:48,640 --> 00:02:53,730
, А потім ці листи, які представлені рідше представлені з більш біт

43
00:02:53,730 --> 00:02:59,840
тому що ви можете собі це дозволити, коли ви важите з частот, що ці літери з'являються.

44
00:02:59,840 --> 00:03:03,020
У нас же ідея тут в дерева Huffman

45
00:03:03,020 --> 00:03:12,360
де ми робимо ланцюг, свого роду шлях, щоб дістатися до певних символів.

46
00:03:12,360 --> 00:03:14,470
І тоді персонажі, які мають найбільш частоти

47
00:03:14,470 --> 00:03:17,940
будуть представлені з найменшою кількістю бітів.

48
00:03:17,940 --> 00:03:22,020
>> Спосіб, яким ви побудувати дерево Хаффмана

49
00:03:22,020 --> 00:03:27,430
шляхом розміщення всіх персонажів, які з'являються в тексті

50
00:03:27,430 --> 00:03:30,630
і розрахунку їх частота, як часто вони з'являються.

51
00:03:30,630 --> 00:03:33,880
Це може бути або з рахунку, скільки разів ці літери з'являються

52
00:03:33,880 --> 00:03:40,270
або, можливо, відсоток з усіх символів, скільки кожен з'являється.

53
00:03:40,270 --> 00:03:44,270
І те, що ви робите, коли у вас є все, що намітили,

54
00:03:44,270 --> 00:03:49,060
Потім ви подивитеся на 2 низькі частоти, а потім приєднатися до них як брати і сестри

55
00:03:49,060 --> 00:03:55,660
де то батьківський вузол має частоту, яка є сумою своїх 2 дітей.

56
00:03:55,660 --> 00:04:00,870
І тоді ви за угодою сказати, що лівий вузол,

57
00:04:00,870 --> 00:04:03,770
Ви будете слідувати, що, слідуючи 0 галузь,

58
00:04:03,770 --> 00:04:08,140
, А потім правий вузол 1 філії.

59
00:04:08,140 --> 00:04:16,040
Як ми бачили в азбуці Морзе, один глюк, що якщо ви тільки що звуковий сигнал і звуковий сигнал

60
00:04:16,040 --> 00:04:18,120
було неоднозначним.

61
00:04:18,120 --> 00:04:22,430
Це може бути або 1 букву або це може бути послідовність з 2 букв.

62
00:04:22,430 --> 00:04:27,790
І те, що Huffman дерев робить це тому, що за характером персонажів

63
00:04:27,790 --> 00:04:34,140
або наші остаточні фактичні символи буття останнього вузла на гілці -

64
00:04:34,140 --> 00:04:39,300
ми маємо на увазі тих, хто, як листя - силу того, що там не може бути ніякої двозначності

65
00:04:39,300 --> 00:04:45,160
, В термінах якої листі ви намагаєтеся кодувати з послідовністю бітів

66
00:04:45,160 --> 00:04:50,670
тому що ніде уздовж бітів, які складають 1 лист

67
00:04:50,670 --> 00:04:55,960
Ви будете стикатися ще цілий лист, і там не буде ніякої плутанини немає.

68
00:04:55,960 --> 00:04:58,430
Але ми будемо йти в прикладах, які ви, хлопці, можете фактично бачити, що

69
00:04:58,430 --> 00:05:02,120
замість нас просто кажу вам, що це правда.

70
00:05:02,120 --> 00:05:06,390
>> Давайте подивимося на простий приклад дерево Хаффмана.

71
00:05:06,390 --> 00:05:09,380
У мене є рядок, що тут має довжину 12 символів.

72
00:05:09,380 --> 00:05:14,010
У мене є 4 В, 6 сніданок, і 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Моїм першим кроком було б розраховувати.

74
00:05:17,270 --> 00:05:20,760
Скільки разів з'являються? Схоже 4 рази на рядок.

75
00:05:20,760 --> 00:05:25,060
У з'являється 6 разів, а C з'являється в 2 рази.

76
00:05:25,060 --> 00:05:28,970
Природно, що я збираюся сказати, я використовую B найчастіше,

77
00:05:28,970 --> 00:05:35,970
Тому я хочу, щоб представляти B з найменшою кількістю бітів, найменше число 0 і 1.

78
00:05:35,970 --> 00:05:42,600
А потім я також збираюся чекати C вимагати найбільшу кількість 0 і 1, а також.

79
00:05:42,600 --> 00:05:48,550
Перше, що я зробив тут я помістив їх у порядку зростання по частоті.

80
00:05:48,550 --> 00:05:52,710
Ми бачимо, що C і A, ті наші 2 низькі частоти.

81
00:05:52,710 --> 00:06:00,290
Ми створюємо батьківський вузол, і що батьківський вузол не має листі, пов'язані з ним,

82
00:06:00,290 --> 00:06:05,070
але у нього є частота, яка є сумою.

83
00:06:05,070 --> 00:06:08,780
Сума стає 2 + 4, який є 6.

84
00:06:08,780 --> 00:06:10,800
Потім ми слідуємо лівої гілки.

85
00:06:10,800 --> 00:06:14,970
Якби ми були на що 6 вузлів, то ми будемо слідувати від 0 до дістатися до C

86
00:06:14,970 --> 00:06:17,450
, А потім 1, щоб дістатися до A.

87
00:06:17,450 --> 00:06:20,300
Так що тепер у нас є 2 вузла.

88
00:06:20,300 --> 00:06:23,920
У нас є значення 6, а потім у нас також є ще один вузол із значенням 6.

89
00:06:23,920 --> 00:06:28,550
І ось ці 2 не тільки 2-низька, але і тільки 2, які залишилися,

90
00:06:28,550 --> 00:06:33,820
тому ми приєднуємося до тих іншим батьком, з сумою буття 12.

91
00:06:33,820 --> 00:06:36,300
Так що тут у нас є дерево Хаффмана

92
00:06:36,300 --> 00:06:40,020
де, щоб дістатися до B, це було б просто біт 1

93
00:06:40,020 --> 00:06:45,430
, А потім, щоб дістатися до нас буде 01, а потім C має 00.

94
00:06:45,430 --> 00:06:51,300
Таким чином, тут ми бачимо, що в основному ми, що представляють ці символи з 1 або 2 біти

95
00:06:51,300 --> 00:06:55,160
де B, як і передбачалося, має найменше.

96
00:06:55,160 --> 00:07:01,730
І тоді ми очікували C, щоб мати більшість, але так як це такий маленький дерево Хаффмана,

97
00:07:01,730 --> 00:07:06,020
Потім також представлені 2 біти, а не десь в середині.

98
00:07:07,820 --> 00:07:11,070
>> Просто, щоб перейти на інший простий приклад дерево Хаффмана,

99
00:07:11,070 --> 00:07:19,570
у вас є рядок "Hello".

100
00:07:19,570 --> 00:07:25,360
Що ви робите, спочатку ви б сказати скільки разів H з'явиться в цьому?

101
00:07:25,360 --> 00:07:34,200
H з'являється один раз, а потім електронної з'являється один раз, і тоді ми маємо л з'являтися в два рази

102
00:07:34,200 --> 00:07:36,580
і про з'являються один раз.

103
00:07:36,580 --> 00:07:44,310
І так, то ми очікуємо, яке букву, яка буде представлена ​​найменшою кількістю біт?

104
00:07:44,310 --> 00:07:47,450
[Студент] л. >> Л. Так. л прав.

105
00:07:47,450 --> 00:07:50,730
Ми очікуємо, що я повинен бути представлений найменшу кількість біт

106
00:07:50,730 --> 00:07:55,890
тому що я все використовується в рядок "Hello".

107
00:07:55,890 --> 00:08:04,280
Що я буду робити тепер витягнути ці вузли.

108
00:08:04,280 --> 00:08:15,580
У мене є 1, який є H, а потім ще 1, який є електронною, а потім 1, що про -

109
00:08:15,580 --> 00:08:23,410
Прямо зараз я ставлю їх в порядок - і потім 2, яка є л.

110
00:08:23,410 --> 00:08:32,799
Тоді я кажу так, як я побудови дерева Хаффмана, щоб знайти 2 вузлів з найменшими частотами

111
00:08:32,799 --> 00:08:38,010
і зробити їх братами і сестрами по створенню батьківського вузла.

112
00:08:38,010 --> 00:08:41,850
Тут у нас є 3 вузлам з найнижчою частотою. Вони все 1.

113
00:08:41,850 --> 00:08:50,620
І ось ми вибрати, який з ми збираємося зв'язати в першу чергу.

114
00:08:50,620 --> 00:08:54,850
Припустимо, я вибираю H і E.

115
00:08:54,850 --> 00:09:01,150
Сума 1 + 1 = 2, але на цей вузол не має листі, пов'язані з ним.

116
00:09:01,150 --> 00:09:04,440
Він просто тримає значення.

117
00:09:04,440 --> 00:09:10,950
Зараз ми подивимося на наступні 2 низькі частоти.

118
00:09:10,950 --> 00:09:15,590
Це 2 і 1. Це може бути будь-який з цих 2, але я збираюся вибрати цю.

119
00:09:15,590 --> 00:09:18,800
Сума 3.

120
00:09:18,800 --> 00:09:26,410
І, нарешті, у мене тільки 2 лівих, так те, що стає 5.

121
00:09:26,410 --> 00:09:32,010
Тоді тут, як і очікувалося, якщо я заповнюю в кодуванні для того,

122
00:09:32,010 --> 00:09:37,480
1s завжди правої гілки і 0 є ліву.

123
00:09:37,480 --> 00:09:45,880
Тоді ми маємо л представлені лише 1 біт, а потім на 2 O

124
00:09:45,880 --> 00:09:52,360
, А потім е на 2, а потім H падає до 3 біт.

125
00:09:52,360 --> 00:09:59,750
Таким чином, ви можете передавати це повідомлення "Hello", а насправді використання символів

126
00:09:59,750 --> 00:10:02,760
на тільки 0 і 1.

127
00:10:02,760 --> 00:10:07,910
Однак слід пам'ятати, що в ряді випадків ми мали зв'язків з нашою частоті.

128
00:10:07,910 --> 00:10:11,900
Ми могли б або приєдналися до H і O Рік може бути.

129
00:10:11,900 --> 00:10:15,730
Або потім, коли у нас було л представлений 2

130
00:10:15,730 --> 00:10:19,410
а також приєднався до однієї представлений 2, ми могли би пов'язаний жоден.

131
00:10:19,410 --> 00:10:23,630
>> І тому, коли ви посилаєте 0 і 1, що насправді не гарантують

132
00:10:23,630 --> 00:10:27,090
що одержувач може повністю прочитати повідомлення прямо з місця в кар'єр

133
00:10:27,090 --> 00:10:30,490
тому що вони не могли знати, які рішення ви зробили.

134
00:10:30,490 --> 00:10:34,920
Тому, коли ми маємо справу з стисненням Хаффмана,

135
00:10:34,920 --> 00:10:40,090
так чи інакше ми повинні сказати одержувача наше послання, як ми вирішили -

136
00:10:40,090 --> 00:10:43,470
Вони повинні знати, якоїсь додаткової інформації

137
00:10:43,470 --> 00:10:46,580
На додаток до повідомлення стислим.

138
00:10:46,580 --> 00:10:51,490
Вони повинні розуміти, що дерево насправді виглядає,

139
00:10:51,490 --> 00:10:55,450
як ми насправді зробили ці рішення.

140
00:10:55,450 --> 00:10:59,100
>> Тут ми просто робили прикладів, заснованих на фактичну кількість,

141
00:10:59,100 --> 00:11:01,550
але іноді ви також можете мати дерево Хаффмана

142
00:11:01,550 --> 00:11:05,760
в залежності від частоти, на якій літери з'являються, і це точно такий же процес.

143
00:11:05,760 --> 00:11:09,090
Тут я висловлюю це в термінах відсотки або частки,

144
00:11:09,090 --> 00:11:11,290
і ось одне і те ж.

145
00:11:11,290 --> 00:11:15,300
Я знаходжу, 2-низький, скласти їх, наступні 2 низький, скласти їх,

146
00:11:15,300 --> 00:11:19,390
поки у мене є повне дерево.

147
00:11:19,390 --> 00:11:23,610
Хоча ми могли б зробити це в будь-якому випадку, коли ми маємо справу з відсотками,

148
00:11:23,610 --> 00:11:27,760
, Що означає, що ми поділом речей, і справа з десятими або, скоріше, плаває

149
00:11:27,760 --> 00:11:30,900
якщо ми думаємо про структури даних з голови.

150
00:11:30,900 --> 00:11:32,540
Що ми знаємо про поплавцях?

151
00:11:32,540 --> 00:11:35,180
Що таке загальна проблема, коли ми маємо справу з поплавками?

152
00:11:35,180 --> 00:11:38,600
[Студент] Неточні арифметика. >> Да. Неточність.

153
00:11:38,600 --> 00:11:43,760
Через плаваючою точкою неточність, для цього PSET, так що ми впевнені,

154
00:11:43,760 --> 00:11:49,450
що ми не втрачають значення, то насправді ми будемо мати справу з графом.

155
00:11:49,450 --> 00:11:54,880
Так що якщо ви повинні були думати вузла Хаффман, якщо ви подивитеся на структуру тут,

156
00:11:54,880 --> 00:12:01,740
якщо ви подивитеся на зелені воно має частоту пов'язаних з ним

157
00:12:01,740 --> 00:12:08,760
а також він вказує на вузол, щоб його лівий, а також вузол в своєму праві.

158
00:12:08,760 --> 00:12:13,970
А потім червоні там теж є характер, пов'язаний з ними.

159
00:12:13,970 --> 00:12:18,900
Ми не збираємося робити окремі для батьків, а потім остаточне вузлів,

160
00:12:18,900 --> 00:12:23,680
який ми називаємо листям, а ті будуть просто порожні значення.

161
00:12:23,680 --> 00:12:31,050
Для кожного вузла ми будемо мати характер, символ, який представляє вузол,

162
00:12:31,050 --> 00:12:40,490
Потім частоти, а також покажчик на його ліву дитини, а також його права дитини.

163
00:12:40,490 --> 00:12:45,680
Листя, які знаходяться на самому дні, буде також мати покажчики на ноди

164
00:12:45,680 --> 00:12:49,550
ліворуч від них, а також їх право, але так як ці значення не вказує на фактичне вузлів,

165
00:12:49,550 --> 00:12:53,970
що б їх вартість буде? >> [Студент] NULL. >> NULL. Саме так.

166
00:12:53,970 --> 00:12:58,430
Ось приклад того, як можна представляти частоти в поплавців,

167
00:12:58,430 --> 00:13:02,130
але ми збираємося мати справу з цим з цілими числами,

168
00:13:02,130 --> 00:13:06,780
так що все, що я зробив це змінити тип даних немає.

169
00:13:06,780 --> 00:13:09,700
>> Давайте перейдемо до трохи більше складний приклад.

170
00:13:09,700 --> 00:13:13,360
Але тепер, коли ми зробили прості, це просто той самий процес.

171
00:13:13,360 --> 00:13:20,290
Ви знайдете 2-низькі частоти, підвести частот

172
00:13:20,290 --> 00:13:22,450
і ось нова частота вашого батьківського вузла,

173
00:13:22,450 --> 00:13:29,310
, Який потім вказує на її лівому з 0 філії і право з 1 філії.

174
00:13:29,310 --> 00:13:34,200
Якщо у нас є рядок "Це CS50", то ми порахувати, скільки разів буде згадано T,

175
00:13:34,200 --> 00:13:38,420
ч згадувалося, I, S, C, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Потім, що я зробив тут з червоними вузлами я просто посадив,

177
00:13:42,010 --> 00:13:48,530
Я сказав, що я буду мати ці символи в кінцевому підсумку в нижній частині мого дерева.

178
00:13:48,530 --> 00:13:51,740
Ті збираються бути все листя.

179
00:13:51,740 --> 00:13:58,200
Потім, що я зробив, я сортував їх за частотою в порядку зростання,

180
00:13:58,200 --> 00:14:02,950
і це насправді так, що PSET код робить це

181
00:14:02,950 --> 00:14:07,550
це сортує їх по частоті, а потім в алфавітному порядку.

182
00:14:07,550 --> 00:14:13,870
Так воно і є число, а потім в алфавітному порядку за частотою.

183
00:14:13,870 --> 00:14:18,520
Тоді що я буду робити, я б знайти 2 низька. Це 0 і 5.

184
00:14:18,520 --> 00:14:22,390
Я б скласти їх, і ось 2. Тоді я буду продовжувати, знайти найближчі 2 низька.

185
00:14:22,390 --> 00:14:26,100
Ці два 1s, а потім вони стають 2, а.

186
00:14:26,100 --> 00:14:31,570
Тепер я знаю, що мій наступний крок буде приєднання до найменшим числом,

187
00:14:31,570 --> 00:14:41,380
яка є T, 1, а потім вибрати один з вузлів, який має 2 як частота.

188
00:14:41,380 --> 00:14:44,560
Так що тут у нас є 3 варіанти.

189
00:14:44,560 --> 00:14:47,980
Що я буду робити для слайдів тільки візуально змінити їх для вас

190
00:14:47,980 --> 00:14:51,790
так що ви можете бачити, як я будую його.

191
00:14:51,790 --> 00:14:59,040
Який код і розподілу коду збираються робити буде приєднатися до T один

192
00:14:59,040 --> 00:15:01,410
з 0 до 5 вузлів.

193
00:15:01,410 --> 00:15:05,060
Отже, що суми до 3, а потім ми продовжимо процес.

194
00:15:05,060 --> 00:15:08,660
2 і 2 зараз є найнижчими, так що потім ці суми до 4.

195
00:15:08,660 --> 00:15:12,560
Кожен наступний досі? Добре.

196
00:15:12,560 --> 00:15:16,410
А після цього у нас є 3 і 3, які повинні бути додані вгору,

197
00:15:16,410 --> 00:15:21,650
так що знову я просто включіть його, так що ви можете бачити візуально так, щоб він не занадто брудним.

198
00:15:21,650 --> 00:15:25,740
Тоді у нас є 6, а потім наш останній крок зараз, що у нас є тільки 2 вузлів

199
00:15:25,740 --> 00:15:30,440
Підсумовуючи ці щоб коріння нашої дерева, яке дорівнює 10.

200
00:15:30,440 --> 00:15:34,100
І число 10 має сенс, оскільки кожен вузол представляє,

201
00:15:34,100 --> 00:15:40,750
їх значення, їх частота номер, було, скільки разів вони з'явилися в рядок,

202
00:15:40,750 --> 00:15:46,350
а то у нас 5 символів в наш ланцюжок, так що має сенс.

203
00:15:48,060 --> 00:15:52,320
Якщо ми дивимося на те, як ми насправді кодувати його,

204
00:15:52,320 --> 00:15:56,580
Як і очікувалося, я і S, які з'являються найчастіше

205
00:15:56,580 --> 00:16:01,350
представлені найменшу кількість біт.

206
00:16:03,660 --> 00:16:05,660
>> Будьте обережні.

207
00:16:05,660 --> 00:16:09,780
У дерев Хаффмана випадок насправді має значення.

208
00:16:09,780 --> 00:16:13,670
Прописні S відрізняється від рядкової с.

209
00:16:13,670 --> 00:16:21,260
Якби ми мали "Це CS50" з великої літери, то рядкові и буде з'являтися тільки в два рази,

210
00:16:21,260 --> 00:16:27,120
буде вузол з 2 в якості свого значення, а потім прописні S буде тільки один раз.

211
00:16:27,120 --> 00:16:33,440
І тоді ваше дерево буде змінити структури, тому що ви насправді мають додатковий аркуш тут.

212
00:16:33,440 --> 00:16:36,900
Але сума все одно буде 10.

213
00:16:36,900 --> 00:16:39,570
Це те, що ми насправді буде викликом контрольної суми,

214
00:16:39,570 --> 00:16:44,060
Крім всіх підрахунків.

215
00:16:46,010 --> 00:16:50,990
>> Тепер, коли ми розглянули Huffman дерев, ми можемо зануритися в Huff'n Puff, PSET.

216
00:16:50,990 --> 00:16:52,900
Ми збираємося почати з розділу питань,

217
00:16:52,900 --> 00:16:57,990
і це відбувається, щоб ви звикли з бінарними деревами і як працювати навколо цього:

218
00:16:57,990 --> 00:17:03,230
малювання вузлів, створюючи свій власний ЬурейеЕ структури для вузла,

219
00:17:03,230 --> 00:17:07,230
і, бачачи, як ви могли б вставити в бінарному дереві, той, який сортується,

220
00:17:07,230 --> 00:17:09,050
через нього, і тому подібне.

221
00:17:09,050 --> 00:17:14,560
Це знання, безумовно, допоможе вам, коли ви занурюєтеся в частині Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
з PSET.

223
00:17:19,150 --> 00:17:26,329
У стандартному виданні PSET, ваше завдання полягає в реалізації Puff,

224
00:17:26,329 --> 00:17:30,240
і в хакерської версії вашим завданням є реалізація Хафф.

225
00:17:30,240 --> 00:17:38,490
Що Хафф робить це бере текст, а потім він переводить його в 0 і 1,

226
00:17:38,490 --> 00:17:41,990
так що процес, який ми зробили вище, де ми розраховували частот

227
00:17:41,990 --> 00:17:50,970
, А потім зробив дерева, а потім сказав: "Як я можу отримати T?"

228
00:17:50,970 --> 00:17:54,840
T представлена ​​на 100, тощо,

229
00:17:54,840 --> 00:17:58,860
, А потім Хафф б текст, а потім висновок, що двійковий файл.

230
00:17:58,860 --> 00:18:04,920
Але й тому, що ми знаємо, що ми хочемо, щоб наші одержувач повідомлення

231
00:18:04,920 --> 00:18:11,790
відтворити точно таку ж дерево, воно також включає інформацію про частоту отсчетов.

232
00:18:11,790 --> 00:18:17,980
Потім з Puff дано двійковий файл з 0 і 1

233
00:18:17,980 --> 00:18:21,740
і також з урахуванням інформації про частоти.

234
00:18:21,740 --> 00:18:26,740
Ми переводимо всі ці 0 і 1 повертається у вихідне повідомлення, що було,

235
00:18:26,740 --> 00:18:29,350
так що ми розпакування цього.

236
00:18:29,350 --> 00:18:36,450
Якщо ви робите Standard Edition, вам не потрібно здійснювати Хафф,

237
00:18:36,450 --> 00:18:39,290
так, то ви можете просто використовувати персонал реалізації Хафф.

238
00:18:39,290 --> 00:18:42,080
Є інструкції в специфікації про те, як це зробити.

239
00:18:42,080 --> 00:18:48,780
Ви можете запустити персоналу здійснення Хафф на певний текстовий файл

240
00:18:48,780 --> 00:18:53,270
а потім використовувати цей вихід як ваш внесок у затяжку.

241
00:18:53,270 --> 00:18:59,330
>> Як я вже говорив, у нас є багато розподілу коду для цього.

242
00:18:59,330 --> 00:19:01,810
Я збираюся почати ходити через нього.

243
00:19:01,810 --> 00:19:04,400
Я буду проводити більшу частину часу на. Ч. файлів

244
00:19:04,400 --> 00:19:07,660
тому що в. с файлами, тому що у нас є. ч

245
00:19:07,660 --> 00:19:11,650
і що дає нам прототипи функцій,

246
00:19:11,650 --> 00:19:15,520
Ми не в повній мірі повинні розуміти точно -

247
00:19:15,520 --> 00:19:20,280
Якщо ви не розумієте, що відбувається в. Файлів с, то не турбуйтеся надто багато,

248
00:19:20,280 --> 00:19:23,600
але обов'язково спробую поглянути, тому що це може дати деякі підказки

249
00:19:23,600 --> 00:19:29,220
і це корисно, щоб звикнути до читання коду інших людей.

250
00:19:38,940 --> 00:19:48,270
>> Дивлячись на huffile.h, в коментарях він заявляє шар абстракції для Huffman-кодованих файлів.

251
00:19:48,270 --> 00:20:01,660
Якщо ми підемо вниз, ми бачимо, що є максимум 256 символів, що ми, можливо, буде потрібно коди.

252
00:20:01,660 --> 00:20:05,480
Це включає в себе всі букви алфавіту - прописні і рядкові -

253
00:20:05,480 --> 00:20:08,250
, А потім символи і цифри, і т.д.

254
00:20:08,250 --> 00:20:11,930
Тоді тут у нас є чарівний номер, що ідентифікує Huffman-кодованих файлів.

255
00:20:11,930 --> 00:20:15,890
У коді Хаффмана вони будуть мати певну кількість магії

256
00:20:15,890 --> 00:20:18,560
пов'язані з заголовка.

257
00:20:18,560 --> 00:20:21,110
Це може виглядати як випадкове число, магія,

258
00:20:21,110 --> 00:20:27,160
Але якщо ви насправді переводити його в ASCII, то це насправді викладає Хафф.

259
00:20:27,160 --> 00:20:34,290
Тут ми маємо структуру для Хаффман файл в кодуванні.

260
00:20:34,290 --> 00:20:39,670
Там всі ці характеристики, пов'язані з файлом Хафф.

261
00:20:39,670 --> 00:20:47,080
Тоді тут ми маємо заголовок файлу Хафф, тому ми називаємо його Huffeader

262
00:20:47,080 --> 00:20:50,810
Замість додавання додаткових годин, тому що звучить однаково в будь-якому випадку.

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

264
00:20:52,720 --> 00:20:57,790
У нас є магічне число пов'язаних з ним.

265
00:20:57,790 --> 00:21:09,040
Якщо це реальний файл Хафф, це буде номер нагорі, це чарівний.

266
00:21:09,040 --> 00:21:14,720
І тоді вона буде мати масив.

267
00:21:14,720 --> 00:21:18,750
Таким чином, для кожного символу, в якому є 256,

268
00:21:18,750 --> 00:21:24,760
він збирається перерахувати, що частота цих символів у файлі Хафф.

269
00:21:24,760 --> 00:21:28,090
І, нарешті, у нас є контрольна сума для частот,

270
00:21:28,090 --> 00:21:32,160
, Яка повинна бути сума цих частотах.

271
00:21:32,160 --> 00:21:36,520
Так ось що Huffeader є.

272
00:21:36,520 --> 00:21:44,600
Тоді у нас є деякі функції, які повертають наступний біт у файлі Huff

273
00:21:44,600 --> 00:21:52,580
а також пише трохи, щоб файл Хафф, а потім ця функція тут, hfclose,

274
00:21:52,580 --> 00:21:54,650
що насправді закриває файл Хафф.

275
00:21:54,650 --> 00:21:57,290
Раніше ми мали справу з прямим просто Fclose,

276
00:21:57,290 --> 00:22:01,190
Але коли у вас є файл Хафф, а fclosing це

277
00:22:01,190 --> 00:22:06,080
те, що ви насправді збираєтеся зробити, це hfclose і hfopen його.

278
00:22:06,080 --> 00:22:13,220
Ті конкретні функції Хафф файли, які ми збираємося мати справу.

279
00:22:13,220 --> 00:22:19,230
Тоді ось ми читаємо в заголовку, а потім написати заголовок.

280
00:22:19,230 --> 00:22:25,700
>> Просто читаючи. Ч файлу ми можемо отримати вид сенс того, що файл Хафф може бути,

281
00:22:25,700 --> 00:22:32,480
які характеристики у нього є, фактично не вдаючись у huffile.c,

282
00:22:32,480 --> 00:22:36,750
, Який, якщо ми заглибимося в, буде трохи складніше.

283
00:22:36,750 --> 00:22:41,270
Він має всі файлового введення / виводу тут справу з покажчиками.

284
00:22:41,270 --> 00:22:48,010
Тут ми бачимо, що коли ми називаємо hfread, наприклад, це все ще справа з FREAD.

285
00:22:48,010 --> 00:22:53,050
Ми не позбутися від цих функцій повністю, але ми посилаємо тих, хто буде піклуватися

286
00:22:53,050 --> 00:22:59,760
всередині файлу Хафф а не робити все це самі.

287
00:22:59,760 --> 00:23:02,300
Ви можете відчувати себе вільно для сканування через це, якщо вам цікаво

288
00:23:02,300 --> 00:23:08,410
і йдуть, а шкірку шар назад небагато.

289
00:23:20,650 --> 00:23:24,060
>> Наступний файл, який ми збираємося дивитися на це tree.h.

290
00:23:24,060 --> 00:23:30,210
До цього в Покрокове керівництво ковзає ми сказали, що ми очікуємо Хаффман вузла

291
00:23:30,210 --> 00:23:32,960
і ми зробили ЬурейеЕ вузла структури.

292
00:23:32,960 --> 00:23:38,360
Ми очікуємо, що це є символ, частоти, а потім 2 зірки вузла.

293
00:23:38,360 --> 00:23:41,870
У цьому випадку те, що ми робимо це по суті той же

294
00:23:41,870 --> 00:23:46,880
тільки замість вузла ми будемо називати їх деревами.

295
00:23:48,790 --> 00:23:56,760
У нас є функція, яка при виклику зробити дерево він повертає вам покажчик дерева.

296
00:23:56,760 --> 00:24:03,450
Назад до Speller, коли ви робили новий вузол

297
00:24:03,450 --> 00:24:11,410
Ви сказали вузол * Нове слово = Танос (SizeOf) тощо.

298
00:24:11,410 --> 00:24:17,510
В принципі, mktree буде мати справу з цим для вас.

299
00:24:17,510 --> 00:24:20,990
Аналогічним чином, коли ви хочете видалити дерево,

300
00:24:20,990 --> 00:24:24,810
так що, по суті, звільняючи дерево, коли ви закінчите з цим,

301
00:24:24,810 --> 00:24:33,790
замість явного виклику безкоштовно на те, що насправді ви просто збираєтеся використовувати функцію rmtree

302
00:24:33,790 --> 00:24:40,360
де ви передаєте покажчик на це дерево, а потім tree.c подбає про це за вас.

303
00:24:40,360 --> 00:24:42,490
>> Ми дивимося в tree.c.

304
00:24:42,490 --> 00:24:47,240
Ми очікуємо, що ті ж функції, за винятком побачити реалізацію, а також.

305
00:24:47,240 --> 00:24:57,720
Як ми і очікували, коли ви дзвоните mktree це mallocs обсягу дерева в покажчик,

306
00:24:57,720 --> 00:25:03,190
ініціалізує всі значення на NULL значення, так 0s або нулі,

307
00:25:03,190 --> 00:25:08,280
і потім повертає покажчик на це дерево, яке ви тільки що malloc'd до вас.

308
00:25:08,280 --> 00:25:13,340
Ось коли ви дзвоните видалити дерево він спочатку переконується, що ви не подвійне звільнення.

309
00:25:13,340 --> 00:25:18,320
Він упевнений, що у вас дійсно є дерево, яке ви хочете видалити.

310
00:25:18,320 --> 00:25:23,330
Ось тому, що дерево також включає в себе дітей,

311
00:25:23,330 --> 00:25:29,560
що вона робить це рекурсивно викликає видалення дерев на лівому вузлі дерева

312
00:25:29,560 --> 00:25:31,650
а також право вузлів.

313
00:25:31,650 --> 00:25:37,790
Перш, ніж він звільняє батьків, він повинен звільнити дітей.

314
00:25:37,790 --> 00:25:42,770
Батько також взаємозамінні з коренем.

315
00:25:42,770 --> 00:25:46,500
Перший в історії батька, так як пра-пра-пра-пра-дідусь

316
00:25:46,500 --> 00:25:52,130
або бабуся дерево, спочатку ми повинні звільнити до рівня першого.

317
00:25:52,130 --> 00:25:58,490
Так що пройти на дно, вільне їх, а потім повернутися вгору, вільні тих, і т.д.

318
00:26:00,400 --> 00:26:02,210
Так що це дерево.

319
00:26:02,210 --> 00:26:04,240
>> Тепер ми подивимося на ліс.

320
00:26:04,240 --> 00:26:09,860
Ліс, де ви розмістите всі ваші дерев Хаффмана.

321
00:26:09,860 --> 00:26:12,910
Він говорив, що ми будемо мати те, що називається ділянка

322
00:26:12,910 --> 00:26:22,320
, Який містить покажчик на дерево, а також покажчик на ділянку називається наступна.

323
00:26:22,320 --> 00:26:28,480
Яка структура робить цей вид виглядає?

324
00:26:29,870 --> 00:26:32,490
Це почасти говорить, що це там.

325
00:26:34,640 --> 00:26:36,700
Право тут.

326
00:26:37,340 --> 00:26:39,170
Зв'язаний список.

327
00:26:39,170 --> 00:26:44,590
Ми бачимо, що коли у нас є сюжет це як зв'язаний список ділянок.

328
00:26:44,590 --> 00:26:53,020
Ліс визначається як зв'язаний список ділянок,

329
00:26:53,020 --> 00:26:58,100
і так структурі лісу ми просто будемо мати покажчик на нашому першій ділянці

330
00:26:58,100 --> 00:27:02,740
і що ділянка має дерево в ньому або, скоріше, вказує на дереві

331
00:27:02,740 --> 00:27:06,190
, А потім вказує на наступну ділянку, так далі, і так далі.

332
00:27:06,190 --> 00:27:11,100
Для того, щоб ліс ми називаємо mkforest.

333
00:27:11,100 --> 00:27:14,930
Тоді у нас є кілька досить корисних функцій тут.

334
00:27:14,930 --> 00:27:23,240
Ми повинні вибрати, де ви проходите в ліс, а потім повертається значення дерева *,

335
00:27:23,240 --> 00:27:25,210
покажчик на дерево.

336
00:27:25,210 --> 00:27:29,370
Який вибір зробить, вона буде йти в ліс, що ви вказуючи на

337
00:27:29,370 --> 00:27:35,240
потім видалити дерево з найнижчою частотою від лісу

338
00:27:35,240 --> 00:27:38,330
, А потім дати вам покажчик на дерево.

339
00:27:38,330 --> 00:27:43,030
Після того як ви зателефонуєте вибрати, дерево не буде існувати в лісі більше,

340
00:27:43,030 --> 00:27:48,550
але повернене значення є покажчиком на цьому дереві.

341
00:27:48,550 --> 00:27:50,730
Тоді у вас є завод.

342
00:27:50,730 --> 00:27:57,420
За умови, що ви передаєте покажчик на дерево, яке має не-0 частот,

343
00:27:57,420 --> 00:28:04,040
що завод буде робити це буде ліс, взяти дерев і рослин, що дерево всередині лісу.

344
00:28:04,040 --> 00:28:06,370
Тут ми маємо rmforest.

345
00:28:06,370 --> 00:28:11,480
Схожі видалити дерево, яке в основному звільнив усіх наших дерев для нас,

346
00:28:11,480 --> 00:28:16,600
видалити ліс буде безкоштовно все, що міститься в цьому лісі.

347
00:28:16,600 --> 00:28:24,890
>> Якщо ми подивимося на forest.c, ми очікуємо, що принаймні 1 rmtree команди там,

348
00:28:24,890 --> 00:28:30,090
тому що, щоб звільнити пам'ять в лісі, якщо ліс є дерева в ньому,

349
00:28:30,090 --> 00:28:32,930
то в кінцевому підсумку ви будете мати, щоб видалити ці дерева теж.

350
00:28:32,930 --> 00:28:41,020
Якщо ми подивимося на forest.c, у нас є mkforest, який, як ми очікуємо.

351
00:28:41,020 --> 00:28:42,890
Ми Танос речі.

352
00:28:42,890 --> 00:28:51,740
Ми ініціалізували перша ділянка в лісі, NULL, тому що це порожні Почнемо з того,

353
00:28:51,740 --> 00:29:05,940
Потім ми бачимо, вибір, який повертає дерево з низькою вагою, низької частоти,

354
00:29:05,940 --> 00:29:13,560
, А потім позбавляється від конкретного вузла, який вказує на це дерево і наступний,

355
00:29:13,560 --> 00:29:16,760
тому він приймає, що із зв'язаного списку лісу.

356
00:29:16,760 --> 00:29:24,510
А то ось у нас є завод, який вставляє дерево у зв'язаному списку.

357
00:29:24,510 --> 00:29:29,960
Що лісів робить це красиво тримає його відсортовані для нас.

358
00:29:29,960 --> 00:29:37,910
І, нарешті, у нас є rmforest і, як і очікувалося, у нас є rmtree називається там.

359
00:29:46,650 --> 00:29:55,440
>> Дивлячись на поширення коду досі, huffile.c була, ймовірно, набагато важче зрозуміти,

360
00:29:55,440 --> 00:29:59,990
в той час як інші файли самі по собі були досить прості, щоб слідувати.

361
00:29:59,990 --> 00:30:03,090
З нашими знаннями покажчики та зв'язані списки і такі,

362
00:30:03,090 --> 00:30:04,860
ми були в змозі слідувати досить добре.

363
00:30:04,860 --> 00:30:10,500
Але все, що потрібно, щоб дійсно переконатися, що ми повністю розуміємо це. Ч. файлів

364
00:30:10,500 --> 00:30:15,840
тому що ви повинні бути викликом цих функцій, вирішення цих значень, що повертаються,

365
00:30:15,840 --> 00:30:20,590
тому переконайтеся, що ви повністю розумієте, яка дія буде виконуватися

366
00:30:20,590 --> 00:30:24,290
всякий раз, коли ви подзвоните по одному з цих функцій.

367
00:30:24,290 --> 00:30:33,020
Але насправді порозуміння всередині нього зовсім не обов'язково, тому що ми є ті. Ч. файлів.

368
00:30:35,170 --> 00:30:39,490
У нас є ще 2 файли, які залишаються в нашій розподілу коду.

369
00:30:39,490 --> 00:30:41,640
>> Давайте подивимося на звалище.

370
00:30:41,640 --> 00:30:47,230
Дамп його коментар тут займає Хаффман стислих файлів

371
00:30:47,230 --> 00:30:55,580
, А потім перекладає і звалища весь його вміст з.

372
00:31:01,010 --> 00:31:04,260
Тут ми бачимо, що вона кличе hfopen.

373
00:31:04,260 --> 00:31:10,770
Це свого роду дзеркальне у файл * вхід = Еореп,

374
00:31:10,770 --> 00:31:13,500
а потім ви проходите в інформації.

375
00:31:13,500 --> 00:31:18,240
Це майже ідентичні, за винятком замість файлу * ви передаєте в Huffile;

376
00:31:18,240 --> 00:31:22,030
замість Еореп ви передаєте в hfopen.

377
00:31:22,030 --> 00:31:29,280
Тут ми читаємо в заголовку першою, яка є своєрідною подібно до того, як ми читаємо в заголовку

378
00:31:29,280 --> 00:31:33,580
для растрових файлів.

379
00:31:33,580 --> 00:31:38,000
Що ми робимо тут, перевіряючи, чи є інформація заголовка

380
00:31:38,000 --> 00:31:44,330
містить право магічне число, яке вказує, що це реальний файл Хафф,

381
00:31:44,330 --> 00:31:53,610
Потім всі ці перевірки, щоб переконатися, що файл, який ми відкриті є актуальною пирхнув файл чи ні.

382
00:31:53,610 --> 00:32:05,330
Що це робить він виводить частоти всі символи, які ми бачимо,

383
00:32:05,330 --> 00:32:09,790
в терміналі в графічну таблицю.

384
00:32:09,790 --> 00:32:15,240
Ця частина буде корисно.

385
00:32:15,240 --> 00:32:24,680
Він має трохи, і читається по частинах в змінну трохи, а потім роздруковує її.

386
00:32:28,220 --> 00:32:35,430
Так що, якщо б я був подзвонити звалища на hth.bin, яка є результатом пихкаючи файл

387
00:32:35,430 --> 00:32:39,490
використання співробітниками рішення, я хотів би отримати це.

388
00:32:39,490 --> 00:32:46,000
Це виводить всі ці персонажі, а потім покласти частоти, на яких вони з'являються.

389
00:32:46,000 --> 00:32:51,180
Якщо ми подивимося, більшість з них 0s за винятком цього: H, яка з'являється двічі,

390
00:32:51,180 --> 00:32:54,820
, А потім T, який з'являється один раз.

391
00:32:54,820 --> 00:33:07,860
А то тут ми маємо фактичне повідомлення в 0 і 1.

392
00:33:07,860 --> 00:33:15,450
Якщо ми подивимося на hth.txt, який імовірно вихідне повідомлення, яке було пирхнув,

393
00:33:15,450 --> 00:33:22,490
ми очікуємо побачити деякі Hs і Ц. там.

394
00:33:22,490 --> 00:33:28,720
Зокрема, ми очікуємо побачити тільки 1 і 2 T Hs.

395
00:33:32,510 --> 00:33:37,440
Тут ми знаходимося в hth.txt. Це дійсно має HTH.

396
00:33:37,440 --> 00:33:41,270
Входить в там, хоча ми не бачимо, є символом нового рядка.

397
00:33:41,270 --> 00:33:53,190
Hth.bin Хафф файл також кодування символу нового рядка, а також.

398
00:33:55,680 --> 00:34:01,330
Тут, тому що ми знаємо, що порядок HTH, а потім рядки,

399
00:34:01,330 --> 00:34:07,340
ми бачимо, що, ймовірно, H представлена ​​тільки однією +1

400
00:34:07,340 --> 00:34:17,120
, А потім, ймовірно, T 01 і потім на наступний Н 1, а

401
00:34:17,120 --> 00:34:21,139
а то у нас новий рядок позначається двома 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> І, нарешті, тому, що ми маємо справу з декількома. С і. Ч. файлів,

404
00:34:31,600 --> 00:34:36,350
ми будемо мати досить складний аргумент для компілятора,

405
00:34:36,350 --> 00:34:40,460
і ось у нас є Makefile, який робить дамп для вас.

406
00:34:40,460 --> 00:34:47,070
Але насправді, ви повинні піти про створення власного puff.c файл.

407
00:34:47,070 --> 00:34:54,330
Makefile насправді не має справу зі створенням puff.c для вас.

408
00:34:54,330 --> 00:34:59,310
Ми йдемо, що до Вас, щоб змінити Makefile.

409
00:34:59,310 --> 00:35:05,930
Коли ви вводите команду зробити все, наприклад, він зробить все це за вас.

410
00:35:05,930 --> 00:35:10,760
Ви можете подивитися на приклади Makefile з минулого PSET

411
00:35:10,760 --> 00:35:17,400
а також йти з цього, щоб побачити, як ви могли б зробити вашу Puff файл

412
00:35:17,400 --> 00:35:20,260
шляхом редагування цього файлу Makefile.

413
00:35:20,260 --> 00:35:22,730
Ось про це наш розподілу коду.

414
00:35:22,730 --> 00:35:28,380
>> Як тільки ми пройшли через це, то тут просто ще одне нагадування

415
00:35:28,380 --> 00:35:30,980
про те, як ми збираємося мати справу з вузлами Хаффмана.

416
00:35:30,980 --> 00:35:35,400
Ми не збираємося бути називаючи їх вузлів більше, ми збираємося називати їх деревами

417
00:35:35,400 --> 00:35:39,260
де ми збираємося подавати їх символ символ,

418
00:35:39,260 --> 00:35:43,340
їх частота, число входжень, з цілим.

419
00:35:43,340 --> 00:35:47,370
Ми використовуємо, тому що це більш точне, ніж плавати.

420
00:35:47,370 --> 00:35:52,980
А то у нас ще один покажчик ліворуч дитини, а також права дитини.

421
00:35:52,980 --> 00:35:59,630
Ліс, як ми бачили, це просто зв'язаний список дерев.

422
00:35:59,630 --> 00:36:04,670
У кінцевому рахунку, коли ми будуємо нашу Хафф файл,

423
00:36:04,670 --> 00:36:07,580
Ми хочемо, щоб наш ліс, щоб утримувати тільки 1 дерево -

424
00:36:07,580 --> 00:36:12,420
1 дерево, 1 корінь з кількома дітьми.

425
00:36:12,420 --> 00:36:20,840
Раніше, коли ми були просто робить нашу Huffman дерев,

426
00:36:20,840 --> 00:36:25,360
Ми почали з розміщення всіх вузлів на нашому екрані

427
00:36:25,360 --> 00:36:27,790
і говорять, що ми збираємося, щоб ці вузли,

428
00:36:27,790 --> 00:36:32,920
в остаточному підсумку вони збираються бути листя, і це їх символ, це їх частота.

429
00:36:32,920 --> 00:36:42,070
У нашому лісі, якби ми просто 3 букви, це ліс з 3 дерев.

430
00:36:42,070 --> 00:36:45,150
І те, як ми продовжимо, коли ми додали першого батька,

431
00:36:45,150 --> 00:36:48,080
Ми зробили ліс з 2 дерев.

432
00:36:48,080 --> 00:36:54,930
Ми зняли 2 з цих дітей у віці від нашого лісу, а потім замінити його батьківський вузол

433
00:36:54,930 --> 00:36:58,820
, Що було ці 2 вузла, як діти.

434
00:36:58,820 --> 00:37:05,600
І, нарешті, наш останній крок зробити наш приклад з As, Bs, Cs і

435
00:37:05,600 --> 00:37:08,030
було б зробити остаточний батьків,

436
00:37:08,030 --> 00:37:13,190
і так, то що б наше загальна кількість дерев у лісі 1.

437
00:37:13,190 --> 00:37:18,140
Чи всі подивитися, як ви починаєте з кількох дерев у лісі

438
00:37:18,140 --> 00:37:22,520
і в кінцевому підсумку з 1? Добре. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Що ми повинні зробити для Puff?

440
00:37:28,110 --> 00:37:37,110
Що нам потрібно зробити, це переконатися, що, як завжди, вони дають нам право тип вхідного

441
00:37:37,110 --> 00:37:39,090
так що ми дійсно можемо запустити програму.

442
00:37:39,090 --> 00:37:43,130
У цьому випадку вони будуть давати нам після їх першого аргументу командного рядка

443
00:37:43,130 --> 00:37:53,440
Ще 2: файл, який ми хочемо розпакувати і виходу розпакувати файл.

444
00:37:53,440 --> 00:38:00,410
Але як тільки ми переконайтеся, що вони проходять повз нас в потрібній кількості цінностей,

445
00:38:00,410 --> 00:38:05,820
Ми хочемо переконатися, що вхід файл Хафф чи ні.

446
00:38:05,820 --> 00:38:10,420
І ось одного разу ми гарантуємо, що це файл Хафф, то ми хочемо побудувати наше дерево,

447
00:38:10,420 --> 00:38:20,940
побудувати дерево так, що воно відповідає дерево, людина, що відправив повідомлення побудований.

448
00:38:20,940 --> 00:38:25,840
Потім, після ми будуємо дерево, то ми можемо мати справу з 0 і 1, що вони пройшли в,

449
00:38:25,840 --> 00:38:29,590
слідувати за тими, на нашу дереву, тому що це ідентично,

450
00:38:29,590 --> 00:38:33,510
а потім пишуть, що повідомлення з, інтерпретувати біти назад в символи.

451
00:38:33,510 --> 00:38:35,880
І потім, в кінці, тому що ми маємо справу з покажчиками тут,

452
00:38:35,880 --> 00:38:38,110
Ми хочемо переконатися, що ми не маємо будь витоку пам'яті

453
00:38:38,110 --> 00:38:41,330
і що ми все безкоштовно.

454
00:38:42,820 --> 00:38:46,430
>> Забезпечення належного використання є стара капелюх для нас зараз.

455
00:38:46,430 --> 00:38:51,980
Візьмемо як входу, яка буде ім'я файлу, пихкати,

456
00:38:51,980 --> 00:38:56,010
а потім ми вказуємо вихід,

457
00:38:56,010 --> 00:39:01,580
тому ім'я файлу для пухкі вихід, який буде текстовий файл.

458
00:39:03,680 --> 00:39:08,820
Це використання. І тепер ми хочемо переконатися, що вхід розбушувався, чи ні.

459
00:39:08,820 --> 00:39:16,420
Згадуючи, чи було що-небудь у розподілі код, який може допомогти нам

460
00:39:16,420 --> 00:39:21,570
з розумінням, чи є файл розбушувався, чи ні?

461
00:39:21,570 --> 00:39:26,910
Існував інформації в huffile.c про Huffeader.

462
00:39:26,910 --> 00:39:33,430
Ми знаємо, що кожен файл має Хафф Huffeader пов'язані з ним з магічним числом

463
00:39:33,430 --> 00:39:37,240
а також масив частот для кожного символу

464
00:39:37,240 --> 00:39:39,570
а також контрольну суму.

465
00:39:39,570 --> 00:39:43,180
Ми знаємо, що, але ми також прийняли поглянути на dump.c,

466
00:39:43,180 --> 00:39:49,120
, В якому вона читала в файл Хафф.

467
00:39:49,120 --> 00:39:53,990
І так, щоб зробити це, він повинен був перевірити чи дійсно вона була розбушувався, чи ні.

468
00:39:53,990 --> 00:40:03,380
Тому, можливо, ми могли б використовувати dump.c як структура для нашого puff.c.

469
00:40:03,380 --> 00:40:12,680
Повернутися до PSET 4, коли у нас був файл copy.c, що скопіювали в трійках RGB

470
00:40:12,680 --> 00:40:14,860
і ми інтерпретували, що для детективний роман і зміна розміру,

471
00:40:14,860 --> 00:40:20,390
Точно так само, то, що ви можете зробити, це просто запустити команду Ф dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
і використовувати деякі з код.

473
00:40:23,600 --> 00:40:28,210
Тим не менш, це не буде так просто, процесу

474
00:40:28,210 --> 00:40:33,010
для перекладу вашого dump.c в puff.c,

475
00:40:33,010 --> 00:40:36,160
але принаймні це дає вам де-небудь, щоб почати

476
00:40:36,160 --> 00:40:40,540
про те, як переконатися, що вхід насправді розбушувався, чи ні

477
00:40:40,540 --> 00:40:43,240
, А також кілька інших речей.

478
00:40:45,930 --> 00:40:50,250
Ми забезпечили належного використання і запевнив, що вхід пирхнув.

479
00:40:50,250 --> 00:40:53,570
Кожен раз, коли ми це зробили, ми зробили належні перевірки на помилки,

480
00:40:53,570 --> 00:41:01,520
так поверненні та вихід з функції, якщо деякі з ладу, якщо є проблема.

481
00:41:01,520 --> 00:41:07,170
>> Тепер те, що ми хочемо зробити, це побудувати реальне дерево.

482
00:41:08,840 --> 00:41:12,640
Якщо ми подивимося в лісі, є 2 основні функції

483
00:41:12,640 --> 00:41:15,800
що ми збираємося хочете стати дуже знайомі.

484
00:41:15,800 --> 00:41:23,870
Там в булевої функції рослин, що рослини не-0 частота дерево в нашому лісі.

485
00:41:23,870 --> 00:41:29,250
І таким чином, ви передаєте покажчик на ліс і покажчик на дерево.

486
00:41:32,530 --> 00:41:40,340
Швидкий запитання: скільки лісу буде у вас, коли ви будуєте дерево Хаффмана?

487
00:41:44,210 --> 00:41:46,650
Наш ліс, як наше полотно, вірно?

488
00:41:46,650 --> 00:41:50,800
Таким чином, ми тільки збираємося мати 1 ліс, але ми збираємося мати кілька дерев.

489
00:41:50,800 --> 00:41:57,590
Тому, перш ніж називати рослини, ви ймовірно збирався хочете, щоб ваш ліс.

490
00:41:57,590 --> 00:42:04,430
Існує команда, що якщо ви подивитеся на forest.h про те, як ви можете зробити ліс.

491
00:42:04,430 --> 00:42:09,270
Ви можете посадити дерево. Ми знаємо, як це робити.

492
00:42:09,270 --> 00:42:11,590
І тоді ви можете також вибрати дерево з лісу,

493
00:42:11,590 --> 00:42:17,540
видалення дерев з низькою вагою і дає вам покажчик на це.

494
00:42:17,540 --> 00:42:23,090
Згадуючи, коли ми робили приклади себе,

495
00:42:23,090 --> 00:42:27,980
Коли ми малювали його, ми просто тільки що додали посилання.

496
00:42:27,980 --> 00:42:31,680
Але тут замість того, щоб просто додати посилання,

497
00:42:31,680 --> 00:42:40,630
думаю про нього як ви видаляєте 2 з цих вузлів, а потім замінити його на інший.

498
00:42:40,630 --> 00:42:44,200
Щоб висловити, що в плані збору та посадки,

499
00:42:44,200 --> 00:42:48,840
Ви вибираєте 2 дерева, а потім посадка інше дерево

500
00:42:48,840 --> 00:42:54,060
, Який має ті 2 дерева, які ви вибрали, як діти.

501
00:42:57,950 --> 00:43:05,280
Для побудови дерева Хаффмана, ви можете прочитати в символах і частоти в порядку

502
00:43:05,280 --> 00:43:10,790
тому що Huffeader дає, що для вас,

503
00:43:10,790 --> 00:43:14,250
дає вам масив частот.

504
00:43:14,250 --> 00:43:19,660
Таким чином, ви можете піти далі і просто ігнорувати все, що з 0 в цьому

505
00:43:19,660 --> 00:43:23,760
тому що ми не хочемо 256 листів в кінці його.

506
00:43:23,760 --> 00:43:27,960
Ми тільки хочемо, щоб кількість листя, які є символами

507
00:43:27,960 --> 00:43:31,600
, Які фактично використовуються у файлі.

508
00:43:31,600 --> 00:43:37,590
Ви можете прочитати в тих символах, і кожен з цих символів, які мають не-0 частот,

509
00:43:37,590 --> 00:43:40,440
ті збираєтеся бути дерев.

510
00:43:40,440 --> 00:43:45,990
Що ви можете зробити, це кожен раз, коли ви читаєте в не-0 частота символ,

511
00:43:45,990 --> 00:43:50,660
Ви можете посадити це дерево в лісі.

512
00:43:50,660 --> 00:43:56,620
Після того як ви посадіть дерева в лісі, ви можете приєднатися до тих дерев, як брати і сестри,

513
00:43:56,620 --> 00:44:01,130
Тож повертаючись до посадки і вибрати, де ви вибираєте 2, а потім завод 1,

514
00:44:01,130 --> 00:44:05,820
де то 1, що ви заводу є батьком 2 дітей, що ви вибрали.

515
00:44:05,820 --> 00:44:11,160
Таким чином, то ваш результат буде одне дерево в лісі.

516
00:44:16,180 --> 00:44:18,170
Ось як ви будуєте свою дерева.

517
00:44:18,170 --> 00:44:21,850
>> Є кілька речей, які можуть піти не так, тут

518
00:44:21,850 --> 00:44:26,580
тому що ми маємо справу зі створенням нових дерев і справу з покажчиками тощо.

519
00:44:26,580 --> 00:44:30,450
Раніше, коли ми маємо справу з покажчиками,

520
00:44:30,450 --> 00:44:36,580
всякий раз, коли ми malloc'd ми хотіли переконатися, що він не повернув нам NULL значення покажчика.

521
00:44:36,580 --> 00:44:42,770
Таким чином, на кілька кроків в рамках цього процесу там буде кілька випадків

522
00:44:42,770 --> 00:44:45,920
де ваша програма може не спрацювати.

523
00:44:45,920 --> 00:44:51,310
Те, що ви хочете зробити, ви хочете, щоб переконатися, що ви обробляти ці помилки,

524
00:44:51,310 --> 00:44:54,580
і в специфікації він говорить з ними впоратися витончено,

525
00:44:54,580 --> 00:45:00,280
так як роздрукувати повідомлення користувачу говорити їм, чому програма повинна вийти

526
00:45:00,280 --> 00:45:03,050
і потім швидко вийти з нього.

527
00:45:03,050 --> 00:45:09,490
Для цього обробка помилок, пам'ятайте, що ви хочете, щоб перевірити його

528
00:45:09,490 --> 00:45:12,160
кожен раз, що не може бути відмови.

529
00:45:12,160 --> 00:45:14,660
Кожен раз, коли ви робите новий покажчик

530
00:45:14,660 --> 00:45:17,040
Ви хочете, щоб переконатися, що це успіх.

531
00:45:17,040 --> 00:45:20,320
Перш, ніж те, що ми робили, роблять новий покажчик і Танос це,

532
00:45:20,320 --> 00:45:22,380
і тоді ми б перевірити, що покажчик NULL.

533
00:45:22,380 --> 00:45:25,670
Так що збираєтеся бути в деяких випадках, коли ви просто можете зробити це,

534
00:45:25,670 --> 00:45:28,610
але іноді ви насправді виклику функції

535
00:45:28,610 --> 00:45:33,100
і в рамках цієї функції, це той, який робить mallocing.

536
00:45:33,100 --> 00:45:39,110
У тому випадку, якщо ми оглянемося на деяких функцій в коді,

537
00:45:39,110 --> 00:45:42,260
Деякі з них є логічними функціями.

538
00:45:42,260 --> 00:45:48,480
В абстрактному випадку, якщо у нас є булева функція називається Foo,

539
00:45:48,480 --> 00:45:54,580
В принципі, ми можемо припустити, що на додаток до Foo робити те, що робить,

540
00:45:54,580 --> 00:45:57,210
так як це булева функція, вона повертає істинне або помилкове -

541
00:45:57,210 --> 00:46:01,300
вірно, якщо успішно, якщо не помилковим.

542
00:46:01,300 --> 00:46:06,270
Тому ми хочемо, щоб перевірити повернене значення Foo є істинним або хибним.

543
00:46:06,270 --> 00:46:10,400
Якщо це неправда, це означає, що ми збираємося хочете надрукувати якусь повідомлення

544
00:46:10,400 --> 00:46:14,390
, А потім вийти з програми.

545
00:46:14,390 --> 00:46:18,530
Те, що ми хочемо зробити, це перевірити повернене значення Foo.

546
00:46:18,530 --> 00:46:23,310
Якщо Foo повертає брехня, то ми знаємо, що ми зіткнулися з якоюсь помилкою

547
00:46:23,310 --> 00:46:25,110
і ми повинні вийти з нашої програми.

548
00:46:25,110 --> 00:46:35,600
Спосіб зробити це, це є стан, при якому фактична функція саме ваш стан.

549
00:46:35,600 --> 00:46:39,320
Скажімо Foo приймає в х.

550
00:46:39,320 --> 00:46:43,390
Ми можемо мати в якості умови, якщо (Foo (х)).

551
00:46:43,390 --> 00:46:50,900
В принципі, це означає, що якщо в кінці виконання Foo він повертає істину,

552
00:46:50,900 --> 00:46:57,390
Потім ми можемо зробити це, тому що функція має оцінити Foo

553
00:46:57,390 --> 00:47:00,500
для того, щоб оцінити загальний стан.

554
00:47:00,500 --> 00:47:06,500
Таким чином, то це, як ви можете зробити щось, якщо функція повертає істину і успішно.

555
00:47:06,500 --> 00:47:11,800
Але коли ти помилок, ви тільки хочете кинути курити, якщо ваша функція повертає брехня.

556
00:47:11,800 --> 00:47:16,090
Що ви можете зробити, це просто додати == помилкових або просто додати вибуху перед ним

557
00:47:16,090 --> 00:47:21,010
, А потім, якщо у вас є (! Foo).

558
00:47:21,010 --> 00:47:29,540
В рамках цього тіла, що умова вам доведеться все обробки помилок,

559
00:47:29,540 --> 00:47:36,940
так як, "Не вдалося створити це дерево", а потім повертає 1 або щось на зразок цього.

560
00:47:36,940 --> 00:47:43,340
Те, що це робить, проте, в тому, що навіть якщо Foo повернулися помилкової -

561
00:47:43,340 --> 00:47:46,980
Скажімо Foo повертає істину.

562
00:47:46,980 --> 00:47:51,060
Тоді вам не доведеться викликати Foo знову. Це поширена помилка.

563
00:47:51,060 --> 00:47:54,730
Тому що це було у вашому стані, це вже оцінка,

564
00:47:54,730 --> 00:47:59,430
так у вас вже є результат, якщо ви використовуєте зробити дерево або щось на зразок того

565
00:47:59,430 --> 00:48:01,840
рослин або забрати або щось.

566
00:48:01,840 --> 00:48:07,460
Він уже має це значення. Це вже виконана.

567
00:48:07,460 --> 00:48:10,730
Так що це корисно використовувати булеві функції як умова

568
00:48:10,730 --> 00:48:13,890
тому що ви чи ні насправді виконати тіло циклу,

569
00:48:13,890 --> 00:48:18,030
він виконує функцію в будь-якому випадку.

570
00:48:22,070 --> 00:48:27,330
>> Наша друга до останнього кроку пише повідомлення у файл.

571
00:48:27,330 --> 00:48:33,070
Як тільки ми побудуємо дерево Хаффмана, то написання повідомлень в файл досить просто.

572
00:48:33,070 --> 00:48:39,260
Це досить просто тепер просто дотримуйтесь 0 і 1.

573
00:48:39,260 --> 00:48:45,480
І так за традицією ми знаємо, що в дереві Хаффмана 0s вказують залишив

574
00:48:45,480 --> 00:48:48,360
і 1s вказує вправо.

575
00:48:48,360 --> 00:48:53,540
Отже, якщо ви читали в біт за бітом, кожен раз, коли ви отримаєте 0

576
00:48:53,540 --> 00:48:59,100
Ви будете дотримуватися лівої гілки, а потім кожен раз, коли ви читаєте в 1

577
00:48:59,100 --> 00:49:02,100
Ви збираєтеся слідувати правої гілки.

578
00:49:02,100 --> 00:49:07,570
І тоді ви будете продовжувати, поки ви натиснете лист

579
00:49:07,570 --> 00:49:11,550
тому що листя буде в кінці гілки.

580
00:49:11,550 --> 00:49:16,870
Як ми можемо сказати, чи будемо ми потрапили листя чи ні?

581
00:49:19,800 --> 00:49:21,690
Ми говорили це раніше.

582
00:49:21,690 --> 00:49:24,040
[Студент] Якщо покажчиків NULL. >> Да.

583
00:49:24,040 --> 00:49:32,220
Ми можемо сказати, якщо ми потрапили листя, якщо покажчики на лівого і правого дерева NULL.

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

585
00:49:34,110 --> 00:49:40,320
Ми знаємо, що ми хочемо читати по крупицях в нашому файлі Хафф.

586
00:49:43,870 --> 00:49:51,220
Як ми бачили раніше в dump.c, що вони зробили, вони читали в біт за бітом в файл Huff

587
00:49:51,220 --> 00:49:54,560
і просто роздрукувати те, що ці біти були.

588
00:49:54,560 --> 00:49:58,430
Ми не збираємося робити цього. Ми будемо робити те, що це трохи більш складним.

589
00:49:58,430 --> 00:50:03,620
Але що ми можемо зробити, ми можемо вважати, що шматок коду, який читає в біт.

590
00:50:03,620 --> 00:50:10,250
Тут ми маємо ціле біт, що представляє поточний біт, якою ми йдемо.

591
00:50:10,250 --> 00:50:15,520
Це піклується про перебір всіх бітів в файл, поки ви не потрапили в кінець файлу.

592
00:50:15,520 --> 00:50:21,270
Грунтуючись на цьому, то ви будете хотіти мати якийсь ітератор

593
00:50:21,270 --> 00:50:26,760
пройти дерева.

594
00:50:26,760 --> 00:50:31,460
А потім залежно від того біт дорівнює 0 або 1,

595
00:50:31,460 --> 00:50:36,920
Ви збираєтеся хочете чи рухатися, що ітератор на лівому або перемістити його в правий

596
00:50:36,920 --> 00:50:44,080
всю дорогу, поки ви натиснете аркуша, так всю дорогу, поки цей вузол, що ви на

597
00:50:44,080 --> 00:50:48,260
не вказує на будь-якому більш вузлів.

598
00:50:48,260 --> 00:50:54,300
Чому ми можемо зробити це за допомогою файлу Хаффман, але не азбуки Морзе?

599
00:50:54,300 --> 00:50:56,610
Тому що в азбуці Морзе є трохи двозначності.

600
00:50:56,610 --> 00:51:04,440
Ми могли би бути схожим, ой, почекайте, ми потрапили листи по шляху, так що, можливо, це наш лист,

601
00:51:04,440 --> 00:51:08,150
в той час як, якщо б ми продовжували тільки трохи довше, то ми б потрапили ще один лист.

602
00:51:08,150 --> 00:51:13,110
Але це не відбудеться в кодуванні Хаффмана,

603
00:51:13,110 --> 00:51:17,540
так що ми можемо бути впевнені, що єдиний спосіб, яким ми збираємося вдарити характер

604
00:51:17,540 --> 00:51:23,480
, Якщо ліва і права дітей цього вузла є NULL.

605
00:51:28,280 --> 00:51:32,350
>> Нарешті, ми хочемо, щоб звільнити всі наші пам'яті.

606
00:51:32,350 --> 00:51:37,420
Ми хочемо, щоб як закрити файл Хафф, що ми маємо справу з

607
00:51:37,420 --> 00:51:41,940
а також видалити всі дерева в нашому лісі.

608
00:51:41,940 --> 00:51:46,470
Грунтуючись на ваших реалізації, ви, ймовірно, захочете подзвонити видалити лісі

609
00:51:46,470 --> 00:51:49,780
а насправді переживає всі дерева самостійно.

610
00:51:49,780 --> 00:51:53,430
Але якщо ви зробили будь тимчасові дерева, ви хочете, щоб звільнити це.

611
00:51:53,430 --> 00:51:59,060
Ви знаєте, ваш код краще, так що ви знаєте, де ви виділенні пам'яті.

612
00:51:59,060 --> 00:52:04,330
І так, якщо ви йдете в, почнемо з управління F'ing навіть для Танос,

613
00:52:04,330 --> 00:52:08,330
бачите, коли ви Танос і переконавшись, що ви звільняєте всі, що

614
00:52:08,330 --> 00:52:10,190
але потім просто переживає свій код,

615
00:52:10,190 --> 00:52:14,260
розуміння, де ви могли б виділеної пам'яті.

616
00:52:14,260 --> 00:52:21,340
Зазвичай ви могли б просто сказати: "В кінці файлу Я просто хочу, щоб видалити лісі на мій ліс»,

617
00:52:21,340 --> 00:52:23,850
так в основному ясно, що пам'ять, безкоштовно, що,

618
00:52:23,850 --> 00:52:28,310
», А потім я також збираюся, щоб закрити файл, а потім моя програма буде кинути курити».

619
00:52:28,310 --> 00:52:33,810
Але в тому, що єдиний раз, коли ваша програма завершує свою роботу?

620
00:52:33,810 --> 00:52:37,880
Ні, тому що іноді, можливо, було помилкою, що сталося.

621
00:52:37,880 --> 00:52:42,080
Може бути, ми не могли відкрити файл або ми не могли зробити інше дерево

622
00:52:42,080 --> 00:52:49,340
або якась помилка сталася в процесі розподілу пам'яті і тому він повертається NULL.

623
00:52:49,340 --> 00:52:56,710
Сталася помилка, і потім ми повернулися і кинути палити.

624
00:52:56,710 --> 00:53:02,040
Отже ви хочете, щоб переконатися, що будь-яке можливе час, що ваша програма може кинути палити,

625
00:53:02,040 --> 00:53:06,980
Ви хочете, щоб звільнити всі ваші пам'яті там.

626
00:53:06,980 --> 00:53:13,370
Це не просто буде в самому кінці головної функції, яку ви кинути свій код.

627
00:53:13,370 --> 00:53:20,780
Ви хочете, щоб озирнутися назад, щоб кожен екземпляр, що ваш код потенційно може повернутися передчасно

628
00:53:20,780 --> 00:53:25,070
, А потім звільнити пам'ять все, що має сенс.

629
00:53:25,070 --> 00:53:30,830
Скажімо, ви закликали зробити лісів і повернувся помилковим.

630
00:53:30,830 --> 00:53:34,230
Тоді ви, напевно, не потрібно буде видалити лісі

631
00:53:34,230 --> 00:53:37,080
тому що ви не маєте лісі ще немає.

632
00:53:37,080 --> 00:53:42,130
Але в кожній точці в коді, де ви могли б повернутися передчасно

633
00:53:42,130 --> 00:53:46,160
Ви хочете, щоб переконатися, що ви звільнити будь-які можливі пам'яті.

634
00:53:46,160 --> 00:53:50,020
>> Тому, коли ми маємо справу з звільнення пам'яті і має потенційні витоку,

635
00:53:50,020 --> 00:53:55,440
Ми хочемо, щоб не тільки використовувати наші судження і наші логіки

636
00:53:55,440 --> 00:54:01,850
але також використовувати Valgrind визначити, чи є ми звільнили всіх наших пам'яттю на належному рівні чи ні.

637
00:54:01,850 --> 00:54:09,460
Ви можете запустити Valgrind на Puff, а потім ви повинні також пройти його

638
00:54:09,460 --> 00:54:14,020
правильну кількість аргументів командного рядка для Valgrind.

639
00:54:14,020 --> 00:54:18,100
Ви можете запустити, але на виході виходить трохи загадкове.

640
00:54:18,100 --> 00:54:21,630
Ми отримали трохи звикнути до нього з Speller, але нам все ще потрібно трохи більше допомоги,

641
00:54:21,630 --> 00:54:26,450
так, то запустити його ще з кількома прапорами, як витік перевірити = повний,

642
00:54:26,450 --> 00:54:32,040
, Що, ймовірно, дасть нам більш корисним виходом на Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Потім ще корисну пораду при налагодженні це команда порівняння.

644
00:54:39,040 --> 00:54:48,520
Ви можете отримати доступ до здійснення співробітників про Хафф, запустити, що в текстовому файлі,

645
00:54:48,520 --> 00:54:55,400
, А потім виводити їх у бінарний файл, двійковий файл Хафф, щоб бути певним.

646
00:54:55,400 --> 00:54:59,440
Тоді, якщо ви використовуєте свій власний листковому на що двійковий файл,

647
00:54:59,440 --> 00:55:03,950
Потім ідеалі, виведеного текстового файлу буде ідентичним

648
00:55:03,950 --> 00:55:08,200
вихідного, що ви пройшли дюйма

649
00:55:08,200 --> 00:55:15,150
Тут я використовую hth.txt в якості прикладу, і це одна говорили у вашій специфікації.

650
00:55:15,150 --> 00:55:21,040
Ось буквально тільки що HTH, а потім рядки.

651
00:55:21,040 --> 00:55:30,970
Але, безумовно, відчувати себе вільно і ви, безумовно, рекомендується використовувати більше прикладів

652
00:55:30,970 --> 00:55:32,620
для вашого текстового файлу.

653
00:55:32,620 --> 00:55:38,110
>> Ви навіть можете взяти постріл в можливо стиснення і декомпресію, то

654
00:55:38,110 --> 00:55:41,600
деякі з файлів, які ви використовували в Speller, як війна і мир

655
00:55:41,600 --> 00:55:46,710
або Джейн Остін або щось подібне до цього - це було б круто - або Остіна Пауерса,

656
00:55:46,710 --> 00:55:51,880
вид роботи з великими файлами, тому що ми б не дійшли до цього

657
00:55:51,880 --> 00:55:55,590
якби ми використовували наступний інструмент тут, LS-л.

658
00:55:55,590 --> 00:56:01,150
Ми звикли до Ls, які в основному перераховані всі вміст в нашому поточному каталозі.

659
00:56:01,150 --> 00:56:07,860
Переходячи в флаг-L насправді відображає розмір цих файлів.

660
00:56:07,860 --> 00:56:12,690
Якщо ви йдете через специфікацію PSET, насправді проведе вас через створення бінарних файлів,

661
00:56:12,690 --> 00:56:16,590
з пихкаючи, і ви побачите, що для дуже маленьких файлів

662
00:56:16,590 --> 00:56:23,910
простору вартості стискаючи його і перекладав усе, що інформація

663
00:56:23,910 --> 00:56:26,980
всіх частот і тому подібні речі перевищує фактичну вигоду

664
00:56:26,980 --> 00:56:30,000
стиснути файл в першу чергу.

665
00:56:30,000 --> 00:56:37,450
Але якщо ви запустите його на кілька довгих текстових файлів, то ви можете бачити, що ви почнете одержувати деяку вигоду

666
00:56:37,450 --> 00:56:40,930
В стиснення цих файлів.

667
00:56:40,930 --> 00:56:46,210
>> І, нарешті, у нас є наш старий приятель GDB, який, безумовно, буде згодяться теж.

668
00:56:48,360 --> 00:56:55,320
>> Чи є у нас якісь питання по деревах Хафф або процес, можливо, прийняття дерев

669
00:56:55,320 --> 00:56:58,590
або будь-які інші питання по Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Добре. Я залишуся навколо деякий час.

671
00:57:02,570 --> 00:57:06,570
>> Спасибі всім. Це було Покрокове керівництво 6. І удачі.

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