Обзор алгоритмов сжатия без потерь

BWT-преобразование и компрессор

Идея метода

BWT-преобразование (Burrows-Wheeler Transform) – техника для сжатия информации (в особенности текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых, даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BWT преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

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

Прежде всего, следует отметить одну из его особенностей. BWT оперирует сразу целым блоком данных. То есть, ему заранее известны сразу все элементы входного потока или, по крайней мере, достаточно большого блока. Это делает затруднительным использование алгоритма в тех областях применения, где требуется сжатие данных “на лету”, символ за символом. В этом отношении BWT даже более требователен, чем методы семейства LZ, использующие для сжатия скользящее окно.

Следует отметить, что возможна реализация сжатия данных на основе BWT, обрабатывающая данные последовательно по символам, а не по блокам. Но скоростные характеристики программ, использующих такую реализацию, будут очень далеки от совершенства.

Первая фаза преобразования – выделение из непрерывного потока блока данных. Далее, нужно из полученного блока данных создать матрицу всех возможных его циклических перестановок. Первой строкой матрицы будет исходная последовательность, второй строкой – она же, сдвинутая циклически на один символ влево и т.д. Рассмотрим преобразование на примере строки "абракадабра". Таким образом, получим следующую матрицу:

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

Теперь остался последний шаг – выписать символы последнего столбца и запомнить номер исходной строки среди отсортированных. В нашем примере "рдакраааабб", 2 – это результат полученный в результате преобразования Барроуза-Уилера.

Теперь осталось сделать следующее:

1. Доказать, что преобразование обратимо.
2. Показать, что оно не требует огромного количества ресурсов.
3. Показать, что оно полезно для последующего сжатия.

Доказательство обратимости преобразования Барроуза-Уилера

Пусть нам известны только результат преобразования, т. е. последний столбец матрицы, и номер исходной строки. Рассмотрим процесс восстановления исходной матрицы. Для этого отсортируем все символы последнего столбца.

Нам известно, что строки матрицы были отсортированы по порядку, начиная с первого символа. Поэтому, очевидно, в результате такой сортировки мы получили первый столбец исходной матрицы.

Поскольку последний столбец по условию задачи нам известен, добавим его в полученную матрицу.

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

Легко заметить, что отсортированные пары вместе с символами последнего столбца составляют тройки. Аналогично восстанавливается вся матрица. А на основании записанного ранее номера исходной строки в матрице – и сама исходная строка.

Вектор обратного преобразования

После того, как удалось наглядно показать принципиальную возможность обратного преобразования, пришло время признаться, что на самом деле нет необходимости воспроизводить посимвольно все строки матрицы по одному символу. Обратите внимание, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца, получалась строка, в которой этот символ находится на первой позиции. Из строки 0 получается строка 9, из 1 - 7 и т.д.:

Для получения вектора обратного преобразования, определим порядок получения символов первого столбца из символов последнего. То есть отсортировать матрицу по номерам новых строк:

Полученные значения номеров строк T = {2, 5, 6, 7, 8, 9, 10, 1, 3, 0, 4} и есть искомый вектор, содержащий номера позиций символов, упорядоченных в соответствии с положением в алфавите, в строке, которую нам надо декодировать.

Теперь получить исходную строку совсем просто. Первым делом возьмем элемент вектора обратного преобразования, соответствующий номеру исходной строки в матрице циклических перестановок, T[2] = 6. Иначе говоря, в качестве первого символа в исходной строке следует взять шестой символ из строки "рдакраааабб". Это символ 'а'. Затем нужно определить, какой символ заставил опуститься найденный символ 'а' на вторую позицию среди равных. Искомый символ находится в последнем столбце шестой строки матрицы. А поскольку T[6]=10, в преобразованной строке он находится в десятой позиции. Это символ 'б'. И т. д.

Реализация обратного преобразования

Проделаем тоже самое при помощи простейшей программы. Введем следующие обозначения:
n – количество символов в блоке из входного потока;
N – количество символов в алфавите;
pos – номер исходной строки в матрице перестановок;
in – входной поток;
count – частоты каждого символа алфавита во входном потоке;
T – вектор обратного преобразования, размер вектора равен n.

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

for( i=0; i<N; i++) count[i]=0;
for( i=0; i<n; i++) count[in[i]]++;
sum = 0;
for( i=0; i<n; i++) {
  sum += count[i];
  count[i] = sum - count[i];
}

Теперь count[i] указывает на первую позицию символа с кодом i в первом столбце матрицы.

Следующий шаг – создание вектора обратного преобразования.

for( i=0; i<n; i++) T[count[in[i]]++]]=i;

Далее, при помощи полученного вектора восстановим исходный текст.

  for( i=0; i<n; i++) {
  putc( in[pos], output );
  pos = T[pos];
}

Использование BWT в сжатии данных

После того, как выяснилось, что наши действия вполне обратимы, и данные мы не исказим, можно перейти к вопросу рассмотрения полезности преобразования. Главная задача преобразования Барроуза-Уилера заключается в том, чтобы переставить символы таким образом, чтобы их можно было легко сжать.

Для понимания этого процесса достаточно представить поток данных состоящим из набора некоторых стабильных сочетаний символов. Сочетание символов, позволяющее предсказать некоторый неизвестный символ, называется контекстом. Например, если нам известна последовательность символов "реобразование", то скорее всего ей предшествует символ "п". Назовем устойчивым (стабильным) такой контекст, для которого распределение частот символов, непосредственно примыкающих к нему слева и справа, меняется незначительно в пределах блока.

Если нам потребуется подвергнуть преобразованию текст данной главы, можно с уверенностью сказать, что строки, начинающиеся с символов "реобразование", будут располагаться рядом в отсортированной матрице. И в соответствующих этим строкам позициях последнего столбца матрицы будет находится символ "п".

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

Преобразование Шиндлера

Следует отметить еще одно преобразование, основанное на сортировке блока данных – преобразование Шиндлера (ST). Отличие от BWT заключается в том, что строки матрицы перестановок упорядочиваются не по всей длине, а только по указанному количеству первых символов. Число таких символов называется порядком преобразования Шиндлера. В случае, если эти символы одинаковы у двух или более строк, они упорядочиваются в соответствии с номером позиции, в которой эти строки встречаются в исходной последовательности.

Справедливости ради надо отметить, что ST является не разновидностью преобразования Барроуза-Уилера, а скорее его обобщением. Можно сказать, что BWT – это преобразование Шиндлера порядка, равного размеру блока.

Методы, используемые совместно с BWT

Как уже было сказано, само по себе преобразование Барроуза-Уилера не сжимает. Эту работу проделывают другие методы, позволяющие толково распорядиться теми свойствами, которыми обладают преобразованные данные.

Среди таких методов можно отметить следующие:

• кодирование длин повторов (RLE);
• метод перемещения стопки книг (MTF);
• кодирование расстояний (DC);
• метод Хаффмана;
• арифметическое кодирование.

Последовательность применения методов, используемых совместно с BWT:

Эффективность

Можно отметить характерные особенности архиваторов, использующих описанное преобразование, по сравнению с другими. Скорость сжатия – на уровне архиваторов, применяющих словарные методы, например, LZ77. Декомпрессия, как правило в 3-4 раза быстрее сжатия. Степень сжатия сильно зависит от типа данных.

Наиболее эффективно применение BWT-архиваторов для текстов и любых данных со стабильными контекстами. Расходы памяти в режиме максимального сжатия довольно близки у всех современных архиваторов. По расходу памяти при декодировании архиваторы на основе BWT занимают промежуточное положение.