Алгоритмы сжатия данных

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

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

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

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

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

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

Формируем пары строк, каждая из которых имеет вид (A.B). Каждая пара образует новую фразу и содержит идентификатор предыдущей фразы и бит, присоединяемый к этой фразе. Объединение всех этих пар представляет окончательный результат сжатия С. P[1] = P[0].0 дает (00.0), P[2] = P[1].0 дает (01.0) и т.д. Схема преобразования отражена в таблице ниже.

Все формулы, содержащие P[0], вовсе не дают сжатия. Очевидно, что С длиннее U, но это получается для короткой исходной последовательности. В случае материала большего объема будет получено реальное сжатие исходной последовательности. Приведенный пример позволяет понять, что не всякая операция архивации приводит к реальному сокращению объема данных.

3.2. Статический алгоритм Хаффмана

Статический алгоритм Хафмана можно считать классическим (см. также Р. Галлагер. Теория информации и надежная связь. "Советское радио", Москва, 1974). Определение "статический" в данном случае относится к используемым словарям. См. также http://www.ics.ics.uci.edu/~dan/pubs/DataCompression.html) (Debra A. Lelewer и Daniel S. hirschberg). Алгоритм Хаффмана предполагает, что вероятности появления в исходном массиве разных кодовых последовательностей (символов) принципиально неравны.

Пусть сообщения $$m(1), …, m(n)$$ имеют вероятности $$P(m(1)), …, P(m(n))$$ и пусть для определенности они упорядочены так, что $$P(m(1)) \ge P(m(2)) \ge … \ge P(m(N))$$. Пусть $$x_1, …, x_n$$ - совокупность двоичных кодов, и пусть $$l_1, l_2, …, l_N$$ — длины этих кодов. Задачей алгоритма является установление соответствия между $$m(i)$$ и $$x_j$$. Можно показать, что для любого ансамбля сообщений с полным числом более 2 существует двоичный код, в котором два наименее вероятных кода $$x_N$$ и $$x_{N-1}$$ имеют одну и ту же длину и отличаются лишь последним символом: $$x_N$$ имеет последний бит 1, а $$x_{N-1}$$ - 0. Редуцированный ансамбль будет иметь свои два наименее вероятные сообщения сгруппированными вместе. После этого можно получить новый редуцированный ансамбль, и так далее. Процедура может быть продолжена до тех пор, пока в очередном ансамбле не останется только два сообщения. Процедура реализации алгоритма сводится к следующему (см. рис 3.1). Сначала группируются два наименее вероятных сообщения, предпоследнему сообщению ставится в соответствие код с младшим битом, равным нулю, а последнему – код с единичным младшим битом (на рисунке $$m(4)$$ и $$m(5)$$ ). Вероятности этих двух сообщений складываются, после чего ищутся два наименее вероятные сообщения во вновь полученном ансамбле ( $$m(3)$$ и $$m'(4)$$ ; $$p(m'(4)) = p(m(4)) + p(m(5))$$ ).

На следующем шаге наименее вероятными сообщениями окажутся $$m(1)$$ и $$m(2)$$. Кодовые слова на полученном дереве считываются справа налево. Алгоритм выдает оптимальный код (минимальная избыточность).

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

Возможно применение стандартных алфавитов (кодовых таблиц) для пересылки английских, русских, французских и т.п. текстов, программных текстов на С++, Паскале и т.д. Кодирование при этом не будет оптимальным, но исключается статистическая обработка пересылаемых фрагментов и отпадает необходимость пересылки кодовых таблиц (алфавитов). Следует заметить, что и в случае алгоритма Хаффмана эффективность сжатия зависит от характера сжимаемого материала. Например, при попытке сжать уже архивированный файл с большой вероятностью можно получить файл большего размера.

3.3. Сжатие данных с использованием преобразования Барроуза-Вилера

Майкл Барроуз и Давид Вилер (Burrows-Wheeler) в 1994 году предложили свой алгоритм преобразования ( BWT ). Этот алгоритм работает с блоками данных и обеспечивает эффективное сжатие без потери информации. В результате преобразования блок данных имеет ту же длину, но другой порядок расположения символов. Алгоритм тем эффективнее, чем больший блок данных преобразуется (например, 256-512 Кбайт или более).

Последовательность S, содержащая N символов ( {S(0), …, S(N-1)} ), подвергается N циклическим сдвигам (вращениям), лексикографической сортировке, а последний символ при каждом вращении извлекается. Из этих символов формируется строка L, где i -й символ является последним символом i -го вращения. Кроме строки L создается индекс I исходной строки S в упорядоченном списке вращений. Существует эффективный алгоритм восстановления исходной последовательности символов S на основе строки L и индекса I. Процедура сортировки объединяет результаты вращений с идентичными начальными символами. Предполагается, что символы в S соответствуют алфавиту, содержащему K символов. Под лексикографической сортировкой подразумевается упорядочение числовых кодов, которые получаются при подстановке ASCII-кодов вместо букв.

Для пояснения работы алгоритма возьмем последовательность S = 'abraca' (N = 6), алфавит X = {'a', 'b', 'c', 'r'}.

Процедура декомпрессии использует L и I. Целью этой процедуры является получение исходной последовательности из N символов (S).

1. Сначала вычисляем первую колонку матрицы M (F). Это делается путем сортировки символов строки L. Каждая колонка исходной матрицы M представляет собой перестановки исходной последовательности S. Таким образом, первая колонка F и L являются перестановками S. Так как строки в M упорядочены, размещение символов в F также упорядочено. F = 'aabcr'.

2. Рассматриваем ряды матрицы M, которые начинаются с заданного символа ch. Строки матрицы М упорядочены лексикографически, поэтому строки, начинающиеся с ch, упорядочены аналогичным образом. Определим матрицу M', которая получается из строк матрицы M путем циклического сдвига на один символ вправо. Для каждого i = 0, …, N-1 и каждого j = 0, …, N-1,

M'[i,j] = m[i, (j-1) mod N]

В рассмотренном примере M и M' имеют вид

Подобно M, каждая строка M' является вращением S, и для каждой строки M существует соответствующая строка M'. M' получена из M так, что строки M' упорядочены лексикографически, начиная со второго символа. Таким образом, если мы рассмотрим только те строки M', которые начинаются с заданного символа ch, они должны следовать упорядоченным образом с учетом второго символа. Следовательно, для любого заданного символа ch строки M, которые начинаются с ch, появляются в том же порядке, что и в M', начинающиеся с ch. В нашем примере это видно на примере строк, начинающихся с 'a'. Строки 'aabrac', 'abraca' и 'acaabr' имеют номера 0, 1 и 2 в M и 1, 3, 4 в M'.

Используя 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 ('abraca').

Последовательность Ti[I] для i = 0, …, N-1 не обязательно является перестановкой чисел 0, …, N-1. Если исходная последовательность S является формой Zp для некоторой подстановки Z и для некоторого p>1, тогда последовательность Ti[I] для i = 0, …, N-1 будет также формой Z'p для некоторой субпоследовательности Z'. Таким образом, если S = 'cancan', Z = 'can' и p = 2, то последовательность Ti[I] для i = 0, …, N-1 будет [2, 4, 0, 2, 4, 0].

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

Возьмем в качестве примера букву "t" в слове "the" и предположим, что исходная последовательность содержит много таких слов. Когда список вращений упорядочен, все вращения, начинающиеся с "he", будут взаимно упорядочены. Один отрезок строки L будет содержать непропорционально большое число "t", перемешанных с другими символами, которые могут предшествовать "he", такими как пробел, "s", "T" и "S".

Аналогичные аргументы могут быть использованы для всех символов всех слов, таким образом, любая область строки L будет содержать большое число некоторых символов. В результате вероятность того, что символ "ch" встретится в данной точке L, весьма велика, если ch встречается вблизи этой точки L, и мала в противоположном случае. Это свойство способствует эффективной работе локально адаптивных алгоритмов сжатия, где кодируется относительное положение идентичных символов. В случае применения к строке L такой кодировщик будет выдавать малые числа, которые могут способствовать эффективной работе последующего кодирования, например, посредством алгоритма Хаффмана.