Алгоритм Зива-Лемпеля
Семёнов Ю.А. (ГНЦ ИТЭФ), 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] - пустая строка. Символом . (точка) обозначается операция объединения (конкатенации).
Формируем пары строк, каждая из которых имеет вид (A . B). Каждая пара образует новую фразу и содержит идентификатор предыдущей фразы и бит, присоединяемый к этой фразе. Объединение всех этих пар представляет окончательный результат сжатия С. P[1]=P[0] . 0 дает (00 . 0), P[2]=P[1] . 0 дает (01 . 0) и т.д. Схема преобразования отражена в таблице ниже.
Формулы |
P[1]=P[0] . 0 |
P[2]=P[1] . 1 |
P[3]=P[1] . 0 |
P[4]=P[2] . 1 |
P[5]=P[1] . 1 |
Пары |
00 . 0=000 |
01 . 1=011 |
01 . 0=010 |
10 . 1=101 |
01 . 1=011 |
С |
000 . 011 . 010 . 101 . 011 = 000011010101011 |
||||
