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

Содержание

 

 

Введение

 

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

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

Основными техническими характеристиками процессов сжатия и результатов их работы являются:

- степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

- скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;

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

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

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

 

 

 

 

 

 

 

 

 

 

Глава 1 Сжатие данных

1. Представление и сжатие данных

 

Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой - ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики).

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

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

Сжатие данных (data compression) - это алгоритм эффективного кодирования  информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio). Он вычисляется путем вычитания из единицы частного от деления размера сжатых данных на размер исходных данных и обычно выражается в процентах. Например, если размер сжатых данных равен 1000 бит, а несжатых - 4000 бит, коэффициент сжатия составит 75%, т.е. мы избавились от трех четвертей исходного количества битов.

Конечно, сжатые данные могут  быть записаны в форме недоступной  для непосредственного считывания и понимания человеком. Люди нуждаются в определенной избыточности представления данных, способствующей их эффективному распознаванию и пониманию. Применительно к эксперименту с подбрасыванием монеты последовательности символов "О" и "Р" обладают большей наглядностью, чем 8-битовые значения байтов. (Возможно, что для большей наглядности пришлось бы разбить последовательности символов "О" и "Р" на группы, скажем, по 10 символов в каждой.) Иначе говоря, возможность выполнения сжатия данных бесполезна, если отсутствует возможность их последующего восстановления. Эту обратную операцию называют декодированием (decoding).

Существует два основных типа сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие без  потерь проще для понимания. Это  метод сжатия данных, когда при восстановлении данных возвращается точная копия исходных данных. Такой тип обеспечивает при распаковке упакованного файла  создание файла, который имеет в точности то же содержимое, что и оригинал перед его сжатием. И напротив, сжатие с потерями не позволяет при восстановлении получить те же исходные данные. Это кажется недостатком, но для определенных типов данных, таких как данные изображений и звука, различие между восстановленными и исходными данными не имеет особого значения: наши зрение и слух не в состоянии уловить образовавшиеся различия. В общем случае алгоритмы сжатия с потерями обеспечивают более эффективное сжатие, чем алгоритмы сжатия без потерь (в противном случае их не стоило бы использовать вообще). Для примера можно сравнить предназначенный для хранения изображений формат с потерями JPEG с форматом без потерь GIF. Множество форматов потокового аудио и видео, используемых в Internet для загрузки мультимедиа-материалов, являются алгоритмами сжатия с потерями.

1.2  Основа всех методов сжатия

 

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

Точная связь  между вероятностями и кодами установлена в теореме Шеннона  о кодировании источника, которая  гласит, что элемент s_h вероятность появления которого равняется p(s,), выгоднее всего представлять -1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получается равным -log₂ p(s,) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей F= {pis,} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное.

Это значение также  называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.

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

Существует 2^л различных файлов длины п бит, где л = 0, 1, 2,... Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2^л исходным файлам будет соответствовать самое большее 2^л-1 различающихся сжатых файлов. Тогда, по крайней мере, одному архивному файлу будет соответствовать несколько различающихся исходных, и, следовательно, его декодирование без потерь информации невозможно в принципе.

1.3 Обзор существующих программ сжатия данных без потерь

 

В настоящее время  существует очень много алгоритмов сжатия данных без потерь. Наиболее распространенными являются такие, как: Lossless JPEG, алгоритм Хаффмена, алгоритмы группы KWE

Существует довольно много реализаций алгоритма группы KWE, среди которых наиболее распространенными являются алгоритм Лемпеля-Зива (алгоритм LZ) и его модификация алгоритм Лемпеля-Зива-Велча (алгоритм LZW).Для алгоритма LZ основан на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. Когда происходит считывание очередного символа входной последовательности данных, то он прибавляется к текущей строке. Это будет продолжаться до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк, а новая фраза, состоящая из совпадающего индекса и следующего за ним символа – записывается в словарь. Если эта фраза появляется еще раз, то она может быть использована для построения более длинной фразы. Это способствует повышению сжатия информации. Семейство LZ-подобных алгоритмов могут различаться, например, методом поиска повторяющихся цепочек.

Алгоритм Lossless JPEG разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений. Этот формат разрабатывался, прежде всего, для хранения изображений в медицинских целях, то есть для тех случаев, когда важно иметь большое изображение без малейших потерь качества.

Суть алгоритма кодирования  по методу Хаффмена в том, что некоторые  символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится. В результате получается систематизация данных в виде дерева («двоичное дерево»).  Алгоритм Хаффмена основан на этой идее с той лишь разницей, что она применяется ко всем символам алфавита. На первом шаге определяются числа повторений (веса) всех символов. На втором шаге строится дерево кодирования. Используются две структуры данных - массив и дерево, в массив заносятся все символы и их веса, дерево пусто. Затем находим два самых редких символа, исключаются из массива и добавляются в дерево (листья). Также создается новый узел дерева с весом равным сумме весов найденных символов и содержащий ссылки на эти символы. Этот узел добавляется в массив. Процедура повторяется пока в массиве не останется один элемент. Третий шаг - собственно кодирование.

Эта работа и посвящена алгоритму Хаффмена.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2 Коды Хаффмена

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

 

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

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

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