Алгоритм Зива-Лемпеля
В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress, lha, pkzip и arj. Модификация алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз. Позднее появилась модификация алгоритма LZ78 – Lempel-Ziv Welsh (использует словарь для байтов для потоков октетов).
Суть алгоритма заключается в следующем:
Если в тексте встретится повторение строк символов, то повторные строки заменяются ссылками (указателями) на исходную строку. Ссылка имеет формат <префикс, расстояние, длина>. Префикс в этом случае равен 1. Поле расстояние идентифицирует слово в словаре строк. Если строки в словаре нет, генерируется код символ вида <префикс, символ>, где поле префикс =0, а поле символ соответствует текущему символу исходного текста. Отсюда видно, что префикс служит для разделения кодов указателя от кодов символ. Введение кодов символ, позволяет оптимизировать словарь и поднять эффективность сжатия. Главная алгоритмическая проблема здесь заключатся в оптимальном выборе строк, так как это предполагает значительный объем переборов.
Рассмотрим пример с исходной последовательностью U=0010001101 (без надежды получить реальное сжатие для столь ограниченного объема исходного материала).
Введем обозначения:
P[n] - фраза с номером n.
C - результат сжатия.
Разложение исходной последовательности бит на фразы представлено в таблице ниже.
| N фразы | Значение | Формула | Исходная последовательность U |
| - | P[0] | ||
| P[1]=P[0].0 | 0. 010001101 | ||
| P[2]=P[1].1 | 0.01.0001101 | ||
| P[3]=P[1].0 | 0. 01.00.01101 | ||
| P[4]=P[2].1 | 0. 01.00.011.01 | ||
| 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 |
Все формулы, содержащие P[0] вовсе не дают сжатия. Очевидно, что С длиннее U, но это получается для короткой исходной последовательности. В случае материала большего объема будет получено реальное сжатие исходной последовательности.
Дата добавления: 2016-03-22; просмотров: 1019;