Преобразование Барроуза - Уилера

Как уже указывалось, преобразование Барроуза - Уилера предназначено

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

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

В оригинальной статье была предложена как одна из возможных реали­заций сжатия на основе BWT совокупность из трех алгоритмов:

■ преобразования Барроуза - Уилера;

■ преобразования Move-To-Front (известного в русскоязычной литературе как перемещение стопки книг);

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

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

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

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

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

Таким образом, мы пришли к первой и самой легкой из фаз преобразо­вания - к выделению из непрерывного потока блока данных.

Де-факто описывать BWT стало принято с помощью примера преобра­зования строки символов "абракадабра".

Далее нужно из полученного блока данных создать матрицу всех воз­можных его циклических перестановок. Первой строкой матрицы будет ис­ходная последовательность, второй строкой - она же, сдвинутая на один символ влево, и т. д. Таким образом, получим матрицу, изображенную на рис. 5.1.

абракадабра бракадабраа ракадабрааб акадабраабр кадабраабра адабраабрак дабраабрака абраабракад браабракада раабракадаб аабракадабр

Рис. 5.1. Множество циклических перестановок строки "абракадабра "

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

Рис. 5.2. Матрица циклических перестановок строки "абракадабра", отсортированная слева направо в соответствии с лексикографическим порядком символов ее строк

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

Теперь нам осталось сделать "всего" 3 вещи:

1) доказать, что преобразование обратимо;

2) показать, что оно не требует огромного количества ресурсов;

3) показать, что оно полезно для последующего сжатия.

Упражнение. Проделайте преобразование Барроуза - Уилера строки "карабас".

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

Возможно, Дэвид Уилер не опубликовал описание алгоритма в 1983 г. потому, что ему самому показалось странным, что можно восстановить на­чальную строку из столь сильно перемешанных между собой символов. Но так или иначе, это не фокус и обратное преобразование действительно воз­можно.

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

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

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

Рис. 5.3. Отсор­тированные символы исходной строки

Рис. 5.4. Первый и последний столбцы матрицы цикличес­ких перестановок

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

I 2 3 4 5 6 7 8 9 10

аа..... р

аб..... д

аб..... а

ад..... к

ак...... р

бр...... а

бр...... а

да..... а

ка...... а

ра...... б

Р^а....... ^б

Рис. 5.5. Первый, второй и последний столбцы матрицы

Таким образом, два столбца нам уже известны. Легко заметить, что отсор­тированные пары вместе с символами последнего столбца составляют тройки. Аналогично восстанавливается вся матрица. А на основании записанного зара­нее номера исходной строки в матрице - и сама исходная строка (рис. 5.6).

Рис. 5.6. Процесс определения всех столбцов матрицы

Упражнение. В результате преобразования Барроуза - Уилера получена стро­ка "тпрооппо". Номер исходной строки в матрице преобразований - 5 (считая с нуля). Восстановите исходную строку.

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

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

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

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

Из строки 0 мы получали строку 9, из первой - седьмую и т. п., (рис. 5.7).

Рис. 5.7. Способ получения первого столбца матрицы из последнего

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

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

Рис. 5.8. Получение вектора обратного преобразования

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

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

Затем нужно определить, какой символ заставил опуститься найденный символ "а" на вторую позицию среди равных. Искомый символ находится в последнем столбце шестой строки матрицы, изображенной на рис. 5.8. А поскольку Т[6] = 10, в преобразованной строке он находится в десятой позиции. Это символ "б". И т. д. (рис. 5.9).

6=^ 10 => Л=> 8=> 3=> 7=> 1=> 5=> 9=> 0=> 2
аб ракадабра

Рис. 5.9. Декодирование исходной строки при помощи вектора обратного преобразования

Упражнение. В результате преобразования Барроуза - Уилера получена стро­ка "тпрооппо". Номер исходной строки в матрице преобразований - 5 (считая с нуля). Постройте вектор обратного преобразования.

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

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

count - массив частот каждого символа алфавита во входном блоке; Т - вектор обратного преобразования, размер вектора равен л.

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

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]; }

После выполнения этих действий countf/] указывает на первую позицию символа с кодом 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 в сжатии данных

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

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

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

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

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

Частичное сортирующее преобразование

Некоторое время спустя после появления первых архиваторов, исполь­зующих преобразование Барроуза - Уилера, было опубликовано описание еще одного алгоритма, также основанного на сортировке блока данных [33, I]. Отличие от BWT заключается в том, что сортировка строк матрицы осу­ществляется не по всей длине строк, а только по некоторому фиксирован­ному количеству символов. В том случае, если у нескольких строк эти сим­волы одинаковы, выше в списке помещается строка, первый символ которой встретился во входном блоке раньше первых символов остальных рассмат­риваемых строк.

Можно сказать, что позиция первого символа строки во входном блоке участвует в сортировке. Число символов строки, участвующих в преобразо­вании, называется порядком сортирующего преобразования. Легко заме­тить, что в результате преобразования нулевого порядка, ST(0), получается исходная строка. В качестве примера выполним преобразования 1-го и 2-го порядка строки "абракадабра" (рис. 5.10).

Рис. 5.10. Частичные сортирующие преобразования 1-го и 2-го порядка

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

Упражнение. Выполните преобразование ST(3) строки "абракадабра".

Легко заметить, что различие между частичным сортирующим преобра­зованием и преобразованием Барроуза - Уилера можно увидеть только при сортировке устойчивых контекстов длиннее порядка преобразования ST. В методе BWT в этом случае продолжается процесс сравнения символов, а в ST- сравнение символов прекращается и выше располагается та строка, первый символ которой встретился во входном блоке раньше. Следователь­но, те данные, в которых встречаются длинные повторы, более эффективно сжимаются преобразованием Барроуза - Уилера. К примеру, типичные тек­стовые файлы на английском языке теряют в сжатии около 5% при выпол­нении сортировки по четырем символам.

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

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