Алгоритм
Зива-Лемпеля
Большинство
алгоритмов сжатия базируется на последовательной схеме сжатия Лемпеля-Зива
(Lempel-Ziv, 1977). Этот алгоритм используется, в частности, стандартной
процедурой UNIX Compress. Методики со статистическим моделированием могут
обеспечить лучшее сжатие, но они заметно медленнее. Но существует алгоритм,
который совмещает в себе лучшие из черт названных выше. Этот алгоритм не
предусматривает последовательной обработки входных данных, а обрабатывает текст
по-блочно. Здесь используется обратимое преобразование блока данных к виду,
который позволяет эффективно сжать данные с помощью простых алгоритмов.
Преобразование имеет целью сгруппировать символы так, чтобы вероятность
появления последовательностей идентичных символов значительно возросла. Такой
текст может быть легко сжат посредством локально-адаптивных алгоритмов в
сочетании с кодировкой Хафмана и арифметической кодировкой.
Последовательность
S, содержащая N символов ({S(0),+ S(N-1)}), подвергается N циклическим сдвигам
(вращениям), лексикографической сортировке, а последний символ при каждом
вращении извлекается. Из этих символов формируется строка L, где i-ый символ
является последним символом i-го вращения. Кроме строки L создается индекс I
исходной строки S в упорядоченном списке вращений. Существует эффективный
алгоритм восстановления исходной последовательности символов S на основе строки
L и индекса I. Процедура сортировки объединяет результаты вращений с идентичными
начальными символами. Предполагается, что символы в S соответствуют алфавиту,
содержащему K символов.
Для пояснения
работы алгоритма возьмем последовательность S= aca=6), алфавит X = {
1. Формируем
матрицу из N*N элементов, чьи строки представляют собой результаты циклического
сдвига (вращений) исходной последовательности S, отсортированных
лексикографически. По крайней мере одна из строк M содержит исходную
последовательность S. Пусть I является индексом строки S. В приведенном примере
индекс I=1, а матрица M имеет вид:
Номер строки |
|
0 |
aabrac |
1 |
abraca |
2 |
acaabr |
3 |
bracaa |
4 |
caabra |
5 |
racaab |
2. Пусть строка
L представляет собой последнюю колонку матрицы M с символами L[0],…,L[N-1]
(соответствуют M[0,N-1],…,M[N-1,N-1]). Формируем строку последних символов
вращений. Окончательный результат характеризуется (L,I). В данном примере L=aab
=1.
Процедура
декомпрессии использует L и I. Целью этой процедуры является получение исходной
последовательности из N символов (S).
1. Сначала
вычисляем первую колонку матрицы M (F). Это делается путем сортировки символов
строки L. Каждая колонка исходной матрицы M представляет собой перестановки
исходной последовательности S. Таким образом, первая колонка F и L являются
перестановками S. Так как строки в M упорядочены, размещение символов в F также
упорядочено. F=bcrP>
2.
Рассматриваем ряды матрицы M, которые начинаются с заданного символа ch. Строки
матрицы М упорядочены лексикографически, поэтому строки, начинающиеся с ch
упорядочены аналогичным образом. Определим матрицу Mкоторая получается из строк
матрицы M путем циклического сдвига на один символ вправо. Для каждого i=0,…,
N-1 и каждого j=0,…,N-1,
Mj] = m[i,(j-1)
mod N]
В рассмотренном
примере M и Mмеют вид:
Строка |
M |
MD> |
0 |
aabrac |
caabra |
1 |
abraca |
aabraс |
2 |
acaabr |
racaab |
3 |
bracaa |
abraca |
4 |
caabra |
acaabr |
5 |
racaab |
bracaa |
Подобно M
каждая строка Mвляется вращением S, и для каждой строки M существует
соответствующая строка Mолучена из M так, что строки Mпорядочены
лексикографически, начиная со второго символа. Таким образом, если мы
рассмотрим только те строки Mкоторые начинаются с заданного символа ch, они
должны следовать упорядоченным образом с учетом второго символа. Следовательно,
для любого заданного символа ch, строки M, которые начинаются с ch, появляются
в том же порядке что и в Mначинающиеся с ch. В нашем примере это видно на
примере строк, начинающихся с Строки racaca abrмеют номера 0, 1 и 2 в M и 1, 3,
4 в MP>
Используя F и
L, первые колонки M и Mы вычислим вектор Т, который указывает на соответствие
между строками двух матриц, с учетом того, что для каждого j = 0,…,N-1 строки j
Mоответствуют строкам T[j] M.
Если L[j]
является к-ым появлением ch в L, тогда T[j]=1, где F[i] является к-ым
появлением ch в F. Заметьте, что Т представляет соответствие один в один между
элементами F и элементами L, а F[T[j]] = L[j]. В нашем примере T равно: (4 0 5
1 2 3).
3. Теперь для
каждого i = 0,…, N-1 символы L[i] и F[i] являются соответственно последними и
первыми символами строки i матрицы M. Так как каждая строка является вращением
S, символ L[i] является циклическим предшественником символа F[i] в S. Из Т мы
имеем F[T[j]] = L[j]. Подставляя i =T[j], мы получаем символ L[T(j)], который
циклически предшествует символу L[j] в S.
Индекс I
указывает на строку М, где записана строка S. Таким образом, последний символ S
равен L[I]. Мы используем вектор T для получения предшественников каждого
символа: для каждого i = 0,…,N-1 S[N-1-i] = L[Ti[I]], где T0[x]
=x, а Ti+1[x] = T[Ti[x]. Эта процедура позволяет
восстановить первоначальную последовательность символов S (aca
Последовательность
Ti[I] для i =0,…,N-1 не обязательно является перестановкой чисел
0,…,N-1. Если исходная последовательность S является формой Zp для
некоторой подстановки Z и для некоторого p>1, тогда последовательность Ti[I]
для i = 0,…,N-1 будет также формой ZSUP для некоторой
субпоследовательности Z Таким образом, если S = can = p=2, последовательность
Ti[I] для i = 0,…,N-1 будет [2,4,0,2,4,0].
Описанный выше
алгоритм упорядочивает вращения исходной последовательности символов S и
формирует строку L, состоящую из последних символов вращений. Для того, чтобы
понять, почему такое упорядочение приводит к более эффективному сжатию,
рассмотрим воздействие на отдельную букву в обычном слове английского текста.
Возьмем в качестве
примера букву слове предположим, что исходная последовательность содержит много
таких слов. Когда список вращений упорядочен, все вращения, начинающиеся с
будут взаимно упорядочены. Один отрезок строки L будет содержать
непропорционально большое число перемешанных с другими символами, которые могут
предшествовать такими как пробел, P>
Аналогичные
аргументы могут быть использованы для всех символов всех слов, таким образом,
любая область строки L будет содержать большое число некоторых символов. В результате
вероятность того, что символ стретится в данной точке L, весьма велика, если ch
встречается вблизи этой точки L, и мала в противоположном случае. Это свойство
способствует эффективной работе локально адаптивных алгоритмов сжатия, где
кодируется относительное положение идентичных символов. В случае применения к
строке L, такой кодировщик будет выдавать малые числа, которые могут
способствовать эффективной работе последующего кодирования, например,
посредством алгоритма Хафмана.