Телекоммуникационные технологии. Том 1



         

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


Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru

В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress , lha , pkzip и arj . Модификация алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз.

Суть алгоритма заключается в следующем:

Если в тексте встретится повторение строк символов, то повторные строки заменяются ссылками (указателями) на исходную строку. Ссылка имеет формат <префикс, расстояние, длина>. Префикс в этом случае равен 1. Поле расстояние идентифицирует слово в словаре строк. Если строки в словаре нет, генерируется код символ вида <префикс, символ>, где поле префикс =0, а поле символ соответствует текущему символу исходного текста. Отсюда видно, что префикс служит для разделения кодов указателя от кодов символ . Введение кодов символ, позволяет оптимизировать словарь и поднять эффективность сжатия. Главная алгоритмическая проблема здесь заключатся в оптимальном выборе строк, так как это предполагает значительный объем переборов.

Рассмотрим пример с исходной последовательностью (см. также )

U =0010001101 (без надежды получить реальное сжатие для столь ограниченного объема исходного материала).

Введем обозначения:

P[n] - фраза с номером n .

C - результат сжатия.

Разложение исходной последовательности бит на фразы представлено в таблице ниже.

N фразы

Значение

Формула

Исходная последовательность U

0

-

P[0]

0010001101

1

0

P[1]=P[0] . 0

0 . 010001101

2

01

P[2]=P[1] . 1

0 . 01 . 0001101

3

010

P[3]=P[1] . 0

0 . 01 . 00 . 01101

4

00

P[4]=P[2] . 1

0 . 01 . 00 . 011 . 01

5

011

P[5]=P[1] . 1

0 . 01 . 00 . 011 . 01

P[0] - пустая строка. Символом . (точка) обозначается операция объединения (конкатенации).




Содержание  Назад  Вперед