Главная-Чем открыть файл-Кодировка хаффмана. Код Хаффмана

Кодировка хаффмана. Код Хаффмана

Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д.Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований. (Последнее утверждение из § 3.8.1 показывает, что наилучший код переменной длины можно иногда получить без этого алгоритма.)

Алгоритм начинается составлением списка символов алфавита в порядке убывания их вероятностей. Затем от корня строится дерево, листьями которого служат эти символы. Это делается по шагам, причем на каждом шаге выбираются два символа с наименьшими вероятностями, добавляются наверх частичного дерева, удаляются из списка и заменяются вспомогательным символом, представляющим эти два символа. Вспомогательному символу приписывается вероятность, равная сумме вероятностей, выбранных на этом шаге символов. Когда список сокращается до одного вспомогательного символа, представляющего весь алфавит, дерево объявляется построенным. Завершается алгоритм спуском по дереву и построением кодов всех символов.

Лучше всего проиллюстрировать этот алгоритм на простом примере. Имеется пять символов с вероятностями, заданными на рис. 1.3а.

Рис. 1.3. Коды Хаффмана.

Символы объединяются в пары в следующем порядке:

1. объединяется с , и оба заменяются комбинированным символом с вероятностью 0.2;

2. Осталось четыре символа, с вероятностью 0.4, а также и с вероятностями по 0.2. Произвольно выбираем и , объединяем их и заменяем вспомогательным символом с вероятностью 0.4;

3. Теперь имеется три символа и с вероятностями 0.4, 0.2 и 0.4, соответственно. Выбираем и объединяем символы и во вспомогательный символ с вероятностью 0.6;

4. Наконец, объединяем два оставшихся символа и и заменяем на с вероятностью 1.

Дерево построено. Оно изображено на рис. 1.3а, «лежа на боку», с корнем справа и пятью листьями слева. Для назначения кодов мы произвольно приписываем бит 1 верхней ветке и бит 0 нижней ветке дерева для каждой пары. В результате получаем следующие коды: 0, 10, 111, 1101 и 1100. Распределение битов по краям - произвольное.

Средняя длина этого кода равна бит/символ. Очень важно то, что кодов Хаффмана бывает много. Некоторые шаги алгоритма выбирались произвольным образом, поскольку было больше символов с минимальной вероятностью. На рис. 1.3b показано, как можно объединить символы по-другому и получить иной код Хаффмана (11, 01, 00, 101 и 100). Средняя длина равна бит/символ как и у предыдущего кода.

Пример: Дано 8 символов А, В, С, D, Е, F, G и H с вероятностями 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 и 12/30. На рис. 1.4а,b,с изображены три дерева кодов Хаффмана высоты 5 и 6 для этого алфавита.

Рис. 1.4. Три дерева Хаффмана для восьми символов.

Средняя длина этих кодов (в битах на символ) равна

Пример : На рис. 1.4d показано другое дерево высоты 4 для восьми символов из предыдущего примера. Следующий анализ показывает, что соответствующий ему код переменной длины плохой, хотя его длина меньше 4.

(Анализ.) После объединения символов А, В, С, D, Е, F и G остаются символы ABEF (с вероятностью 10/30), CDG (с вероятностью 8/30) и H (с вероятностью 12/30). Символы ABEF и CDG имеют наименьшую вероятность, поэтому их необходимо было слить в один, но вместо этого были объединены символы CDG и H. Полученное дерево не является деревом Хаффмана.

Таким образом, некоторый произвол в построении дерева позволяет получать разные коды Хаффмана с одинаковой средней длиной. Напрашивается вопрос: «Какой код Хаффмана, построенный для данного алфавита, является наилучшим?» Ответ будет простым, хотя и неочевидным: лучшим будет код с наименьшей дисперсией.

Дисперсия показывает насколько сильно отклоняются длины индивидуальных кодов от их средней величины (это понятие разъясняется в любом учебнике по статистике). Дисперсия кода 1.3а равна , а для кода 1.3b .

Код 1.3b является более предпочтительным (это будет объяснено ниже). Внимательный взгляд на деревья показывает, как выбрать одно, нужное нам. На дереве рис. 1.3а символ сливается с символом , в то время как на рис. 1.3b он сливается с . Правило будет такое: когда на дереве имеется более двух узлов с наименьшей вероятностью, следует объединять символы с наибольшей и наименьшей вероятностью; это сокращает общую дисперсию кода.

Если кодер просто записывает сжатый файл на диск, то дисперсия кода не имеет значения. Коды Хаффмана с малой дисперсией более предпочтительны только в случае, если кодер будет передавать этот сжатый файл по линиям связи. В этом случае, код с большой дисперсией заставляет кодер генерировать биты с переменной скоростью. Обычно данные передаются по каналам связи с постоянной скоростью, поэтому кодер будет использовать буфер. Биты сжатого файла помещаются в буфер по мере их генерации и подаются в канал с постоянной скоростью для передачи. Легко видеть, что код с нулевой дисперсией будет подаваться в буфер с постоянной скоростью, поэтому понадобится короткий буфер, а большая дисперсия кода потребует использование длинного буфера.

Следующее утверждение можно иногда найти в литературе по сжатию информации: длина кода Хаффмана символа с вероятностью всегда не превосходит . На самом деле, не смотря на справедливость этого утверждения во многих примерах, в общем случае оно не верно. Я весьма признателен Гаю Блелоку, который указал мне на это обстоятельство и сообщил пример кода, приведенного в табл. 1.5. Во второй строке этой таблицы стоит символ с кодом длины 3 бита, в то время как .

Табл. 1.5. Пример кода Хаффмана.

Длина кода символа , конечно, зависит от его вероятности . Однако она также неявно зависит от размера алфавита. В большом алфавите вероятности символов малы, поэтому коды Хаффмана имеют большую длину. В маленьком алфавите наблюдается обратная картина. Интуитивно это понятно, поскольку для малого алфавита требуется всего несколько кодов, поэтому все они коротки, а большому алфавиту необходимо много кодов и некоторые из них должны быть длинными.

Рис. 1.6. Код Хаффмана для английского алфавита.

На рис. 1.6 показан код Хаффмана для всех 26 букв английского алфавита.

Случай алфавита, в котором символы равновероятны, особенно интересен. На рис. 1.7 приведены коды Хаффмана для алфавита с 5, 6, 7 и 8 равновероятными символами. Если размер алфавита является степенью 2, то получаются просто коды фиксированной длины. В других случаях коды весьма близки к кодам с фиксированной длиной. Это означает, что использование кодов переменной длины не дает никаких преимуществ. В табл. 1.8 приведены коды, их средние длины и дисперсии.

Рис. 1.7. Коды Хаффмана с равными вероятностями.

Тот факт, что данные с равновероятными символами не сжимаются методом Хаффмана может означать, что строки таких символов являются совершенно случайными. Однако, есть примеры строк, в которых все символы равновероятны, но не являются случайными, и их можно сжимать. Хорошим примером является последовательность , в которой каждый символ встречается длинными сериями. Такую строку можно сжать методом RLE, но не методом Хаффмана. (Буквосочетание RLE означает «run-length encoding», т.е. «кодирование длин серий». Этот простой метод сам по себе мало эффективен, но его можно использовать в алгоритмах сжатия со многими этапами, см.

Другими словами, будем вдвигать слева в переменную code бит за битом из входного потока, до тех пор, пока code < base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.

Предположим, что цикл в (2), после нескольких итераций, остановился. В этом случае выражение (code - base) суть порядковый номер искомого узла (символа) на уровне length. Первый узел (символ), находящийся на уровне length в дереве, расположен в массиве symb по индексу offs. Но нас интересует не первый символ, а символ под номером (code - base). Поэтому индекс искомого символа в массиве symb равен (offs + (code - base)). Иначе говоря, искомый символ symbol=symb + code - base].

Приведем конкретный пример. Пользуясь изложенным алгоритмом декодируем сообщение Z / .

Z / ="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1"

  1. code = 0, length = 1
  2. code = 0 < base = 1
    code = 0 << 1 = 0
    code = 0 + 0 = 0
    length = 1 + 1 = 2
    code = 0 < base = 2
    code = 0 << 1 = 0
    code = 0 + 0 = 0
    length = 2 + 1 = 3
    code = 0 < base = 2
    code = 0 << 1 = 0
    code = 0 + 1 = 1
    length = 3 + 1 = 4
    code = 1 = base = 1
  3. symbol = symb = 2 + code = 1 - base = 1] = symb = A
  1. code = 1, length = 1
  2. code = 1 = base = 1
  3. symbol = symb = 7 + code = 1 - base = 1] = symb = H
  1. code = 0, length = 1
  2. code = 0 < base = 1
    code = 0 << 1 = 0
    code = 0 + 0 = 0
    length = 1 + 1 = 2
    code = 0 < base = 2
    code = 0 << 1 = 0
    code = 0 + 0 = 0
    length = 2 + 1 = 3
    code = 0 < base = 2
    code = 0 << 1 = 0
    code = 0 + 0 = 0
    length = 3 + 1 = 4
    code = 0 < base = 1
    code = 0 << 1 = 0
    code = 0 + 1 = 1
    length = 4 + 1 = 5
    code = 1 > base = 0
  3. symbol = symb = 0 + code = 1 - base = 0] = symb = F

Итак, мы декодировали 3 первых символа: A , H , F . Ясно, что следуя этому алгоритму мы получим в точности сообщение S.

Вычисление длин кодов

Для того чтобы закодировать сообщение нам необходимо знать коды символов и их длины. Как уже было отмечено в предыдущем разделе, канонические коды вполне определяются своими длинами. Таким образом, наша главная задача заключается в вычислении длин кодов.

Оказывается, что эта задача, в подавляющем большинстве случаев, не требует построения дерева Хаффмана в явном виде. Более того, алгоритмы использующие внутреннее (не явное) представление дерева Хаффмана оказываются гораздо эффективнее в отношении скорости работы и затрат памяти.

На сегодняшний день существует множество эффективных алгоритмов вычисления длин кодов ( , ). Мы ограничимся рассмотрением лишь одного из них. Этот алгоритм достаточно прост, но несмотря на это очень популярен. Он используется в таких программах как zip, gzip, pkzip, bzip2 и многих других.

Вернемся к алгоритму построения дерева Хаффмана. На каждой итерации мы производили линейный поиск двух узлов с наименьшим весом. Ясно, что для этой цели больше подходит очередь приоритетов, такая как пирамида (минимальная). Узел с наименьшим весом при этом будет иметь наивысший приоритет и находиться на вершине пирамиды. Приведем этот алгоритм.

    Включим все кодируемые символы в пирамиду.

    Последовательно извлечем из пирамиды 2 узла (это будут два узла с наименьшим весом).

    Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла взятых из пирамиды. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

    Включим сформированный узел в пирамиду.

    Если в пирамиде больше одного узла, то повторить 2-5.

Будем считать, что для каждого узла сохранен указатель на его родителя. У корня дерева этот указатель положим равным NULL. Выберем теперь листовой узел (символ) и следуя сохраненным указателям будем подниматься вверх по дереву до тех пор, пока очередной указатель не станет равен NULL. Последнее условие означает, что мы добрались до корня дерева. Ясно, что число переходов с уровня на уровень равно глубине листового узла (символа), а следовательно и длине его кода. Обойдя таким образом все узлы (символы), мы получим длины их кодов.

Максимальная длина кода

Как правило, при кодировании используется так называемая кодовая книга (CodeBook) , простая структура данных, по сути два массива: один с длинами, другой с кодами. Другими словами, код (как битовая строка) хранится в ячейке памяти или регистре фиксированного размера (чаще 16, 32 или 64). Для того чтобы не произошло переполнение, мы должны быть уверены в том, что код поместится в регистр.

Оказывается, что на N-символьном алфавите максимальный размер кода может достигать (N-1) бит в длину. Иначе говоря, при N=256 (распространенный вариант) мы можем получить код в 255 бит длиной (правда для этого файл должен быть очень велик: 2.292654130570773*10^53~=2^177.259)! Ясно, что такой код в регистр не поместится и с ним нужно что-то делать.

Для начала выясним при каких условиях возникает переполнение. Пусть частота i-го символа равна i-му числу Фибоначчи. Например: A -1, B -1, C -2, D -3, E -5, F -8, G -13, H -21. Построим соответствующее дерево Хаффмана.

ROOT /\ / \ / \ /\ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B

Такое дерево называется вырожденным . Для того чтобы его получить частоты символов должны расти как минимум как числа Фибоначчи или еще быстрее. Хотя на практике, на реальных данных, такое дерево получить практически невозможно, его очень легко сгенерировать искусственно. В любом случае эту опасность нужно учитывать.

Эту проблему можно решить двумя приемлемыми способами. Первый из них опирается на одно из свойств канонических кодов. Дело в том, что в каноническом коде (битовой строке) не более младших бит могут быть ненулями. Другими словами, все остальные биты можно вообще не сохранять, т.к. они всегда равны нулю. В случае N=256 нам достаточно от каждого кода сохранять лишь младшие 8 битов, подразумевая все остальные биты равными нулю. Это решает проблему, но лишь отчасти. Это значительно усложнит и замедлит как кодирование, так и декодирование. Поэтому этот способ редко применяется на практике.

Второй способ заключается в искусственном ограничении длин кодов (либо во время построения, либо после). Этот способ является общепринятым, поэтому мы остановимся на нем более подробно.

Существует два типа алгоритмов ограничивающих длины кодов. Эвристические (приблизительные) и оптимальные. Алгоритмы второго типа достаточно сложны в реализации и как правило требуют больших затрат времени и памяти, чем первые. Эффективность эвристически-ограниченного кода определяется его отклонением от оптимально-ограниченного. Чем меньше эта разница, тем лучше. Стоит отметить, что для некоторых эвристических алгоритмов эта разница очень мала ( , , ), к тому же они очень часто генерируют оптимальный код (хотя и не гарантируют, что так будет всегда). Более того, т.к. на практике переполнение случается крайне редко (если только не поставлено очень жесткое ограничение на максимальную длину кода), при небольшом размере алфавита целесообразнее применять простые и быстрые эвристические методы.

Мы рассмотрим один достаточно простой и очень популярный эвристический алгоритм. Он нашел свое применение в таких программах как zip, gzip, pkzip, bzip2 и многих других.

Задача ограничения максимальной длины кода эквивалентна задаче ограничения высоты дерева Хаффмана. Заметим, что по построению любой нелистовой узел дерева Хаффмана имеет ровно два потомка. На каждой итерации нашего алгоритма будем уменьшать высоту дерева на 1. Итак, пусть L - максимальная длина кода (высота дерева) и требуется ограничить ее до L / < L. Пусть далее RN i самый правый листовой узел на уровне i, а LN i - самый левый.

Начнем работу с уровня L. Переместим узел RN L на место своего родителя. Т.к. узлы идут парами нам необходимо найти место и для соседного с RN L узла. Для этого найдем ближайший к L уровень j, содержащий листовые узлы, такой, что j < (L-1). На месте LN j сформируем нелистовой узел и присоединим к нему в качестве дочерних узел LN j и оставшийся без пары узел с уровня L. Ко всем оставшимся парам узлов на уровне L применим такую же операцию. Ясно, что перераспределив таким образом узлы, мы уменьшили высоту нашего дерева на 1. Теперь она равна (L-1). Если теперь L / < (L-1), то проделаем то же самое с уровнем (L-1) и т.д. до тех пор, пока требуемое ограничение не будет достигнуто.

Вернемся к нашему примеру, где L=5. Ограничим максимальную длину кода до L / =4.

ROOT /\ / \ / \ /\ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F

Видно, что в нашем случае RN L =F , j=3, LN j =C . Сначала переместим узел RN L =F на место своего родителя.

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B (непарный узел)

Теперь на месте LN j =C сформируем нелистовой узел.

ROOT /\ / \ / \ /\ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B (непарный узел) C (непарный узел)

Присоединим к сформированному узлу два непарных: B и C .

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C

Таким образом, мы ограничили максимальную длину кода до 4. Ясно, что изменив длины кодов, мы немного потеряли в эффективности. Так сообщение S, закодированное при помощи такого кода, будет иметь размер 92 бита, т.е. на 3 бита больше по сравнению с минимально-избыточным кодом.

Ясно, что чем сильнее мы ограничим максимальную длину кода, тем менее эффективен будет код. Выясним насколько можно ограничивать максимальную длину кода. Очевидно что не короче бит.

Вычисление канонических кодов

Как мы уже неоднократно отмечали, длин кодов достаточно для того чтобы сгенерировать сами коды. Покажем как это можно сделать. Предположим, что мы уже вычислили длины кодов и подсчитали сколько кодов каждой длины у нас есть. Пусть L - максимальная длина кода, а T i - количество кодов длины i.

Вычислим S i - начальное значение кода длины i, для всех i из

S L = 0 (всегда)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (всегда)

Для нашего примера L = 5, T 1 .. 5 = {1, 0, 2 ,3, 2}.

S 5 = 00000 bin = 0 dec
S 4 = (S 5 =0 + T 5 =2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dec
S 3 = (S 4 =1 + T 4 =3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dec
S 2 = (S 3 =2 + T 3 =2) >> 1 = (100 bin >> 1) = 10 bin = 2 dec
S 1 = (S 2 =2 + T 2 =0) >> 1 = (10 bin >> 1) = 1 bin = 1 dec

Видно, что S 5 , S 4 , S 3 , S 1 - в точности коды символов B , A , C , H . Эти символы объединяет то, что все они стоят на первом месте, каждый на своем уровне. Другими словами, мы нашли начальное значение кода для каждой длины (или уровня).

Теперь присвоим коды остальным символам. Код первого символа на уровне i равен S i , второго S i + 1, третьего S i + 2 и т.д.

Выпишем оставшиеся коды для нашего примера:

B = S 5 = 00000 bin A = S 4 = 0001 bin C = S 3 = 010 bin H = S 1 = 1 bin
F = S 5 + 1 = 00001 bin D = S 4 + 1 = 0010 bin E = S 3 + 1 = 011 bin
G = S 4 + 2 = 0011 bin

Видно, что мы получили точно такие же коды, как если бы мы явно построили каноническое дерево Хаффмана.

Передача кодового дерева

Для того чтобы закодированное сообщение удалось декодировать, декодеру необходимо иметь такое же кодовое дерево (в той или иной форме), какое использовалось при кодировании. Поэтому вместе с закодированными данными мы вынуждены сохранять соответствующее кодовое дерево. Ясно, что чем компактнее оно будет, тем лучше.

Решить эту задачу можно несколькими способами. Самое очевидное решение - сохранить дерево в явном виде (т.е. как упорядоченное множество узлов и указателей того или иного вида). Это пожалуй самый расточительный и неэффективный способ. На практике он не используется.

Можно сохранить список частот символов (т.е. частотный словарь). С его помощью декодер без труда сможет реконструировать кодовое дерево. Хотя этот способ и менее расточителен чем предыдущий, он не является наилучшим.

Наконец, можно использовать одно из свойств канонических кодов. Как уже было отмечено ранее, канонические коды вполне определяются своими длинами. Другими словами, все что необходимо декодеру - это список длин кодов символов. Учитывая, что в среднем длину одного кода для N-символьного алфавита можно закодировать [(log 2 (log 2 N))] битами, получим очень эффективный алгоритм. На нем мы остановимся подробнее.

Предположим, что размер алфавита N=256, и мы сжимаем обыкновенный текстовый файл (ASCII). Скорее всего мы не встретим все N символов нашего алфавита в таком файле. Положим тогда длину кода отсутвующих символов равной нулю. В этом случае сохраняемый список длин кодов будет содержать достаточно большое число нулей (длин кодов отсутствующих символов) сгруппированных вместе. Каждую такую группу можно сжать при помощи так называемого группового кодирования - RLE (Run - Length - Encoding). Этот алгоритм чрезвычайно прост. Вместо последовательности из M одинаковых элементов идущих подряд, будем сохранять первый элемент этой последовательности и число его повторений, т.е. (M-1). Пример: RLE("AAAABBBCDDDDDDD")=A3 B2 C0 D6.

Более того, этот метод можно несколько расширить. Мы можем применить алгоритм RLE не только к группам нулевых длин, но и ко всем остальным. Такой способ передачи кодового дерева является общепринятым и применяется в большинстве современных реализаций.

Реализация: SHCODEC

Приложение: биография Д. Хаффмана

Дэвид Хаффман родился в 1925 году в штате Огайо (Ohio), США. Хаффман получил степень бакалавра электротехники в государственном университете Огайо (Ohio State University) в возрасте 18 лет. Затем он служил в армии офицером поддержки радара на эсминце, который помогал обезвреживать мины в японских и китайских водах после Второй Мировой Войны. В последствии он получил степень магистра в университете Огайо и степень доктора в Массачусетском Институте Технологий (Massachusetts Institute of Technology - MIT). Хотя Хаффман больше известен за разработку метода построения минимально-избыточных кодов, он так же сделал важный вклад во множество других областей (по большей части в электронике). Он долгое время возглавлял кафедру Компьютерных Наук в MIT. В 1974, будучи уже заслуженным профессором, он подал в отставку. Хаффман получил ряд ценных наград. В 1999 - Медаль Ричарда Хамминга (Richard W. Hamming Medal) от Института Инженеров Электричества и Электроники (Institute of Electrical and Electronics Engineers - IEEE) за исключительный вклад в Теорию Информации, Медаль Louis E. Levy от Франклинского Института (Franklin Institute) за его докторскую диссертацию о последовательно переключающихся схемах, Награду W. Wallace McDowell, Награду от Компьютерного Сообщества IEEE, Золотую юбилейную награду за технологические новшества от IEEE в 1998. В октябре 1999 года, в возрасте 74 лет Дэвид Хаффман скончался от рака.

R.L. Milidiu, A.A. Pessoa, E.S. Laber, "Efficient implementation of the warm-up algorithm for the construction of length-restricted prefix codes", Proc. of ALENEX (International Workshop on Algorithm Engineering and Experimentation), pp. 1-17, Springer, Jan. 1999.

На данный момент мало кто задумывается над тем, как же работает сжатие файлов. По сравнению с прошлым пользование персональным компьютером стало намного проще. И практически каждый человек, работающий с файловой системой, пользуется архивами. Но мало кто задумывается над тем, как они работают и по какому принципу происходит сжатие файлов. Самым первым вариантом этого процесса стали коды Хаффмана, и их используют по сей день в различных популярных архиваторах. Многие пользователи даже не задумываются, насколько просто происходит сжатие файла и по какой схеме это работает. В данной статье мы рассмотрим, как происходит сжатие, какие нюансы помогают ускорить и упростить процесс кодирования, а также разберемся, в чем принцип построения дерева кодирования.

История алгоритма

Самым первым алгоритмом проведения эффективного кодирования электронной информации стал код, предложенный Хаффманом еще в середине двадцатого века, а именно в 1952 году. Именно он на данный момент является основным базовым элементом большинства программ, созданных для сжатия информации. На данный момент одними из самых популярных источников, использующих этот код, являются архивы ZIP, ARJ, RAR и многие другие.

Также данный алгоритм Хаффмана применяется для и других графических объектов. Ну и все современные факсы также используют кодирование, изобретенное в 1952 году. Несмотря на то что со времени создания кода прошло так много времени, по сей день его используют в самых новых оболочках и на оборудовании старого и современного типов.

Принцип эффективного кодирования

В основу алгоритма по Хаффману входит схема, позволяющая заменить самые вероятные, чаще всего встречающиеся символы системы. А те, которые встречаются реже, заменяются более длинными кодами. Переход на длинные коды Хаффмана происходит только после того, как система использует все минимальные значения. Такая методика позволяет минимизировать длину кода на каждый символ исходного сообщения в целом.

Важным моментом является то, что в начале кодирования вероятности появления букв должны быть уже известны. Именно из них и будет составляться конечное сообщение. Исходя из этих данных, осуществляется построение кодового дерева Хаффмана, на основе которого и будет проводиться процесс кодирования букв в архиве.

Код Хаффмана, пример

Чтобы проиллюстрировать алгоритм, возьмем графический вариант построения кодового дерева. Чтобы использование этого способа было эффективным, стоит уточнить определение некоторых значений, необходимых для понятия данного способа. Совокупность множества дуг и узлов, которые направлены от узла к узлу, принято называть графом. Само дерево является графом с набором определенных свойств:

  • в каждый узел может входить не больше одной из дуг;
  • один из узлов должен быть корнем дерева, то есть в него не должны входить дуги вообще;
  • если от корня начать перемещение по дугам, этот процесс должен позволять попасть совершенно в любой из узлов.

Существует также такое понятие, входящее в коды Хаффмана, как лист дерева. Он представляет собой узел, из которого не должно выходить ни одной дуги. Если два узла соединены дугой, то один из них является родителем, другой ребенком, в зависимости от того, из какого узла дуга выходит, и в какой входит. Если два узла имеют один и тот же родительский узел, их принято называть братскими узлами. Если же, кроме листьев, у узлов выходит по несколько дуг, то это дерево называется двоичным. Как раз таким и является дерево Хаффмана. Особенностью узлов данного построения является то, что вес каждого родителя равен сумме веса всех его узловых детей.

Алгоритм построения дерева по Хаффману

Построение кода Хаффмана делается из букв входного алфавита. Образуется список тех узлов, которые свободны в будущем кодовом дереве. Вес каждого узла в этом списке должен быть таким же, как и вероятность возникновения буквы сообщения, соответствующей этому узлу. При этом среди нескольких свободных узлов будущего дерева выбирается тот, который весит меньше всего. При этом если минимальные показатели наблюдаются в нескольких узлах, то можно свободно выбирать любую из пар.

После чего происходит создание родительского узла, который должен весить столько же, сколько весит сумма этой пары узлов. После этого родителя отправляют в список со свободными узлами, а дети удаляются. При этом дуги получают соответствующие показатели, единицы и нули. Этот процесс повторяется ровно столько, сколько нужно, чтобы оставить только один узел. После чего выписываются по направлению сверху вниз.

Повышение эффективности сжатия

Чтобы повысить эффективность сжатия, нужно во время построения дерева кода использовать все данные относительно вероятности появления букв в конкретном файле, прикрепленном к дереву, и не допускать того, чтобы они были раскиданы по большому количеству текстовых документов. Если предварительно пройтись по этому файлу, можно сразу просчитать статистику того, насколько часто встречаются буквы из объекта, подлежащего сжиманию.

Ускорение процесса сжатия

Чтобы ускорить работу букв нужно проводить не по показателям вероятности появления той или иной буквы, а по частоте ее встречаемости. Благодаря этому алгоритм становится проще, и работа с ним значительно ускоряется. Также это позволяет избежать операций, связанных с плавающими запятыми и делением.

Кроме того, работая в таком режиме, динамический код Хаффмана, а точнее сам алгоритм, не подлежит никаким изменениям. В основном это связанно с тем, что вероятности имеют прямую пропорциональность частотам. Стоит обратить особое внимание на то, что конечный вес файла или так называемого корневого узла будет равен сумме количества букв в объекте, подлежащем обработке.

Заключение

Коды Хаффмана - простой и давно созданный алгоритм, который до сих пор используется многими известными программами и компаниями. Его простота и понятность позволяют добиться эффективных результатов сжатия файлов любых объемов и значительно уменьшить занимаемое ими место на диске хранения. Иными словами, алгоритм Хаффмана - давно изученная и проработанная схема, актуальность которой не уменьшается по сей день.

А благодаря возможности уменьшить размер файлов, их передача через сеть или другими способами становится более простой, быстрой и удобной. Работая с алгоритмом, можно сжать совершенно любую информацию без вреда для ее структуры и качества, но с максимальным эффектом уменьшения веса файла. Иными словами, кодирование по коду Хаффмана было и остается самым популярным и актуальным методом сжатия размера файла.

Кодирование Хаффмана. Часть 1.
Вступление
Здравствуй, дорогой читатель! В данной статье будет рассмотрен один из способов сжатия данных. Этот способ является достаточно широко распространённым и заслуживает определённого внимания. Данный материал рассчитан по объёму на три статьи, первая из которых будет посвящена алгоритму сжатия, вторая - программной реализации алгоритма, а третья ― декомпрессии. Алгоритм сжатия будет написан на языке C++, алгоритм декомпрессии ― на языке Assembler.
Однако, перед тем, как приступить к самому алгоритму, следует включить в статью немного теории.
Немного теории
Компрессия (сжатие ) ― способ уменьшения объёма данных с целью дальнейшей их передачи и хранения.
Декомпрессия ― это способ восстановления сжатых данных в исходные.
Компрессия и декомпрессия могут быть как без потери качества (когда передаваемая/хранимая информация в сжатом виде после декомпрессии абсолютно идентична исходной), так и с потерей качества (когда данные после декомпрессии отличаются от оригинальных). Например, текстовые документы, базы данных, программы могут быть сжаты только способом без потери качества, в то время как картинки, видеоролики и аудиофайлы сжимаются именно за счёт потери качества исходных данных (характерный пример алгоритмов ― JPEG, MPEG, ADPCM), при порой незаметной потере качества даже при сжатии 1:4 или 1:10.
Выделяются основные виды упаковки:
  • Десятичная упаковка предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и так далее. При подобном подходе уже ощущается сжатие минимум 1:2.
  • Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
  • Символьное подавление - способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
  • Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). При таком подходе коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому ― с наибольшей.
Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хаффмана, последний из которых мы и будем рассматривать.
Конкретнее об алгоритме
Как уже известно из предыдущего подраздела, алгоритм Хафмана основан на статистическом кодировании. Разберёмся поподробнее в его реализации.
Пусть имеется источник данных, который передаёт символы (a_1, a_2, ..., a_n) с разной степенью вероятности, то есть каждому a_i соответствует своя вероятность (или частота) P_i(a_i) , при чём существует хотя бы одна пара a_i и a_j ,i\ne j , такие, что P_i(a_i) и P_j(a_j) не равны. Таким образом образуется набор частот {P_1(a_1), P_2(a_2),...,P_n(a_n)} , при чём \displaystyle \sum_{i=1}^{n} P_i(a_i)=1 , так как передатчик не передаёт больше никаких символов кроме как {a_1,a_2,...,a_n} .
Наша задача ― подобрать такие кодовые символы {b_1, b_2,...,b_n} с длинами {L_1(b_1),L_2(b_2),...,L_n(b_n)} , чтобы средняя длина кодового символа не превышала средней длины исходного символа. При этом нужно учитывать условие, что если P_i(a_i)>P_j(a_j) и i\ne j , то L_i(b_i)\le L_j(b_j) .
Хафман предложил строить дерево, в котором узлы с наибольшей вероятностью наименее удалены от корня. Отсюда и вытекает сам способ построения дерева:
1. Выбрать два символа a_i и a_j , i\ne j , такие, что P_i(a_i) и P_j(a_j) из всего списка {P_1(a_1),P_2,...,P_n(a_n)} являются минимальными.
2. Свести ветки дерева от этих двух элементов в одну точку с вероятностью P=P_i(a_i)+P_j(a_j) , пометив одну ветку нулём, а другую ― единицей (по собственному усмотрению).
3. Повторить пункт 1 с учётом новой точки вместо a_i и a_j , если количество получившихся точек больше единицы. В противном случае мы достигли корня дерева.
Теперь попробуем воспользоваться полученной теорией и закодировать информацию, передаваемую источником, на примере семи символов.
Разберём подробно первый цикл. На рисунке изображена таблица, в которой каждому символу a_i соответствует своя вероятность (частота) P_i(a_i) . Согласно пункту 1 мы выбираем два символа из таблицы с наименьшей вероятностью. В нашем случае это a_1 и a_4 . Согласно пункту 2 сводим ветки дерева от a_1 и a_4 в одну точку и помечаем ветку, ведущую к a_1 , единицей, а ветку, ведущую к a_4 ,― нулём. Над новой точкой приписываем её вероятность (в данном случае ― 0.03) В дальнейшем действия повторяются уже с учётом новой точки и без учёта a_1 и a_4 .

После многократного повторения изложенных действий выстраивается следующее дерево:

По построенному дереву можно определить значение кодов {b_1,b_2,...,b_n} , осуществляя спуск от корня к соответствующему элементу a_i , при этом приписывая к получаемой последовательности при прохождении каждой ветки ноль или единицу (в зависимости от того, как именуется конкретная ветка). Таким образом таблица кодов выглядит следующим образом:

i b i L i (b i) 1 011111 62 1 13 0110 44 011110 65 010 36 00 27 01110 5

Теперь попробуем закодировать последовательность из символов.
Пусть символу a_i соответствует (в качестве примера) число i . Пусть имеется последовательность 12672262. Нужно получить результирующий двоичный код.
Для кодирования можно использовать уже имеющуюся таблицу кодовых символов b_i при учёте, что b_i соответствует символу a_i . В таком случае код для цифры 1 будет представлять собой последовательность 011111, для цифры 2 ― 1, а для цифры 6 ― 00. Таким образом, получаем следующий результат:

Данные12672262Длина кодаИсходные001010110111010010110 01024 битКодированные011111100011101100119 бит

В результате кодирования мы выиграли 5 бит и записали последовательность 19 битами вместо 24.
Однако это не даёт полной оценки сжатия данных. Вернёмся к математике и оценим степень сжатия кода. Для этого понадобится энтропийная оценка.
Энтропия ― мера неопределённости ситуации (случайной величины) с конечным или с чётным числом исходов. Математически энтропия формулируется как сумма произведений вероятностей различных состояний системы на логарифмы этих вероятностей, взятых с обратным знаком:

H(X)=-\displaystyle \sum_{i=1}^{n}P_i\cdot log_d (P_i) .​

Где X ― дискретная случайная величина (в нашем случае ― кодовый символ), а d ― произвольное основание, большее единицы. Выбор основания равносилен выбору определённой единицы измерения энтропии. Так как мы имеем дело с двоичными цифрами, то в качестве основания рационально выбрать d=2 .
Таким образом, энтропию для нашего случая можно представить в виде:

H(b)=-\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot log_2 (P_i(a_i)) .​

Энтропия обладает замечательным свойством: она равна минимальной допустимой средней длине кодового символа \overline{L_{min}} в битах. Сама же средняя длина кодового символа вычисляется по формуле

\overline{L(b)}=\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot L_i(b_i) .​

Подставляя значения в формулы H(b) и \overline{L(b)} , получаем следующий результат: H(b)=2,048 , \overline{L(b)}=2,100 .
Величины H(b) и \overline{L(b)} очень близки, что говорит о реальном выигрыше в выборе алгоритма. Теперь сравним среднюю длину исходного символа и среднюю длину кодового символа через отношение:

\frac{\overline{L_{src}}}{L(b)}=\frac{3}{2,1}=1,429 .​

Таким образом, мы получили сжатие в соотношении 1:1,429, что очень неплохо.
И напоследок, решим последнюю задачу: дешифровка последовательности битов.
Пусть для нашей ситуации имеется последовательность битов:

001101100001110001000111111​

Необходимо определить исходный код, то есть декодировать эту последовательность.
Конечно, в такой ситуации можно воспользоваться таблицей кодов, но это достаточно неудобно, так как длина кодовых символов непостоянна. Гораздо удобнее осуществить спуск по дереву (начиная с корня) по следующему правилу:
1. Исходная точка ― корень дерева.
2. Прочитать новый бит. Если он ноль, то пройти по ветке, помеченной нулём, в противном случае ― единицей.
3. Если точка, в которую мы попали, конечная, то мы определили кодовый символ, который следует записать и вернуться к пункту 1. В противном случае следует повторить пункт 2.
Рассмотрим пример декодирования первого символа. Мы находимся в точке с вероятностью 1,00 (корень дерева), считываем первый бит последовательности и отправляемся по ветке, помеченной нулём, в точку с вероятностью 0,60. Так как эта точка не является конечной в дереве, то считываем следующий бит, который тоже равен нулю, и отправляемся по ветке, помеченной нулём, в точку a_6 , которая является конечной. Мы дешифровали символ ― это число 6. Записываем его и возвращаемся в исходное состояние (перемещаемся в корень).
Таким образом декодированная последовательность принимает вид.

Данные

001101100001110001000111111 Длина кодаКодированные00110110000111000100011111127 битИсходные6223676261233 бит

В данном случае выигрыш составил 6 бит при достаточно небольшой длине последовательности.
Вывод напрашивается сам собой: алгоритм прост. Однако следует сделать замечание: данный алгоритм хорош для сжатия текстовой информации (действительно, реально мы используем при набивке текста примерно 60 символов из доступных 256, то есть вероятность встретить иные символы близка к нулю), но достаточно плох для сжатия программ (так как в программе все символы практически равновероятны). Так что эффективность алгоритма очень сильно зависит от типа сжимаемых данных.
Постскриптум
В этой статье мы рассмотрели алгоритм кодирования по методу Хаффмана, который базируется на неравномерном кодировании. Он позволяет уменьшить размер передаваемых или хранимых данных. Алгоритм прост для понимания и может давать реальный выигрыш. Кроме этого, он обладает ещё одним замечательным свойством: возможность кодировать и декодировать информацию "на лету" при условии того, что вероятности кодовых слов правильно определены. Хотя существует модификация алгоритма, позволяющая изменять структуру дерева в реальном времени.
В следующей части статьи мы рассмотрим байт-ориентированное сжатие файлов с использованием алгоритма Хаффмана, реализованное на C++.
Кодирование Хаффмана. Часть 2
Вступление
В прошлой части мы рассмотрели алгоритм кодирования, описали его математическую модель, произвели кодирование и декодирование на конкретном примере, рассчитали среднюю длину кодового слова, а также определили коэффициент сжатия. Кроме этого, были сделаны выводы о преимуществах и недостатках данного алгоритма.
Однако, помимо этого неразрешёнными остались ещё два вопроса: реализация программы, сжимающей файл данных, и программы, распаковывающей сжатый файл. Первому вопросу и посвящена настоящая статья. Поэтому следует заняться проектированием.
Проектирование
Первым делом необходимо посчитать частоты вхождения символов в файл. Для этого опишем следующую структуру:

    // Структура для подсчёта частоты символа

    typedef struct TFreq

    int ch;

    TTable * table;

    DWORD freq;

    } TFreq;

Эта структура будет описывать каждый символ из 256. ch ― сам ASCII-символ, freq ― количество вхождений символа в файл. Поле table ― указатель на структуру:

    // Описатель узла

    typedef struct TTable

    int ch;

    TTable * left;

    TTable * right;

    } TTable;

Как видно, TTable ― это описатель узла с разветвлением по нулю и единице. При помощи этих структур в дальнейшем и будет осуществляться построение дерева компрессии. Теперь объявим для каждого символа свою частоту и свой узел:

    TFreq Freq[ 256 ] ;

Попробуем разобраться, каким образом будет осуществляться построение дерева. На начальной стадии программа должна осуществить проход по всему файлу и подсчитать количество вхождений символов в него. Помимо этого, для каждого найденного символа программа должна создать описатель узла. После этого из созданных узлов с учётом частоты символов программа строит дерево, размещая узлы в определённом порядке и устанавливая между ними связи.
Построенное дерево хорошо для декодирования файла. Но для кодирования файла оно неудобно, потому что неизвестно, в каком направлении следует идти от корня, чтобы добраться до необходимого символа. Для этого удобнее построить таблицу преобразования символов в код. Поэтому определим ещё одну структуру:

    // Описатель кодового символа

    typedef struct TOpcode

    DWORD opcode;

    DWORD len;

    } TOpcode;

Здесь opcode ― кодовая комбинация символа, а len - её длина (в битах). И объявим таблицу из 256 таких структур:

    TOpcode Opcodes[ 256 ] ;

Зная кодируемый символ, можно определить его кодовое слово по таблице. Теперь перейдём непосредственно к подсчёту частот символов (и не только).
Подсчёт частот символов
В принципе, это действие не составляет труда. Достаточно открыть файл и подсчитать в нём число символов, заполнив соответствующие структуры. Посмотрим реализацию этого действия.
Для этого объявим глобальные дескрипторы файлов:

    FILE * in, * out, * assemb;

in ― файл, из которого осуществляется чтение несжатых данных.
out ― файл, в который осуществляется запись сжатых данных.
assemb ― файл, в который будет сохранено дерево в удобном для распаковки виде. Так как распаковщик будет написан на ассемблере, то вполне рационально дерево сделать частью распаковщика, то есть представить его в виде инструкций на Ассемблере.
Первым делом необходимо проинициализировать все структуры нулевыми значениями:

    // Подсчёт частот символов

    int CountFrequency(void )

    int i; // переменная цикла

    int count= 0 ; // вторая переменная цикла

    DWORD TotalCount= 0 ; // размер файла.

    // Инициализация структур

    for (i= 0 ; i< 256 ; i++ )

    Freq[ i] .freq = 0 ;

    Freq[ i] .table = 0 ;

    Freq[ i] .ch = i;

После этого мы подсчитываем число вхождений символа в файл и размер файла (конечно, не самым идеальным способом, но в примере нужна наглядность):

    // Подсчёт частот символов (по-символьно)

    while (! feof (in) ) // пока не достигнут конец файла

    i= fgetc (in) ;

    if (i! = EOF ) // если не конец файла

    Freq[ i] .freq ++ ; // частота ++

    TotalCount++ ; // размер ++

Так как код неравномерный, то распаковщику будет проблематично узнать число считываемых символов. Поэтому в таблице распаковки необходимо зафиксировать его размер:

    // "Сообщаем" распаковщику размер файла

    fprintf (assemb, "coded_file_size:\n dd %8lxh\n \n " , TotalCount) ;

После этого все используемые символы смещаются в начало массива, а неиспользуемые затираются (путём перестановок).

    // смещаем все неиспользуемые символы в конец

    i= 0 ;

    count= 256 ;

    while (i< count) // пока не достигли конца

    if (Freq[ i] .freq == 0 ) // если частота 0

    Freq[ i] = Freq[ -- count] ; // то копируем запись из конца

    else

    i++ ; // всё ОК - двигаемся дальше.

И только после такой "сортировки" выделяется память под узлы (для некоторой экономии).

    // Выделяем память под узлы

    for (i= 0 ; i< count; i++ )

    Freq[ i] .table = new TTable; // создаём узел

    Freq[ i] .table - > left= 0 ; // без соединений

    Freq[ i] .table - > right= 0 ; // без соединений

    Freq[ i] .table - > ch= Freq.ch ; // копируем символ

    Freq[ i] .freq = Freq.freq ; // и частоту

    return count;

Таким образом, мы написали функцию первоначальной иницализации системы, или, если смотреть на алгоритм в первой части статьи, "записали используемые символы в столбик и приписали к ним вероятности", а также для каждого символа создали "отправную точку" ― узел ― и проинициализировали её. В поля left и right записали нули. Таким образом, если узел будет в дереве последним, то это будет легко увидеть по left и right , равным нулю.
Создание дерева
Итак, в предыдущем разделе мы "записали используемые символы в столбик и приписали к ним вероятности". На самом деле, мы приписали к ним не вероятности, а числители дроби (то есть количество вхождений символов в файл). Теперь надо построить дерево. Но для того, чтобы это сделать, необходимо найти минимальный элемент в списке. Для этого вводим функцию, в которую передаём два параметра ― количество элементов в списке и элемент, который следует исключить (потому что искать будем парами, и будет очень неприятно, если мы от функции дважды получим один и тот же элемент):

    // поиск узла с наименьшей вероятностью.

    int FindLeast(int count, int index)

    int i;

    DWORD min= (index== 0 ) ? 1 : 0 ; // элемент, который считаем

    // минимальным

    for (i= 1 ; i< count; i++ ) // цикл по массиву

    if (i! = index) // если элемент не исключён

    if (Freq[ i] .freq < Freq[ min] .freq ) // сравниваем

    min= i; // меньше минимума - запоминаем

    return min; // возвращаем индекс минимума

Поиск реализован несложно: сначала выбираем "минимальный" элемент массива. Если исключаемый элемент ― 0, то берём в качестве минимума первый элемент, в противном случае минимумом считаем нулевой. По мере прохождения по массиву сравниваем текущий элемент с "минимальным", и если он окажется меньше, то его помечаем как минимальный.
Теперь, собственно говоря, сама функция построения дерева:

    // Функция построения дерева

    void PreInit(int count)

    int ind1, ind2; // индексы элементов

    TTable * table; // указатель на "новый узел"

    while (count> 1 ) // цикл, пока не достигли корня

    ind1= FindLeast(count,- 1 ) ; // первый узел

    ind2= FindLeast(count,ind1) ; // второй узел

    table= new TTable; // создаём новый узел

    table- > ch= - 1 ; // не конечный

    table- > left= Freq[ ind1] .table ; // 0 - узел 1

    table- > right= Freq[ ind2] .table ; // 1 - узел 2

    Freq[ ind1] .ch = - 1 ; // модифицируем запись о

    Freq[ ind1] .freq + = Freq[ ind2] .freq ; // частоте для символа

    Freq[ ind1] .table = table; // и пишем новый узел

    if (ind2! = (-- count) ) // если ind2 не последний

    Freq[ ind2] = Freq[ count] ; // то на его место

    // помещаем последний в массиве

Таблица кодовых символов
Итак, дерево в памяти мы построили: попарно брали два узла, создавали новый узел, в который записывали на них указатели, после чего второй узел удаляли из списка, а вместо первого узла писали новый с разветвлением.
Теперь возникает ещё одна проблема: кодировать по дереву неудобно, потому что необходимо точно знать, по какому пути находится тот или иной символ. Однако проблема решается довольно просто: создаётся ещё одна таблица ― таблица кодовых символов ― в неё и записываются битовые комбинации всех используемых символов. Для этого достаточно однократно рекурсивно обойти дерево. Заодно, чтобы повторно его не обходить, можно в функцию обхода добавить генерацию ассемблерного файла для дальнейшего декодирования сжатых данных (см. раздел "Проектирование ").
Собственно, сама функция не сложна. Она должна приписывать к кодовой комбинации 0 или 1, если узел не конечный, в противном случае добавить кодовый символ в таблицу. Помимо всего этого, сгенерировать ассемблерный файл. Рассмотрим эту функцию:

    void RecurseMake(TTable * tbl, DWORD opcode, int len)

    fprintf (assemb,"opcode%08lx_%04x:\n " ,opcode,len) ; // метку в файл

    if (tbl- > ch! = - 1 ) // узел конечный

    BYTE mod= 32 - len;

    Opcodes[ tbl- > ch] .opcode = (opcode>> mod) ; // сохраняем код

    Opcodes[ tbl- > ch] .len = len; // и его длину (в битах)

    // и создаём соответствующую метку

    fprintf (assemb," db %03xh,0ffh,0ffh,0ffh\n \n " ,tbl- > ch) ;

    else // узел не конечный

    opcode>>= 1 ; // освобождаем место под новый бит

    len++ ; // увеличиваем длину кодового слова

    \n " ,opcode,len) ;

    fprintf (assemb," dw opcode%08lx_%04x\n \n " ,opcode| 0x80000000 ,len) ;

    RecurseMake(tbl- > left,opcode,len) ;

    RecurseMake(tbl- > right,opcode| 0x80000000 ,len) ;

    // удаляем узел (он уже не нужен)

    delete tbl;

Помимо всего прочего, после прохождения узла функция удаляет его (освобождает указатель). Теперь разберёмся, что за параметры передаются в функцию.

  • tbl ― узел, который надо обойти.
  • opcode ― текущее кодовое слово. Старший бит должен быть всегда свободен.
  • len ― длина кодового слова.
В принципе, функция не сложнее "классического факториала" и не должна вызывать трудностей.
Битовый вывод
Вот мы и добрались до не самой приятной части нашего архиватора, а именно ― до вывода кодовых символов в файл. Проблема состоит в том, что кодовые символы имеют неравномерную длину и вывод приходится осуществлять побитовый. В этом поможет функция PutCode . Но для начала объявим две переменные ― счётчик битов в байте и выводимый байт:

    // Счётчик битов

    int OutBits;

    // Выводимый символ

    BYTE OutChar;

OutBits увеличивается на один при каждом выводе бита, OutBits==8 сигнализирует о том, что OutChar следует сохранить в файл.

    void PutCode(int ch)

    int len;

    int outcode;

    // получаем длину кодового слова и само кодовое слово

    outcode= Opcodes[ ch] .opcode ; // кодовое слово

    len= Opcodes[ ch] .len ; // длина (в битах)

    while (len> 0 ) // выводим по-битно

    // Цикл пока переменная OutBits занята не полностью

    while ((OutBits< 8 ) && (len> 0 ) )

    OutChar>>= 1 ; // освобождаем место

    OutChar| = ((outcode& 1 ) << 7 ) ; // и в него помещаем бит

    outcode>>= 1 ; // следующий бит кода

    len-- ; // уменьшаем длину

  1. OutBits++ ; // количество битов выросло

  2. }

  3. // если используются все 8 бит, то сохраняем их в файл

  4. if (OutBits== 8 )

  5. {

  6. fputc (OutChar,out) ; // сохраняем в файл

  7. OutBits= 0 ; // обнуляем

  8. OutChar= 0 ; // параметры

  9. }

  10. }

  11. }

Помимо этого, нужно организовать что-то вроде "fflush", то есть после вывода последнего кодового слова OutChar не поместится в выходной файл, так как OutBits !=8. Отсюда появляется ещё одна небольшая функция:

  1. // "Очистка" буфера битов

  2. void EndPut(void )

  3. {

  4. // Если в буфере есть биты

  5. if (OutBits! = 0 )

Похожие публикации: