Метод Хаффмана

I. Общие сведения о сжатии данных 8

Введение

Сжатие данных (англ. data compression) - это алгоритмическое преобразование данных, производимых с целью уменьшения их объема. Он используется для более рационального использования устройств хранения и передачи данных. Синонимы - упаковка данных, сжатие, кодирование сжатия, кодирование источника. Обратная процедура называется восстановлением данных (декомпрессия).
Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение фрагментов в тексте (например, слова естественного или машинного языка). Такая избыточность обычно устраняется путем замены повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины.
Другой тип избыточности связан с тем, что некоторые значения в сжатых данных встречаются чаще, чем другие. Сокращение объема данных достигается путем замены часто встречающихся данных короткими кодовыми словами, а редкие данные - длинными (энтропийное кодирование). Сжатие данных, которые не обладают свойством избыточности (например, случайный сигнал или шум, зашифрованные сообщения), принципиально невозможно без потерь.
Мы все хорошо знаем, что такое информация. Интуитивно нам это вполне понятно, однако это скорее качественное восприятие предмета. Информация представляется нам одной из сущностей, которые невозможно точно определить и тем более измерить количественно. Однако, существует область математики, которая называется теорией информации, где информацию изучают именно количественно. Другим важным достижением теории информации является вполне строгое определение избыточности. Сейчас мы попытаемся истолковать это понятие интуитивно, указав, что есть избыточность для двух простых типов компьютерных данных, и что представляют собой данные, из которых удалена избыточность.
Первый тип информации - это текст. Текст представляет собой важнейший вид компьютерных данных. Огромное количество компьютерных программ и приложений являются по своей природе нечисловыми; они работают с данными, у которых основными элементарными компонентами служат символы текста. Компьютер способен сохранять и обрабатывать лишь двоичную информацию, состоящую из нулей и единиц. Поэтому каждому символу текста необходимо сопоставить двоичный код. Современные компьютеры используют так называемые коды ASCII (произносится «аски», а само слово ASCII является сокращением от «American Standard Code for Information Interchange»), хотя все больше компьютеров и приложений используют новые коды Unicode. ASCII представляет код фиксированной длины, где каждому символу присваивается 8-битовая последовательность (сам код занимает семь битов, а восьмой - проверочный, который изначально был задуман для повышения надежности кода). Код фиксированной длины представляется наилучшим выбором, поскольку позволяет компьютерным программам легко оперировать с символами различных текстов. С другой стороны, код фиксированной длины является по существу избыточным. В случайном текстовом файле мы ожидаем, что каждый символ встречается приблизительно равное число раз. Однако файлы, используемые на практике, навряд ли являются случайными. Они содержат осмысленные тексты, и по опыту известно, что, например, в типичном английском тексте некоторые буквы, такие, как «Е», «Т» и «А», встречаются гораздо чаще, чем «Z» и «Q». Это объясняет, почему код ASCII является избыточным, а также указывает на пути устранения избыточности. ASCII избыточен прежде всего потому, что независимо присваивает каждому символу, часто или редко используемому, одно и то же число бит (восемь). Чтобы удалить такую избыточность, можно воспользоваться кодами переменной длины, в котором короткие коды присваиваются буквам, встречающимся чаще, а редко встречающимся буквам достаются более длинные коды. Точно так работает кодирование Хаффманаю.

Метод Хаффмана – это адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью, разработанный в 1952 году Дэвидом Хаффманом. Данный метод применяется во многих архиваторах и форматах фалов. Этот метод основан на том, что различные символы любого алфавита имеют разную вероятность появления в тексте. Для примера - в русском языке буква "А" встречается намного чаще, чем "Ъ". Итак, раз разные символы имеют разные вероятности появления, следовательно, если кодировать их не все по 8 бит, как они хранятся в ASCII формате, а длину кода наиболее часто встречаемых уменьшить за счёт увеличения длины кода редких символов - можно сжать исходный текст.

Рассмотрим алгоритм кодирования информации, применяемый в методе Хаффмана на примере фразы «beep boop beer!». Прежде всего формируется алфавит символов с частотой появления каждого символа в тексте. Далее символы сортируются по убыванию частоты появления: