Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


3.3.3. Алгоритм Лемпела-Зива

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

В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела-Зива разработан так, чтобы быть независимым от статистики источника. Следовательно, алгоритм Лемпела-Зива принадлежит классу универсальных алгоритмов кодировать источника. Этот алгоритм переменно-фиксированной длины, а кодирование выполняется так, как описано ниже.

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

Как пример рассмотрим бинарную последовательность

10101101001001110101000011001110101100011011.

Деление последовательности, как описано выше, производит следующие фразы:

1,0,10, 11,01,00. 100, 111,010, 1000,011,001, 110, 101, 10001, 1011.

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

Таблица 3.3.4. Словарь для алгоритма Лемпела-Зива

 

Расположение в словаре

Содержимое словаря

Кодовое слово

1

0001

1

00001

2

0010

0

00000

3

0011

10

00010

4

0100

11

00011

5

0101

01

00101

6

0110

00

00100

7

0111

100

00110

8

1000

111

01001

9

1001

010

01010

10

1010

1000

01110

11

1011

011

01011

12

1100

001

01101

13

1101

110

01000

14

1110

101

00111

15

1111

10001

10101

16

 

1011

11101

Ячейки словаря пронумерованы последовательно, начиная с 1 и далее, в данном случае до 16, что является числом фраз в последовательности. Различные фразы, соответствующие каждой ячейке, также перечислены, как показано в таблице. Кодовые слова конструируются путём соединения двух частей. Первая часть представляет собой номер ячейки словаря (в двоичной форме) предыдущей фразы, которая соответствует новой фразе, кроме последнего символа. Вторая часть — это новый символ, выданный источником. Он добавляется в конец к первой части, т.е. к номеру ячейки предыдущей фразы. Первоначальный номер ячейки 0000 используется, чтобы кодировать «пустую» фразу.

Декодер источника создает идентичную таблицу на приемном конце системы связи и соответственно декодирует полученную последовательность.

Можно заметить, что таблица закодировала 44 исходных бита в 16 кодовых слов по пять битов каждый, что привело к 80 кодированным битам. Следовательно, алгоритм вообще не обеспечил никакое сжатие данных. Однако неэффективность является следствием того, что последовательность, которую мы рассмотрели, очень коротка. По мере увеличения длины последовательности процедура кодирования становится более эффективной и приводит к сжатию последовательности на выходе источника.

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

Алгоритм Лемпела-Зива широко используется при сжатии компьютерных файлов. «Сжимающие» и «разжимающие» программы (утилиты) в операционной системе UNIX и многочисленные алгоритмы в операционной системе MS DOS являются воплощениями различных версий этого алгоритма.

 



<< ПредыдущаяОглавлениеСледующая >>