Коды Хаффмена - Курсовая работа

3.2 Принцип работы алгоритма ХаффменаРазвитие программ-архиваторов позволило добиться не только сжатия без потерь, но также возможности создания многотомных архивов и архивов в различных форматах. Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации. Основными техническими характеристиками процессов сжатия и результатов их работы являются: - степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков; скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока; Речь пойдет о коде Хаффмена (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code).В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Можно было бы подбросить монету множество раз, построить большую таблицу результатов, а затем выполнить определенный статистический анализ этого большого набора данных с целью формулирования или доказательства какой-то теоремы. Для построения набора данных, результаты подбрасывания монеты можно было бы записывать несколькими различными способами: можно было бы записывать слова "орел" или "решка"; можно было бы записывать буквы "О" или "Р"; или же можно было бы записывать единственный бит (например "да" или "нет", в зависимости от того, на какую сторону падает монета). Согласно теории информации, результат каждого подбрасывания монеты можно закодировать единственным битом, поэтому последний приведенный вариант был бы наиболее эффективным с точки зрения объема памяти, необходимого для кодирования результатов. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio).В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины. Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент sh вероятность появления которого равняется p(s,), выгоднее всего представлять-1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получается равным-log2 p(s,) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования.Существует довольно много реализаций алгоритма группы KWE, среди которых наиболее распространенными являются алгоритм Лемпеля-Зива (алгоритм LZ) и его модификация алгоритм Лемпеля-Зива-Велча (алгоритм LZW).Для алгоритма LZ основан на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. Это будет продолжаться до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк, а новая фраза, состоящая из совпадающего индекса и следующего за ним символа - записывается в словарь. Алгоритм Lossless JPEG разработан группой экспертов в области фотографии (Joint Photographic Expert Group).Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Классический алгоритм Хаффмена на входе получает таблицу частот встречаемости символов в сообщении. Алгоритм построения Н-дерева прост и элегантен: - символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение; Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева.В результате мы получили бы самый медленный в мире алгоритм сжатия, так как построение Н-дерева - это слишком большая работа и производить ее при обработке каждого символа неразумно. Вторая операция - перестановка узлов дерева - требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узл

Содержание

Введение

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

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

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

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

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

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

2.2 Особенности кодирования Хаффмена

2.3 Применение кодирования Хаффмена

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

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

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

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

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

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

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

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