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 являются воплощениями различных версий этого алгоритма.