Алгоритм построения оптимального префиксного кода

.

 

 

 

Рисунок 3.1 – Формирование нового узла

 

Номер в рамке –  сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый узел с суммарной частотой вхождения. Самая низкая частота теперь у F и нового узла. Снова сделаем операцию слияния узлов: Рисунок 3.2 – Слияние узлов.

 

 

 

 

 

Рисунок 3.2 – Слияние  узлов

 

Рассматриваем таблицу  снова для следующих двух символов (B и E). Мы продолжаем в этот режим пока все дерево не сформировано, т.е. пока все не сведется к одному узлу: Рисунок 3.3 – Формирование дерева.

 

 

 

 

 

 

 

 

Рисунок 3.3 – Формирование дерева

 

Теперь, когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмена для нашего символа C – 00. Для следующего символа (А) у нас получается – лево, право, лево, лево, что выливается в последовательность 0100. Выполнив выше сказанное для всех символов, получим:

• C = 00 (2 бита)
• A = 0100 (4 бита)
• D = 0101 (4 бита)
• F = 011 (3 бита)
• B = 10 (2 бита)
• E = 11 (2 бита)

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

Таблица 3.3 – Уменьшение размера выходного файла

 

Частота	Первоначально	Уплотненные биты	Уменьшено на
C 30 A 10 D 5 F 10 B 20 E 25	30 x 8 = 240 10 x 8 = 80 5 x 8 = 40 10 x 8 = 80 20 x 8 = 160 25 x 8 = 200	30 x 2 = 60 10 x 3 = 30 5 x 4 = 20 10 x 4 = 40 20 x 2 = 40 25 x 2 = 50	180 50 20 40 120 150

 

• первоначальный размер файла: 100 байт – 800 бит;
• размер сжатого файла: 30 байт – 240 бит;
• 240 – 30% из 800, так что мы сжали этот файл на 70%.

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

Первое решение: мы должны сохранять дерево вместе с файлом. Это превращается в итоге в увеличение размеров выходного файла. В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной. Таблица в нашем примере имеет 5 узлов плюс 6 вершин (где и находятся наши символы), всего 11. 4 байта 11 раз – 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику – наша таблица будет приблизительно 50 байтов длины. Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая, что первоначальная длинна файла в рассматриваемом примере была 100 байт – мы получили 20% сжатие информации. Выполнена трансляция символьного ASCII набора в наш новый набор, требующий меньшее количество знаков по сравнению со стандартным.

Рассмотрим максимум, который мы можем получить для  различных разрядных комбинаций в оптимальном дереве, которое  является несимметричным.

Мы получим, что можно иметь только:

• 4 - 2 разрядных кода;
• 8 - 3 разрядных кодов;
• 16 - 4 разрядных кодов;
• 32 - 5 разрядных кодов;
• 64 - 6 разрядных кодов;
• 128 - 7 разрядных кодов.

Необходимо еще два 8 разрядных кода.

• 4 - 2 разрядных кода;
• 8 - 3 разрядных кодов;
• 16 - 4 разрядных кодов;
• 32 - 5 разрядных кодов;
• 64 - 6 разрядных кодов;
• 128 - 7 разрядных кодов.

--------

254

Итак, мы имеем итог из 256 различных комбинаций, которыми можно  кодировать байт. Из этих комбинаций лишь 2 по длине равны 8 битам. Если мы сложим число битов, которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме, мы сжали 256 байт к 195 или 33%, таким образом, максимально идеализированный Huffman может достигать сжатия в 33%, когда используется на уровне байта.

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

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

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

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

3.3 Примеры реализации алгоритма   Хаффмена

 

Пример 1. Построение кодового дерева. Пусть задана исходная последовательность символов: aabbbbbbbbccсcdeeeee.

Ее исходный объем  равен 20 байт (160 бит). В соответствии с данными закодированная исходная последовательность символов будет выглядеть следующим образом: 110111010000000011111111111111001010101010: Рисунок 3.4 - Создание оптимальных префиксных кодов.

Следовательно, ее объем  будет равен 42 бита. Коэффициент  сжатия приближенно равен 3,8.

 

 
Рисунок 3.4 - Создание оптимальных префиксных кодов

 

Пример 2. Представим себе изображение из 8-и битовых пикселов, в котором половина пикселов равна 127, а другая половина имеет значение 128. Проанализируем эффективность метода RLE для индивидуальных битовых областей по сравнению с кодированием Хаффмена.

Анализ. Двоичная запись 127 равна 01111111, а 128 - 10000000. Половина пикселей поверхности будет нулем, а вторая половина единицей. В самом плохом случае область будет походить на шахматную доску, то есть, иметь много серий длины 1. В этом случае каждая серия требует кода в 1 бит, что ведет к одному кодовому биту на пиксель на область, или 8 кодовых битов на пиксель для всего изображения. Это приводит к полному отсутствию сжатия. А коду Хаффмена для такого изображения понадобится всего два кода (поскольку имеется всего два разных пикселя), и они могут быть длины 1. Это приводит к одному кодовому биту на пиксель, то есть к восьмикратному сжатию.

 

Пример 3. Программная реализация алгоритма Хаффмена с помощью кодового дерева.

Листинг программной  реализации алгоритма Хаффмена с помощью кодового дерева представлен в приложении А.

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

 

заключение

 

Думая о данных, обычно мы представляем себе не что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных.

Многое изменилось тогда, когда были созданы первые ЭВМ, размеры которых вне всякой критики, а объемы жестких дисков — меньше, чем ПЗУ в первых мобильных телефонах. Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники. Одна из самых главных проблем при работе с данными — это их размер. Нам всегда хочется, что бы уместилось как можно больше. Тут-то весь прогрессивный мир и задумался о том, как поместить в такой маленький объем памяти как можно больше полезных документов. И вот ученые стали предлагать свои наработки, но большинство из этих теорем лишь доказывали возможность сжатия тех или иных данных. Идей о сжатии же и, тем более, о последующем разжатии было немного. Постепенно родился энтропийный анализ данных, позволяющий оценить компактность хранения информации и возможность ее сжатия — благодаря этому событию идеи начали воплощаться в реальность. Была предложена идея сжатия в результате подсчета частоты появления тех или иных байт в тексте: текст первоначально оценивается упаковщиком, подсчитывается частота появления в тексте каждой буквы, присутствующей в нем, частота повторения участков текста и т.д.; составляется таблица этих самых частот, по которой уже вторым проходом происходит упаковка/распаковка. Метод надолго засел в умах разработчиков. Его идеальной реализацией можно считать алгоритм Хаффмена и последующие доработки.

В этой работе мы провели анализ одного из самых распространенных методов сжатия данных. Речь шла о коде Хаффмена (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code). Рассмотрены основные идеи кода Хаффмена, исследованы ряд важных свойств оптимального кодирования и познакомлены с реализацией его на практике. Метод Хаффмена и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмена) – нашли широчайшее применение в нашей жизни.

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

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

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

 

Библиография

 

1. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2007
2. http://ru.wikipedia.org/wiki/Код_Хаффмена.
3. Симонович С.В. Информатика. Базовый курс. – СПб.: Питер, 2008.
4. Сергеенко B. C., Баринов В. В. Сжатие данных, речи, звука и изображений в телекоммуникационных системах. – М.: РадиоСофт, 2009.
5. Глушаков С. В. Лучшие программы для ПК. - СПб.: АСТ, 2008.
6. Панин В.В. Основы теории информации: учебное пособие для вузов. – М.: Бином. Лаборатория знаний, 2009. 
7. Зуев Ю.А. По океану дискретной математики. Том 2: От перечислительной комбинаторики до современной криптографии: Графы. Алгоритмы. Коды, блок-схемы, шифры. – М.: Либроком, 2012.
8. Павловская Т. А., Щупак Ю. А. C++. Объектно-ориентированное программирование. – СПб.: Питер, 2008.
9. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование. — СПб.: Физматлит, 2007.
10. Потапов В. Н. Введение в теорию информации. Учебное пособие. – Новосибирск: НГУ, 2009.
11. Верещагин Н. К., Щепин Е. В. Информация, кодирование и предсказание. – М.: МЦНМО, 2012.   
12. Ромащенко А. Е., Румянцев А. Ю., Шень А. Заметки по теории кодирования. – М.: МЦНМО, 2011.
13. Березкин Е.Ф. Основы теории информации и кодирования. – М.: МИФИ, 2010.
14. Сидельников В. М. Теория кодирования. – М.: Физматлит, 2008.
15. Чечёта С. И. Введение в дискретную теорию информации и кодирования. – М.:МЦНМО, 2011.