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

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

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

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

Пример. Используя Zip–модификацию алгоритма Лемпеля-Зива, закодировать последовательность

abaababbbbbbbabbbba. (*)

Результат кодирования будем записывать в таблицу, содержащую три строки. В первой строке – адрес пакета данных, во второй – пакет данных в виде <адрес словаря, следующий знак данных>, в третьей – содержимое текущего пакета данных.

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

Сформируем первый пакет данных и добавим его в словарь. Первый символ кодируемой последовательности (*) – «а» запишем по первому адресу. Пакет данных будет иметь вид: <0,a>. При формировании текущего пакета данных не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, значение следующего знака данных равно «а», – символу, который необходимо записать в словарь.

Адрес: 1

Пакет данных: <0,a>

Содержимое: а.

Второй символ кодируемой последовательности (*) – «в» запишем по второму адресу. Пакет данных будет иметь вид: <0,в>. При формировании этого пакета данных также не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, а значение следующего знака данных равно «в», – символу, который необходимо записать в словарь.

Адрес: 2

Пакет данных: <0,в>

Содержимое: в.

Просматриваем далее входную последовательность ab aababbbbbbbabbbba. Будем отмечать в ней подчеркиванием уже закодированные символы. Следующий из незакодированных символов – «а» уже встречался в словаре, поэтому теперь в один пакет запишем объединение этого символа со следующим

Адрес: 3

Пакет данных: <1,а>

Содержимое: аа.

Запись <1,а> в пакете данных означает, что необходимо взять символ(ы) записанные по адресу 1 и добавить к ним символ «а». Далее будем аналогичным образом продолжать процесс кодирования, каждый раз просматривая динамически формируемый словарь справа налево, т.е. с последней записи к первой. Оформим процесс кодирования в таблицу.

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

Поиск по сайту: