Алгоритм Хаффмана

Размещено на http://www.allbest.ru/

Контрольная работа

Алгоритм Хаффмана

Брянск-2009 г.

Введение

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

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

Первым такой алгоритм опубликовал Дэвид Хаффман (David Huffman) в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.

1. Биография Д. Хаффмана

Дэвид Хаффман родился в 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 лет Дэвид Хаффман скончался от рака.

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

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

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

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

Кодирование Оптимальное (англ. optimal coding) - создание кодов, обеспечивающих максимальную скорость и надежность приема и переработки информации.

Свойства оптимального кодирования

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

2. Алгоритм Хаффмана

Теперь рассмотрим принцип работы алгоритма Хаффмана.

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

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее:

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

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из «узлов» D и A новый «узел», частота вхождения для которого будет равна сумме частот D и A:

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

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

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (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-ю битами (один байт), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла. Сжатие складывается следующим образом:

хаффман сжатие файл символ

Первоначальный размер файла: 100 байт - 800 бит;

Размер сжатого файла: 30 байт - 240 бит;

240 - 30% из 800, так что мы сжали этот файл на 70%.

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

Первое решение: мы должны сохранять дерево вместе с файлом. Это превращается в итоге в увеличение размеров выходного файла.

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин (где и находятся наши символы), всего 11. 4 байта 11 раз - 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая, что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили - трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

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

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

Заключение

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

Литература

1. Новиков Ф.А. Дискретная математика для программистов - Питер, 2007

2. Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование - М.: Феникс, 2002

3. http://ru.wikipedia.org/wiki/Код_Хаффмана

Размещено на Allbest.ru