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]