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

Ключевые слова и синонимы

Сжатие данных при помощи блочной сортировки

Постановка задачи

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

До публикации преобразования Барроуза-Уилера в области сжатия данных без потерь доминировали два подхода (см. исчерпывающий обзор в работах [1, 15]). Первый подход был предложен в революционных работах Шеннона и Хаффмана и основан на идее использования более коротких кодовых слов для самых часто встречающихся символов. Идея этого подхода была основана на технике Хаффмана и алгоритме арифметического кодирования Arithmetic Coding, а в более поздний период – и на семействе алгоритмов сжатия PPM (Prediction by Partial Matching, прогнозирование по частичному совпадению). Второй подход был предложен в работах Лемпеля и Зива и основан на идее адаптивного построения словаря и представления входной строки в виде конкатенации словарных слов. Лучшие известные алгоритмы сжатия, основанные на этом подходе, составляют так называемое семейство ZIP; они давно уже являются стандартом и доступны практически на всех вычислительных платформах (в их числе gzip, zip, winzip и многие другие).

Преобразование Барроуза-Уилера воплощает совершенно иной подход к сжатию данных без потерь,основанный на идее преобразования входных данных, чтобы их сжатие стало проще. По словам авторов, «(эта) техника [..] заключается в применении обратимого преобразования к текстовому блоку, чтобы сделать избыточность входных данных более доступной для обработки простыми схемами кодирования» [3, раздел 7]. Эта техника не только позволила разработать самые современные алгоритмы сжатия, но и ввела понятие сжатых индексов [14] и была успешно расширена для сжатия (и индексирования) структурированных данных – таких как XML-файлы [ ] и таблицы [16].

Основные результаты

Нотация

Пусть s – строка длины n, состоящая из символов алфавита £. Для i = 0, ... , n-1 обозначим за[i] i-й символ строки s, а за s[i, n-1] – суффикс строки s, начинающийся с позиции i (т.е. начинающийся с символа s[i]). Если даны две строки, s и t, выражение s -< t будет обозначать, что s лексикографически предшествует t.

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

В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов см. рис. 1):

1. добавить в концу строки s специальный символ $, который меньше любого другого символа в S;

2. сформировать концептуальную матрицу M, строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке;

3. построить преобразованные текст J = bwt(s), взяв последний столбец матрицы M.

Заметим, что каждый столбец матрицы M – и, следовательно, преобразованный текст s – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы M, состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss.

mississippi$ $ mississipp i ississippi$m i $mississip P ssissippi$mi i ppi$missis s sissippi$mis i ssippi$mis s issippi$miss i ssissippi$ m ssippi$missi m —^ ississippi $ sippi$missis P i$mississi P ippi$mississ P pi$mississ i ppi$mississi s ippi$missi s pi$mississip s issippi$mi s i$mississipp s sippi$miss i $mississippi s sissippi$m i

Рисунок 1

Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это s = bwt(s) = ipssm$pissii

Хотя из определения это не очевидно, преобразование bwt является обратимым, и оба преобразования (bwt и его обращение) могут быть выполнены за оптимальное время O(n). Ради лучшего согласования с более современной литературой следующая нотация и техники доказательства будут несколько отличаться от изложенных в работе [3].

Определение 1. Для 1 < i < n обозначим за s[ki, n-1] суффикс строки s, являющейся префиксом строки i матрицы M, и определим ^(i) как индекс строки, которой предшествует префикс s[ki + 1, n - 1].

Например, на рис. 1 это будет "^(2) = 7, поскольку строка 2 матрицы M имеет префикс ippi, а строка 7 – ppi. Отметим, что ^(i) не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s.1

Лемма 1. Для i = 1, ... , n имеет место F[i] = s[W(i)].

Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является s[ki + 1, n - 1], является s[ki]. Из этого, согласно определению 1, следует s[&(i)] = s[ki] = F[i], что и требовалось доказать. □

Лемма 2. Если 1 < i < j < n и F[i] = F[j], то

Доказательство. Пусть s[ki, n - 1] (соответственно, s[kj, n - 1]) обозначает суффикс s, являющийся перфиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что s[ki, n - 1] -< s[kj, n - 1]. Из гипотезы F[i] = F[j] следует, что s[ki] = s[kj], поскольку должно иметь место s[ki + 1, n - 1] -< s[kj + 1, n - 1]. Из этого следует утверждение леммы, поскольку по построению ^(i) (&(j), соответственно) является лексикографической позицией строки, префиксом которой является s[ki + 1, n - 1] (s[kj + 1, n - 1], соответственно). □

Лемма 3. Для любого символа c 2 X1 верно: если F[j] _0 £-f/i-е вхождением c в F, то s[4^(j)] является l-м вхождением c в s.

Доказательство. Возьмем индекс h, такой, что h < j и F[h] = F[j] = c (случай с h > j является симметричным). Из леммы 2 следует, что <^(fc) < Ф()), а из леммы 1 – что s[W(h)] = s[W(j)] = c. Следовательно, количество символов c, предшествующих F[j] в F, совпадает с количеством символов c, предшествующих s[^(j)] в s (аналогичная ситуация имеет место для последущих символов), из чего следует справедливость формулировки леммы. □

На рис. 1 имет место Ф(2) = 7, и F[2] и s[7] занимают вторую позицию в соответствующих строках. Это свойство обычно формулируется так: соответствующим символы имеют один и тот же относительный порядок в строках F и s.

Лемма 4. Для любого i значение может быть вычислено из s = bwt(s).

Доказательство. Получить F можно в результате простой алфавитной сортировки символов s. Затем вычислим ^(i) следующим образом: (1) положим с = F[i]; (2) вычислим £, такое, что F[i] является £-м вхождением c в F; (3) возвратим индекс l-го вхождения cms. □

Вернемся к рис. 1. Для вычисления ^(10) достаточно положить c = F[10] = s и заметить, что F[10] является вторым вхождением s в F. Тогда достаточно локализовать индекс j второго s в s, в данном случае это j = 4. Следовательно, ^(10) = 4; префиксом строки 10 является sissippi, а строки 4 –issippi.

Теорема 5. Исходную строку можно восстановить из bwt(s).

Доказательство. Из леммы 4 следует, что столбец F и отображение 4> могут быть получены из bwt(s). Обозначим за j0 индекс специального символа $ в строке s. По построению строка j0 матрицы bwt имеет префикс s[0, n - 1], из чего следует s[0] = F[j0]. Пусть j1 = ^(/o). Согласно определению 1, префиксом строки j1 является s[1, n - 1], следовательно, s[1] = F[j1]. Продолжая аналогичные рассуждения, по индукции получаем j0)] для i = 1, ..., n - 1. □

1 В [3] вместо Ф авторы используют карту, в сущности, являющуюся инверсией 9. Использование 9 было предложено в литературе, посвященной сжатым индексам, где 9 и его обращение играют важную роль (см. [14]).

Алгоритмические вопросы

Важное свойство bwt заключается в том, что и прямая, и обратная версия преобразования позволяют разрабатывать эффективные алгоритмы, исключительно простые и элегантные.

Рисунок 2

Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение (?, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива [1, |27|], который изначально содержит в позиции count [i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения j0

Теорема 6. Пусть s[1, n] – строка над алфавитом S константного размера. Строка s = bwt(s) может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.

Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) ) бит рабочего пространства при помощи, например, алгоритма из [ ]. Суффиксный массив представляет собой строку целых чисел sa[1, n], такую, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы M является уникальный суффикс s, за которым идет специальным символ $, суффиксный массив обеспечивает упорядочение строк в M. Следовательно, bwt(s) можно вычислить из sa за линейное время при помощи процедуры sa2bwt на рис. 2. □

Теорема 7. Пусть s[1, n] – строка над алфавитом S константного размера. При наличии bwt(s) строка s может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.

Доказательство. Алгоритм вычисления s практически дословно воспроизводить процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения 4> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа c 2 E счетчик count[c] выдает индекс первой строки матрицы M, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс l-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi [h] значение i = Ф(И). После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5.

Очевидно, что выполнение процедур bwt2psi и psi2text занимает время O(n). Объем рабочего пространства зависит главным образом от стоимости хранения массива psi, который занимает O(n log n) бит. □

Алгоритм сжатия Барроуза-Уилера

Использование процедуры bwt для сжатия данных можно обосновать следующим образом. Рассмотрим строку w, которая k раз встречается внутри строки s. В bwt-матрице s будет k последовательных строк, префиксом которых является w – скажем, строки say rw + 1, rw + 2, ... , rw + k. Следовательно, позиции rw + 1, ... , rw + k в J = bwt(s) будут содержать в точности те символы, коорые непосредственно предшествуют w в s. Если в строке s некоторые шаблоны встречаются чаще других, то для многих подстрок w соответствующие позиции rw + 1, ... : : , rw + k строки s будут содержать только несколько различающихся символов. Например, если s – текст на английском языке, а w – строка «his», соответствующая часть J, скорее всего, будет содержать множество букв «t» и пустых символов и совсем немного других символов. Поскольку J является перестановкой s, она обычно оказывается локально гомогенной в том смысле, что ее «короткие» подстроки обычно содержат только несколько различающихся символов.2

Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку s с использованием кодирования по модели «движение к началу» (move-to-front) [ ] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся после предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и J и в случае, если J является локально гомогенной, строка mtffs) будет в основном состоять из целых числе малой величины.3 Учитывая это смещенное распределение, можно легко сжать строку mtffs): Барроуз и Уилер предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел.

2 Очевидно, что это верно в случае, если s обладает некоторой регулярностью: если строка s оказывается случайной, то и s также будет случайной.

3 Если s – текст на английском языке, mtf(s) обычно содержит более 50% нулей.

Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия бех потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого k > 0. К примеру, Каплан и др. [ ] показали, что для любой входной строки s и вещественного числа ji > 1 длина сжатой строки ограничена jinH^ (s) + n log(f (//.)) + jigi + O(logn) бит, где f (//.) – стандартная standard дзета-функция, а gk – функция, зависящая только от k и от размера S. Эта граница поточечно верна для любой строки s, одновременно для любых к > O и /x > 1; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы.