Методы Шеннона-фано и Хаффмена

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

Код строится следующим образом: все символы, встречающиеся в файле выписывают в таблицу в порядке убывания частот их появления. Затем их разделяют на две группы так, чтобы в каждой из них были примерно равные суммы частот символов. Первые биты кодов всех символов одной половины устанавливаются в "О", а второй — в "I". После этого каждую группу делят еще раз пополам и так до тех пор, пока в каждой группе не останется по одному символу. Допустим, файл состоит из некоторой символьной строки aaaaaaaaaabbbbbbbbccccccdddddeeeefff, тогда каждый символ этой строки можно закодировать как показано в табл. 8.1.

Таблица 8.1. Пример построения кода Шеннона-Фано

Итак, если обычно каждый символ кодировался 7—8 битами, то теперь требуется максимум 3 бита.

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

Более удачен в данном отношении метод Хаффмена. Он позволяет однозначно построить код с наименьшей средней длиной, приходящейся на символ.

Таблица 8.2. Пример кодировки одних и тех же символов различными кодами

Таблица 8.3. Пример кодировки одних И тех же символов различными кодами

Суть метода Хаффмена сводится к следующему. Символы, встречающиеся в файле, выписываются в столбец в порядке убывания вероятностей (частоты) их появления. Два последних символа объединяются в один с суммарной вероятностью. Из полученной новой вероятности и вероятностей новых символов, не использованных в объединении, формируется новый столбец в порядке убывания вероятностей, а две последние вновь объединяются. Это продолжается до тех пор, пока не останется одна вероятность, равная сумме вероятностей всех символов, встречающихся в файле.

Таблица 8.4. Кодирование методом Хаффмена

Таблица 8.5. Коды символов для кодового дерева на рис. 8.1

Процесс кодирования с использованием метода Хаффмена поясняется табл. 8.4. Для составления кода, соответствующего данному символу, необходимо проследить путь перехода знака по строкам и столбцам таблицы кода.

Более наглядно принцип действия метода Хаффмена можно представить В виде кодового дерева (рис. 8.1) на основе табл. 8.4. Из точки, соответствующей сумме всех вероятностей (в данном случае она равна 100), направляются две ветви. Ветви с большей вероятностью присваивается единица, с меньшей — нуль. Продолжая последовательно разветвлять дерево, доходим до вероятности каждого символа.

Рис. 8.1. Кодовое дерево для кода Хаффмена

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

Алгоритм LZW

Непосредственным предшественником алгоритма LZW явился алгоритм LZ78, опубликованный в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel-Ziv-Welch).

Алгоритм LZW построен вокруг так называемой таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины, равные 12 бит. Таблица обладает свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже содержится в словаре.

Алгоритм работы кодера LZW следующий:

Проинициализировать словарь односимвольными фразами, соответствующими символам входного алфавита;

Прочитать первый символ сообщения в текущую фразу *г;

Шаг алгоритма:

Прочитать очередной символ сообщения К:

Если КОНЕЦ_СООВЩЕНИЯ

Выдать ход »;

Иначе

Выдать ход w;

Добавить wK в словарь ;

Повторить Шаг алгоритма;

Конец Если;

Пример работы кодера LZW при преобразовании трехсимвольного алфавита приведен в табл. 8.6 и 8.7.

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

Таблица 8.6. Работа кодера LZW на примере трехсимвольного алфавита (а, б, в)

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

Таблица 8.7. Словарь, построенный кодером LZW, для примера из табл. 8.6

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

Алгоритм декодирования LZW описывается следующим образом:

КОД 8 Прочитать первый ход сообщения( );

ПредмдущийКОД = КОД;

Выдать символ К, у которого код(К) == КОД;

Последний символ = К;

Поиск по сайту: