Теория информации    

3.      Идеи построения алгоритма сжатия Лемпеля-Зива

 

 

 

 

Существует большое количество модификаций алгоритма Лемпеля-Зива [1, 3], все модификации этого алгоритма основаны на принципе динамических словарей. Перечислим основные идеи, на которых базируется алгоритм Лемпеля-Зива.
1. Каждая очередная закодированная последовательность символов добавляется к раннее закодированным символам таким образом, что вместе с ними она образует разложение всей принятой и переданной информации на несовпадающие между собой фразы. Такое разложение хранится в памяти и используется в дальнейшем в качестве словаря.
2. Кодирование осуществляется при помощи указателей на фразы из уже сформированного словаря фраз. Кодирование является динамической процедурой, ориентированной на блоки. Сам процесс кодирования может быть дополнен скользящими окнами, содержащими текущий словарь фраз, и Look-ahead буфером.

3.1. Zip–модификация алгоритма Лемпеля-Зива

Согласно [3] процесс кодирования начинается с пустого словаря, так что первые элементы являются позициями, которые не ссылаются на более ранние позиции. В словаре рекуррентно формируется выполняемая последовательность адресов. Каждому адресу соответствует последовательность из элементов алфавита. Закодированные данные хранятся в виде пакетов со следующей структурой:

<ссылка на адрес словаря, следующий знак данных>.

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

abaababbbbbbbabbbba. (*)

Результат кодирования будем записывать в таблицу, содержащую три строки. В первой строке – адрес пакета данных, во второй – пакет данных в виде <адрес словаря, следующий знак данных> , в третьей – содержимое текущего пакета данных
На начальном этапе работы алгоритма динамически формируемый словарь пуст. Пока словарь пуст, будем просматривать кодируемую фразу посимвольно и кодировать отдельные символы, по мере заполнения словаря будем пытаться кодировать в один пакет данных несколько подряд идущих символов.
Сформируем первый пакет данных и добавим его в словарь. Первый символ кодируемой последовательности (*) – «а» запишем по первому адресу. Пакет данных будет иметь вид: <0,a>. При формировании текущего пакета данных не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, значение следующего знака данных равно «а», – символу, который необходимо записать в словарь.
Адрес: 1
Пакет данных: <0,a>
Содержимое: а.
Второй символ кодируемой последовательности (*) – «в» запишем по второму адресу. Пакет данных будет иметь вид: <0,в>. При формировании этого пакета данных также не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, а значение следующего знака данных равно «в», – символу, который необходимо записать в словарь.
Адрес: 2
Пакет данных: <0,в>
Содержимое: в.
Просматриваем далее входную последовательность abaababbbbbbbabbbba. Будем отмечать в ней подчеркиванием уже закодированные символы. Следующий из незакодированных символов – «а» уже встречался в словаре, поэтому теперь в один пакет запишем объединение этого символа со следующим
Адрес: 3
Пакет данных: <1,а>
Содержимое: аа.
Запись <1,а> в пакете данных означает, что необходимо взять символ(ы) записанные по адресу 1 и добавить к ним символ «а». Далее будем аналогичным образом продолжать процесс кодирования, каждый раз просматривая динамически формируемый словарь справа налево, т.е. с последней записи к первой. Оформим процесс кодирования в таблицу.

Обратите внимание, что последний пакет данных, записанный по адресу 9, не содержит знака данных

3.2. LZW-модификация алгоритма Лемпеля-Зива

Эта модификация отличается от рассмотренной ранее Zip–модификации структурой пакета данных. Концепция адреса не используется, наоборот имеются ссылки предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Пакет данных формируется из трех значений: <А, В, С>, первые два из которых указывают на уже закодированную подпоследовательность данных, следующим образом: число А указывает на сколько знаков необходимо отступить назад, чтобы найти начало нужной подпоследовательности, В – длина подпоследовательности которую необходимо считать, С – следующий знак.
Пример. Используя LZW–модификацию алгоритма Лемпеля-Зива, закодировать последовательность

abaababbbbbbbabbbba. (**)

Для кодирования алгоритмом Лемпеля-Зива установлено, что [1, стр. 83]:
-очень эффективно кодируются повторяющиеся символы и часто появляющиеся цепочки символов;
-редко повторяющиеся символы и последовательности символов с течением времени удаляются из словаря фраз;
-кодирование начальных фраз затрачивается относительно большое количество бит;
-методы теории информации позволяют доказать, что кодирование методом Лемпеля-Зива асимптотически оптимально. Это означает, что для очень длинного текста избыточность исчезает, то есть среднее число бит, необходимое для кодирования текста стремиться к энтропии текста;
-практическая степень сжатия для длинных текстов составляет 50-60%.