Пусть дано графическое изображение дерева хаффмана. Коды Хаффмана: примеры, применение

Кодирование Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

Этот процесс можно представить как построение дерева , корень которого - символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n 0 потомков - символы из предыдущего шага и т. д.

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

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д - наибольшим.

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что энтропия источника, независимым образом порождающего символы с указанными частотами составляет ~2,1858 бита на символ, т.е. избыточность построенного для такого источника кода Хаффмана, понимаемая, как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

Классический алгоритм Хаффмана имеет ряд существенных недостатков. Во-первых, для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Во-вторых, избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. В-третьих, для источника с энтропией, не превышающей 1 (например, для двоичного источника), непосредственное применение кода Хаффмана бессмысленно.

Адаптивное сжатие

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.

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

Обновление дерева при считывании очередного символа сообщения состоит из двух операций.

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

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

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

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

Переполнение

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмана неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмана превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмана превосходит размер типа «целое» в битах, наступает переполнение.

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

Масштабирование весов узлов дерева Хаффмана

Принимая во внимание сказанное выше, алгоритм обновления дерева Хаффмана должен быть изменен следующим образом: при увеличении веса нужно проверять его на достижение допустимого максимума. Если мы достигли максимума, то необходимо «масштабировать» вес, обычно разделив вес листьев на целое число, например, 2, а потом пересчитав вес всех остальных узлов.

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

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

Выигрыш от масштабирования

Масштабирование веса узлов дерева через определенные интервалы дает неожиданный результат. Несмотря на то, что при масштабировании происходит потеря точности статистики, тесты показывают, что оно приводит к лучшим показателям сжатия, чем если бы масштабирование откладывалось. Это можно объяснить тем, что текущие символы сжимаемого потока больше «похожи» на своих близких предшественников, чем на тех, которые встречались намного раньше. Масштабирование приводит к уменьшению влияния «давних» символов на статистику и к увеличению влияния на неё «недавних» символов. Это очень сложно измерить количественно, но, в принципе, масштабирование оказывает положительное влияние на степень сжатия информации. Эксперименты с масштабированием в различных точках процесса сжатия показывают, что степень сжатия сильно зависит от момента масштабирования веса, но не существует правила выбора оптимального момента масштабирования для программы, ориентированной на сжатие любых типов информации.

Применение

Сжатие данных по Хаффману применяется при сжатии фото- и видеоизображений (JPEG , стандарты сжатия MPEG), в архиваторах (PKZIP , LZH и др.), в протоколах передачи данных MNP5 и MNP7.

Примечания

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М .: Вильямс, 2006. - 1296 с. - ISBN 0-07-013151-1
• Д. Сэломон. Сжатие данных, изображения и звука. - М .: Техносфера, 2004. - 368 с. - 3000 экз. - ISBN 5-94836-027-X
• Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Хаффмана // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М .: Вильямс, 2006. - С. 392-398. - ISBN 0-201-74395-7

Ссылки

• Код Хаффмана (WebArchive)
• Сжатие по алгоритму Хаффмана на algolist.manual.ru

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

Дерево Хаффмана для файла, содержащего Z разных символов имеет Z листьев. Путь от корня к листу, который представляет определенный символ, определяет кодировку, и каждый шаг на пути к листу определяет кодировку (которая может быть 0 , 1 , ..., (N-1) ). Путём размещения часто встречающихся символы ближе к корню, и менее часто встречающихся символов дальше от корня, и достигается желаемое сжатие. Строго говоря, такое дерево будет деревом Хаффмана, только если в результате кодирования будет использовано минимальное число N -ичных символов для кодирования заданного файла.

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

На рисунке ниже показан пример троичного дерева Хаффмана, символы "a " и "е " кодируются с помощью одной троичного символа; менее часто встречающиеся символы "s " и "p " кодируются с помощью двух троичных символов и наиболее редко встречающиеся символы "x ", "q " и "y " кодируются с помощью трех троичных символов каждый.

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

Зная количество входных символов Z , значение N , обозначающее "N -арность" дерева Хаффмана и сам заголовок, необходимо найти первичное значение закодированных символов.

Входные данные

Входные данные начинаются с целого числа T , расположенного в отдельной строке и обозначающего количество последующих тестовых случаев. Далее задано каждый из T тестовых случаев, каждый из которых расположен в 3 -х строках следующим образом:

• Количество различных символов в тестовом случае Z (2 ≤ Z ≤ 20 );
• Число N , обозначающее " N -арность" дерева Хаффмана (2 ≤ N ≤ 10 );
• Строка, представляющая заголовок полученного сообщения, каждый символ будет цифрой в диапазоне . Эта строка будет содержать меньше 200 символов.

Примечание : Хотя и редко, но это возможно для заголовка, чтобы иметь несколько толкований при расшифровке (например, для заголовка "010011101100 ", и значениях Z = 5 и N = 2 ). Гарантируется, что во всех предлагаемых во входных данных тестовых случаях, имеется единственное решение.

Выходные данные

Для каждого из T тестовых случаев вывести Z строк, дающих декодированную версию каждого из Z символов в порядке возрастания. Используйте формат оригинал->кодировка , где оригинал - это десятичное число в диапазоне и соответствующая кодированная строка кодированных цифр для этих символов (каждая цифра ≥ 0 и < N ).

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

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

Алгоритм: история

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

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

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

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

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

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

Дерево Хаффмана: алгоритм построения

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

Как повысить эффективность сжатия

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

Как ускорить процесс сжатия

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

Вывод

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

1. code = следующий бит из потока, length = 1
2. Пока code < base
   code = code << 1
   code = code + следующий бит из потока
   length = length + 1
3. symbol = symb + code - base]

Другими словами, будем вдвигать слева в переменную 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 и т.д.

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

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

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

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

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

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

Наконец, можно использовать одно из свойств канонических кодов. Как уже было отмечено ранее, канонические коды вполне определяются своими длинами. Другими словами, все что необходимо декодеру - это список длин кодов символов. Учитывая, что в среднем длину одного кода для 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.

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

Книга:

Алгоритм кодирования Хаффмана очень похож на алгоритм сжатия Шеннона-Фано. Этот алгоритм был изобретен Девидом Хаффманом (David Huffman) в 1952 году ("A method for the Construction of Minimum-Redundancy Codes" ("Метод создания кодов с минимальной избыточностью")), и оказался еще более удачным, чем алгоритм Шеннона-Фано. Это обусловлено тем, что алгоритм Хаффмана математически гарантированно создает наименьший по размеру код для каждого из символов исходных данных.

Аналогично применению алгоритма Шеннона-Фано, нужно построить бинарное дерево, которое также будет префиксным деревом, где все данные хранятся в листьях. Но в отличие от алгоритма Шеннона-Фано, который является нисходящим, на этот раз построение будет выполняться снизу вверх. Вначале мы выполняем просмотр входных данных, подсчитывая количество появлений значений каждого байта, как это делалось и при использовании алгоритма Шеннона-Фано. Как только эта таблица частоты появления символов будет создана, можно приступить к построению дерева.

Будем считать эти пары символ-количество "пулом" узлов будущего дерева Хаффмана. Удалим из этого пула два узла с наименьшими значениями количества появлений. Присоединим их к новому родительскому узлу и установим значение счетчика родительского узла равным сумме счетчиков его двух дочерних узлов. Поместим родительский узел обратно в пул. Продолжим этот процесс удаления двух узлов и добавления вместо них одного родительского узла до тех пор, пока в пуле не останется только один узел. На этом этапе можно удалить из пула один узел. Он является корневым узлом дерева Хаффмана.

Описанный процесс не очень нагляден, поэтому создадим дерево Хаффмана для предложения "How much wood could a woodchuck chuck?" Мы уже вычислили количество появлений символов этого предложения и представили их в виде таблицы 11.1, поэтому теперь к ней потребуется применить описанный алгоритм с целью построения полного дерева Хаффмана. Выберем два узла с наименьшими значениями. Существует несколько узлов, из которых можно выбрать, но мы выберем узлы "m" и Для обоих этих узлов число появлений символов равно 1. Создадим родительский узел, значение счетчика которого равно 2, и присоединим к нему два выбранных узла в качестве дочерних. Поместим родительский узел обратно в пул. Повторим цикл с самого начала. На этот раз мы выбираем узлы "а" и "Д.", объединяем их в мини-дерево и помещаем родительский узел (значение счетчика которого снова равно 2) обратно в пул. Снова повторим цикл. На этот раз в нашем распоряжении имеется единственный узел, значение счетчика которого равно 1 (узел "Н") и три узла со значениями счетчиков, равными 2 (узел "к" и два родительских узла, которые были добавлены перед этим). Выберем узел "к", присоединим его к узлу "H" и снова добавим в пул родительский узел, значение счетчика которого равно 3. Затем выберем два родительских узла со значениями счетчиков, равными 2, присоединим их к новому родительскому узлу со значением счетчика, равным 4, и добавим этот родительский узел в пул. Несколько первых шагов построения дерева Хаффмана и результирующее дерево показаны на рис. 11.2.

Рисунок 11.2. Построение дерева Хоффмана

Используя это дерево точно так же, как и дерево, созданное для кодирования Шеннона-Фано, можно вычислить код для каждого из символов в исходном предложении и построить таблицу 11.5.

Таблица 11.5. Коды Хаффмана для символов примера предложения

Символ - Количество появлений

Пробел - 00

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

Теперь можно вычислить код для всего предложения. Он начинается с битов:

1111110111100001110010100...

и содержит всего 131 бит. Если бы исходное предложение было закодировано кодами ASCII, по одному байту на символ, оно содержало бы 286 битов. Таким образом, в данном случае коэффициент сжатия составляет приблизительно 54%.

Повторим снова, что, как и при применении алгоритма Шеннона-Фано, необходимо каким-то образом сжать дерево и включить его в состав сжатых данных.

Восстановление выполняется совершенно так же, как при использовании кодирования Шеннона-Фано: необходимо восстановить дерево из данных, хранящихся в сжатом потоке, и затем воспользоваться им для считывания сжатого потока битов.

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

Эта высокоуровневая подпрограмма TDHuffroanCompress, выполняющая кодирование Хаффмана, приведена в листинге 11.5.

Листинг 11.5. Высокоуровневая подпрограмма кодирования Хаффмана

procedure TDHuffmanCompress(aInStream, aOutStream: TStream);

HTree: THuffmanTree;

HCodes: PHuffmanCodes;

BitStrm: TtdOutputBitStream;

Signature: longint;

{вывести информацию заголовка (сигнатуру и размер несжатых данных)}

Signature:= TDHuffHeader;

aOutStream.WriteBuffer(Signature, sizeof(longint));

Size:= aInStream.Size;

aOutStream.WriteBuffer(Size, sizeof(longint));

{при отсутствии данных для сжатия необходимо выйти из подпрограммы}

if (Size = 0) then

{подготовка}

{создать сжатый поток битов}

BitStrm:= TtdOutputBitStream.Create(aOutStream);

{распределить память под дерево Хаффмана}

HTree:= THuffmanTree.Create;

{определить распределение символов во входном потоке и выполнить восходящее построение дерева Хаффмана}

HTree.CalcCharDistribution(aInStream);

{вывести дерево в поток битов для облегчения задачи программы восстановления данных}

HTree.SaveToBitStream (BitStrm);

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

if not HTree.RootIsLeaf then begin

{распределить память под массив кодов}

{вычислить все коды}

HTree.CalcCodes(HCodes^);

{сжать символы входного потока в поток битов}

DoHuffmanCompression(aInStream, BitStrm, HCodes^);

if (HCodes <> nil) then

Dispose(HCodes);

Код содержит множество элементов, которые мы еще не рассматривали. Но мы вполне можем вначале рассмотреть работу программы в целом, а затем приступить к рассмотрению каждого отдельного этапа. Прежде всего, мы записываем в выходной поток небольшой заголовок, за которым следует значение длины входного потока. Впоследствии эта информация упростит задачу восстановления данных, гарантируя, что сжатый поток соответствует созданному нами. Затем мы создаем объект потока битов, содержащий выходной поток. Следующий шаг -создание экземпляра класса THuffmanTree. Этот класс, как вскоре будет показано, будет использоваться для создания дерева Хаффмана и содержит различные методы, помогающие в решении этой задачи. Один из методов этого нового объекта, вызываемых в первую очередь, метод CalcCharDistribution, определяет статистическую информацию распределения символов во входном потоке, а затем строит префиксное дерево Хаффмана.

После того, как дерево Хаффмана построено, можно вызвать метод SaveToBitStream, чтобы записать структуру дерева в выходной поток.

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

В противном случае входной поток должен содержать, по меньшей мере, два различных символа, и дерево Хаффмана имеет вид обычного дерева, а не единственного узла. В этом случае мы выполняем оптимизацию: вычисляем таблицу кодов для каждого символа, встречающегося во входном потоке. Это позволит сэкономить время на следующем этапе, когда будет выполняться реальное сжатие, поскольку нам не придется постоянно перемещаться по дереву для выполнения кодирования каждого символа. Массив HCodes - простой 256-элементный массив, содержащий коды всех символов и построенный посредством вызова метода CalcCodes объекта дерева Хаффмана.

И, наконец, когда все эти структуры данных определены, мы вызываем подпрограмму DoHuffmanCompression, выполняющую реальное сжатие данных. Код этой подпрограммы приведен в листинге 11.6.

Листинг 11.6. Цикл сжатия Хаффмана

procedure DoHuffmanCompression(aInStream: TStream;

aBitStream: TtdOutputBitStream;

var aCodes: THuffmanCodes);

Buffer: PByteArray;

BytesRead: longint;

{сбросить входной поток в начальное состояние}

while (BytesRead <> 0) do

{записать строку битов для каждого символа блока}

for i:= 0 to pred(BytesRead) do aBitStream.WriteBits(aCodes]);

BytesRead:= aInStream.Read(Buffer^, HuffmanBufferSize);

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

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

Вначале мы объявляем узел дерева Хаффмана THaffxnanNode и массив этих узлов THaffmanNodeArray фиксированного размера. Этот массив будет использоваться для создания реальной структуры дерева и будет содержать ровно 511 элементов. Почему именно это количество?

Это число определяется небольшой теоремой (или леммой) о свойствах бинарного дерева, которая еще не упоминалась.

Листинг 11.7. Класс дерева Хаффмана

PHuffmanNode = ^THuffmanNode;

THuffmanNode = packed record

hnCount: longint;

hnLeftInx: longint;

hnRightInx: longint;

hnIndex: longint;

PHuffmanNodeArray = ^THuffmanNodeArray;

THuffmanNodeAr ray = array of THuffmanNode;

THuffmanCodeStr = string;

PHuffmanCodes = ^THuffmanCodes;

THuffmanCodes = array of TtdBitString;

THuffmanTree = class private

FTree: THuffmanNodeArray;

procedure htBuild;

procedure htCalcCodesPrim(aNodeInx: integer;

var aCodeStr: THuffmanCodeStr;

var aCodes: THuffmanCodes);

function htLoadNode(aBitStream: TtdInputBitStream): integer;

procedure htSaveNode(aBitStream: TtdOutputBitStream;

aNode: integer);

constructor Create;

procedure CalcCharDistribution(aStream: TStream);

procedure CalcCodes(var aCodes: THuffmanCodes);

function DecodeNextByte(aBit St ream: TtdInputBitStream): byte;

procedure LoadFromBitStream(aBitStream: TtdInputBitStream);

function RootIsLeaf: boolean;

procedure SaveToBitStream(aBitStream: TtdOutputBitStream);

property Root: integer read FRoot;

Предположим, что дерево содержит только два типа узлов: внутренние, имеющие ровно по два дочерних узла, и листья, не имеющие узлов (иначе говоря, не существует узлов, имеющих только один дочерний узел, - именно такой вид имеет префиксное дерево). Сколько внутренних узлов имеет это дерево, если оно содержит n листьев? Лемма утверждает, что такое дерево содержит ровно n - 1 внутренних узлов. Это утверждение можно доказать методом индукции. Когда n = 1, лемма явно выполняется, поскольку дерево содержит только корневой узел.

Теперь предположим, что лемма справедлива для всех i < n, где n < 1, и рассмотрим случай, когда i = n. В этом случае дерево должно содержать, по меньшей мере, один внутренний узел - корневой. Этот корневой узел имеет два дочерних дерева: левое и правое. Если левое дочернее дерево имеет x листьев, то, согласно сделанному нами допущению, оно должно содержать x - 1 внутренних узлов, поскольку x < n. Аналогично, согласно сделанному допущению, если правое дочернее дерево имеет y листьев, оно должно содержать y - 1 внутренних узлов. Все дерево содержит n листьев, причем это число должно быть равно X + Y (вспомните, что корневой узел является внутренним). Следовательно, количество внутренних узлов равно (x-1) + (y-1) + 1, что составляет в точности n-1.

Чем же эта лемма может нам помочь? В префиксном дереве все символы должны храниться в листьях. В противном случае было бы невозможно получить однозначные коды. Следовательно, независимо от его внешнего вида, префиксное дерево, подобное дереву Хаффмана, будет содержать не более 511 узлов: не более 256 листьев и не более 255 внутренних узлов. Следовательно, мы должны быть в состоянии реализовать дерево Хаффмана (по крайней мере, обеспечивающее кодирование значений байтов) в виде 511-элементного массива.

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

Причина выбора типов кода Хаффмана (THuffmanCodeStr и THuffmanCodes) станет понятной после рассмотрения генерации кодов для каждого из символов.

Конструктор Create класса дерева Хаффмана всего лишь выполняет инициализацию внутреннего массива дерева.

Листинг 11.8. Конструирование объекта дерева Хаффмана

constructor THuffmanTree.Create;

inherited Create;

FillChar(FTree, sizeof(FTree), 0);

for i:= 0 to 510 do

FTree[i].hnIndex:= i;

Поскольку конструктор не распределяет никакой памяти, и никакое распределение памяти не выполняется ни в каком другом объекте класса, явному деструктору нечего делать. Поэтому по умолчанию класс использует метод TObject.Destroy.

Первым методом, вызываемым для дерева Хаффмана в подпрограмме сжатия, был метод CalcCharDistribution. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.

Листинг 11.9. Вычисление количеств появлений символов

procedure THuffmanTree.CalcCharDistribution(aStream: TStream);

Buffer: PByteArray;

BytesRead: integer;

{считывать все байты с поддержанием счетчиков появлений для каждого значения байта, начиная с начала потока}

aStream.Position:= 0;

GetMem(Buffer, HuffmanBufferSize);

while (BytesRead <> 0) do

for i:= pred(BytesRead) downto 0 do

inc(FTree].hnCount);

BytesRead:= aStream.Read(Buffer^, HuffmanBufferSize);

FreeMem(Buffer, HuffmanBufferSize);

{построить дерево}

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

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

Листинг 11.10. Построение дерева Хаффмана

function CompareHuffmanNodes(aData1, aData2: pointer): integer; far;

Node1: PHuffmanNode absolute aData1;

Node2: PHuffmanNode absolute aData2;

{ПРИМЕЧАНИЕ: эта подпрограмма сравнения предназначена для реализации очереди по приоритету Хаффмана, которая является *сортирующим деревом с выбором наименьшего элемента*. Поэтому она должна возвращать элементы в порядке, противоположном ожидаемому}

if (Node1^.hnCount) > (Node2^.hnCount) then

if (Node1^.hnCount) = (Node2^.hnCount)

else Result:= 1;

procedure THuffmanTree.htBuild;

PQ: TtdPriorityQueue;

Node1: PHuffmanNode;

Node2: PHuffmanNode;

RootNode: PHuffmanNode;

{создать очередь по приоритету}

PQ:= TtdPriorityQueue.Create(CompareHuffmanNodes, nil);

PQ.Name:= "Huffman tree minheap";

{добавить в очередь все ненулевые узлы}

for i:= 0 to 255 do

if (FTree[i].hnCount <> 0) then

PQ.Enqueue(@FTree[i]);

{ОСОБЫЙ СЛУЧАЙ: существует только один ненулевой узел, т.е. входной поток состоит только из одного символа, повторяющегося один или более раз. В этом случае значение корневого узла устанавливается равным значению индекса узла единственного символа}

if (PQ.Count = 1) then begin

RootNode:= PQ.Dequeue;

FRoot:= RootNode^.hnIndex;

{в противном случае имеет место обычный случай наличия множества различных символов}

{до тех пор, пока в очереди присутствует более одного элемента, необходимо выполнять удаление двух наименьших элементов, присоединять их к новому родительскому узлу и добавлять его в очередь}

while (PQ.Count > 1) do

Node1:= PQ.Dequeue;

Node2:= PQ.Dequeue;

RootNode:= @FTree;

with RootNode^ do

hnLeftInx:= Node1^.hnIndex;

hnRightInx Node2^.hnIndex;

hnCount:= Node1^.hnCount + Node2^.hnCount;

PQ.Enqueue(RootNode);

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

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

И, наконец, мы освобождаем объект очереди по приоритету. Теперь дерево Хаффмана полностью построено.

Следующий метод, вызываемый в высокоуровневой подпрограмме сжатия - метод, который выполняет запись дерева Хаффмана в выходной поток битов. По существу, нам необходимо применить какой-либо алгоритм, выполняющий запись достаточного объема информации, чтобы можно было восстановить дерево. Одна из возможностей предусматривает запись символов и их значений счетчика появлений. При наличии этой информации программа восстановления может без труда восстановить дерево Хаффмана, просто вызывая метод htBuild. Это кажется здравой идеей, если не учитывать объем, занимаемый таблицей символов и количеств их появлений в сжатом выходном потоке. В этом случае каждый символ занимал бы в выходном потоке полный байт, а его значение счетчика занимало бы определенное фиксированное количество байтов (например, два байта на символ, чтобы можно было подсчитывать вплоть до 65535 появлений). При наличии во входном потоке 100 отдельных символов вся таблица занимала бы 300 байт. Если бы во входном потоке присутствовали все возможные символы, таблица занимала бы 768 байт.

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

Конечно, если бы входной поток был достаточно большим, некоторые из значений счетчиков могли бы превысить размер 2-байтового слова, и для каждого символа пришлось бы использовать по три или даже четыре байта.

Более рациональный подход - игнорировать значения счетчиков символов и сохранять реальную структуру дерева. Префиксное дерево содержит два различных вида узлов: внутренние с двумя дочерними узлами и внешние, не имеющие дочерних узлов. Внешние узлы - это узлы, содержащие символы. Выполним обход дерева, применив один из обычных методов обхода (фактически, мы будем использовать метод обхода в ширину). Для каждого достигнутого узла будем записывать нулевой бит, если узел является внутренним, или единичный бит, если узел является внешним, за которым будет следовать представляемый узлом символ. Код реализации метода SaveToBitStream и вызываемого им рекурсивного метода htSaveNode, который выполняет реальный обход дерева и запись информации в поток битов, представлен в листинге 11.11.

Листинг 11.11. Запись дерева Хаффмана в поток битов

procedure THuffmanTree.htSaveNode(aBitStream: TtdOutputBitStream;

aNode: integer);

{если этот узел является внутренним, выполнить запись нулевого бита, затем левого дочернего дерева, а затем - правого дочернего дерева}

if (aNode >= 256) then begin

aBitStream.WriteBit(false);

htSaveNode(aBitStream, FTree.hnLeftInx);

htSaveNode(aBitStream, FTree.hnRightInx);

{в противном случае узел является листом и нужно записать единичный бит, а затем символ}

aBitStream.WriteBit(true);

aBitStream.WriteByte (aNode);

{aNode - символ}

procedure THuffmanTree.SaveToBitStream(aBitStream: TtdOutputBitStream);

htSaveNode(aBitStream, FRoot);

Если бы во входном потоке присутствовало 100 отдельных символов, он содержал бы 99 внутренних узлов, и требовалось бы всего 199 битов для хранения информации об узлах плюс 100 байтов для хранения самих символов - всего около 125 байтов. Если бы во входном потоке были представлены все символы, требовалось бы 511 битов для хранения информации об узлах плюс место для хранения 256 символов. Таким образом, всего для хранения дерева требовалось бы 320 байтов.

Полный код подпрограммы сжатия дерева Хаффмана можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHuffmn.pas.

После того, как мы рассмотрели реализацию сжатия Хаффмана, приступим к вопросу решения задачи восстановления данных. Код подпрограммы TDHuffmanDeconpress, управляющей этим процессом, приведен в листинге 11.12.

Листинг 11.12. Подпрограмма TDHuffmanDecoropress

procedure TDHuffmanDecompress(aInStream, aOutStream: TStream);

Signature: longint;

HTree: THuffmanTree;

BitStrm: TtdInputBitStream;

{выполнить проверку на предмет того, что входной поток является потоком, правильно закодированным методом Хаффмана}

aInStream.Seek(0, soFromBeginning);

aInStream.ReadBuffer(Signature, sizeof(Signature));

if (Signature <> TDHuffHeader) then

raise EtdHuffmanException.Create(FmtLoadStr(tdeHuffBadEncodedStrm,));

aInStream.ReadBuffer(Size, sizeof(longint));

{если данные для восстановления отсутствуют, осуществить выход из подпрограммы}

if (Size = 0) then

{подготовиться к восстановлению}

{создать поток битов}

BitStrm:= TtdInputBitStream.Create(aInStream);

BitStrm.Name:= "Huffman compressed stream";

{создать дерево Хаффмана}

HTree.LoadFromBitStream(BitStrm);

{если корневой узел дерева Хаффмана является листом, исходный поток состоит только из повторений одного символа}

if HTree.RootIsLeaf then

WriteMultipleChars(aOutStream, AnsiChar(HTree.Root), Size) {в противном случае выполнить восстановление символов входного потока посредством использования дерева Хаффмана}

DoHuffmanDecompression(BitStrm, aOutStream, HTree, Size);

Прежде всего, мы проверяем, начинается ли поток с корректной сигнатуры. Если нет, не имеет смысла продолжать процесс, поскольку поток явно содержит ошибки.

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

Листинг 11.13. Подпрограмма DoHuffmanDecompression

procedure DoHuffmanDecompression(aBitStream: TtdInputBitStream;

aOutStream: TStream; aHTree: THuffmanTree; aSize: longint);

CharCount: longint;

Buffer: PByteArray;

BufEnd: integer;

GetMem(Buffer, HuffmanBufferSize);

{предварительная установка переменных цикла}

{повторять процесс до тех пор, пока не будут восстановлены все символы}

Ch:= aHTree.DecodeNextByte (aBitStream);

Buffer^ :=Ch;

{если буфер заполнен, необходимо выполнить его запись}

if (BufEnd = HuffmanBufferSize) then begin

aOutStream.WriteBuffer(Buffer^, HuffmanBufferSize);

{если в буфере остались какие-либо данные, необходимо выполнить его запись}

if (BufEnd <> 0) then

aOutStream.WriteBuffer(Buffer^, BufEnd);

FreeMem(Buffer, HuffmanBufferSize);

По существу подпрограмма представляет собой цикл, внутри которого многократно выполняется декодирование байтов и заполнение буфера. Когда буфер заполняется, мы записываем его в выходной поток и начинаем заполнять его снова. Декодирование выполняется при помощи метода DecodeNextByte класса THuffmanTree.

Листинг 11.14. Метод DecodeNextByte

function THuffmanTree.DecodeNextByte(aBitStream: TtdInputBitStream): byte;

NodeInx: integer;

NodeInx:= FRoot;

while (NodeInx >= 256) do

if not aBitStream.ReadBit then

NodeInx:= FTree.hnLeftInx else

NodeInx:= FTree.hnRightInx;

Result:= NodeInx;

Этот метод крайне прост. Он просто начинает обработку с корневого узла дерева Хаффмана, а затем для каждого бита, считанного из входного потока битов, в зависимости от того, был ли он нулевым или единичным, выполняет переход по левой или правой связи. Как только подпрограмма достигает листа, она возвращает индекс достигнутого узла (его значение будет меньше или равно 255). Этот узел является декодированным байтом.

Полный код выполнения восстановления дерева Хаффмана можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHuffmn.pas.