Реферат: Коды без памяти. Коды Хаффмена. Коды с памятью

Недостатки метода Хаффмена

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

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

Еще один недостаток кодов Хаффмена - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код Хаффмена становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Наконец, код Хаффмена обеспечивает среднюю длину кода, совпадающую с энтропией, только в том случае, когда вероятности символов источника являются целыми отрицательными степенями двойки: 1/2 = 0,5; 1/4 = 0,25; 1/8 = 0,125; 1/16 = 0,0625 и т.д. На практике же такая ситуация встречается очень редко или может быть создана блокированием символов со всеми вытекающими отсюда последствиями.

Коды с памятью

Обычно рассматривают два типа кодов с памятью:

- блочные коды;

- коды с конечной памятью.

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

В качестве примера сожмем вектор данных X = (0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1), используя блочный код второго порядка.

Сначала разобьем вектор X на блоки длины 2: 01, 10, 10, 01, 11, 10, 01, 01.

Будем рассматривать эти блоки как элементы нового “гипералфавита” {01, 10, 11}. Чтобы определить, какой код назначить какому их символов этого нового алфавита, определим вектор частот появлений элементов дополнительного алфавита в последовательности блоков. Получим вектор частот (4, 3, 1), то есть наиболее часто встречающийся блок 01 появляется 4 раза, следующий по частоте встречаемости блок 10 - три раза и наименее часто встречающийся блок 11 - лишь один раз.

Оптимальный вектор Крафта для вектора частот ( 4, 3, 1 ) - это вектор (1, 2, 2). Таким образом, кодер для оптимального блочного кода второго порядка применительно к заданному вектору данных X определяется табл. 1.

Таблица 1

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

0, 10, 10, 0, 11, 10, 0, 0.

Объединяя эти кодовые слова вместе, имеем выходную последовательность кодера:

B(X) = ( 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0 ).

Можно проверить, что энтропия H(X) исходного вектора X равна 0.9887 бит/букву, а степень сжатия, получаемая в результате использования блочного кода R(X) = 12/16 = 0.75 бит на выборку данных, оказалась меньше нижней границы энтропии. Полученный результат, казалось бы, противоречит теореме Шеннона, утверждающей, что невозможно достичь средней длины кода, меньшей энтропии источника. Однако на самом деле это не так. Если внимательно посмотреть на вектор данных X , то можно заметить закономерность: за символом 0 чаще следует 1, то есть условная вероятность Р(1/0) существенно больше, чем просто Р(0). Следовательно, энтропию этого источника нужно считать как энтропию сложного сообщения, а она, как известно, всегда меньше, чем для источника простых сообщений.

Код с конечной памятью при кодировании вектора данных ( X₁ , X₂ , ..., X_n ) использует кодовую книгу, состоящую из нескольких различных кодов без памяти . Каждая выборка данных кодируется кодом без памяти из кодовой книги, определяемым значением некоторого числа предыдущих выборок данных.

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

Кодер с памятью при кодировании текущего символа учитывает значение предшествующего ему символа . Таким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA, DA и CA (иными словами, код обладает памятью в один символ источника) (табл. 2).

Таблица 2

Результат кодирования - вектор B(X) = (10111011111011) длиной в 11 бит искоростью сжатия R = 13/11=1,18 бита на символ данных, тогда как при кодировании равномерным трехразрядным кодом с R = 3 понадобилось бы 33 бита.

ЛИТЕРАТУРА

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.