Вопрос № 12

2.7. Код Лемпеля–Зива.

Методы кодирования источника, рассмотренные в 2.3 и 2.4, базируются на точном априорном знании вероятностей всех его сообщений. На практике, однако, нередки ситуации, когда статистика источника заранее неизвестна, и для преодоления априорной неопределенности приходится оценивать вероятности сообщений непосредственно в процессе кодирования. Подобный подход лежит в основе схем словарного кодирования, для знакомства с которыми обратимся к простейшей версии популярного алгоритма Лемпеля-Зива. Указанный алгоритм не требует предварительного знания статистики кодируемых данных и состоит в формировании словаря, фразами в котором являются блоки переменной длины с выхода источника. Каждая новая запись в словарь (новая фраза) определяет последовательность символов источника, отличающуюся от ранее внесенных туда только последним символом. Она состоит из адреса префикса (т.е. уже занесенной в словарь фразы, которая идентична новой за исключением последнего символа) и обновляющего бита источника, превращающего префикс в новую фразу. Данная пара чисел в двоичной форме образует кодовое слово, отвечающее фразе в словаре. На приемной стороне декодер источника создает идентичный словарь, используя поток кодированных символов, и, тем самым, восстанавливает последовательность сообщений.

Пример 2.7.1. Пусть с выхода дискретного источника снимается двоичный поток вида

10101100001001100111001101001111001110100111110011100001100111001100111000.

Требуется закодировать информационную последовательность двоичным кодом на основе алгоритма Лемпеля–Зива с использованием словаря из 16 фраз.

Два начальных адреса в словаре отводятся алфавиту используемого кода: для двоичного кода под первым адресом значится нуль, под вторым – единица (или наоборот при условии, что порядок согласован с декодирующей стороной). Начиная кодирование, кодер заносит по третьему адресу фразу 10, поскольку это первая двухсимвольная комбинация в потоке. Соответствующее ей кодовое слово состоит из двух частей: адрес префикса в словаре (в данном случае префикс 1 находится по адресу 2) и обновляющей буквы с выхода источника, превращающей префикс в комбинацию, еще не включенную в словарь, т.е. в нашем примере 0. В результате фразе 10 сопоставляется кодовое слово (2,0), содержащееся в словаре под третьим адресом.

Закодировав первые два бита потока (10) кодер ждет появления первой комбинации, отсутствующей пока в словаре. В нашем примере таковой оказывается трехбитовая комбинация 101, следующая за началом 10. Эта фраза состоит из префикса 10, имеющегося в словаре по адресу 3, и обновляющего бита 1. Таким образом, кодовое слово имеет вид (3,1) и заносится в словарь под четвертым адресом. Последующие этапы процедуры аналогичны рассмотренным и иллюстрируются табл. 2.4. В последнем ее столбце кодовые слова представлены в двоичной форме с резервированием первых 4 бит для адреса префикса и 5-го бита для передачи обновляющего бита источника. В результате применения алгоритма Лемпеля–Зива исходный информационный поток из 74-х бит источника кодируется в последовательность из 70 двоичных символов вида

00100 00111 00110 00010 01011 01111 10000 10001 10100 10101 10110 01101 11011 11010.

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

Для понимания процедуры декодирования достаточно рассмотреть пример 2.7.1 в обратном порядке, т.е. начав с потока кодовых символов. Обратим внимание на то, что обсуждаемый код Лемпеля-Зива – равномерный и проблема опознавания начала слова, таким образом, не стоит. В нашем примере все слова содержат 5 двоичных символов. Декодер, приняв очередное кодовое слово, разбивает его на две части – префикс (4 бита в нашем примере), и обновляющий бит. Префикс определяет адрес уже содержащейся в словаре фразы, которая вместе с новым символом образует очередную запись, заносимую в первую свободную строку. Так, приняв первое слово 00100, декодер устанавливает, что фраза, хранящаяся по адресу 2, состоит только из одного символа 1, что соответствует тривиальной записи буквы алфавита источника. Вместе с дополнительным символом 0 формируется новая фраза – 10, заносимая в словарь в третью строку. Аналогичные действия выполняются и для последующих кодовых слов. Одновременно каждая новая фраза поступает на выход декодера, формируя поток декодированных информационных бит. Таким образом, при кодировании заполнение словаря происходит «слева направо», т.е. от фразы к кодовому слову, тогда как при декодировании словарь заполняется в обратном порядке (от кодового слова к фразе).

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

Алгоритм Лемпеля-Зива и родственные ему имеют множество модификаций и огромный диапазон приложений. Достаточно сказать, что они лежат в основе всех методов архивирования компьютерных файлов.