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

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

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

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

Преобразование Барроуза-Уилера представляет собой технику, используемую для сжатия данных без потерь. Она является алгоритмическим ядром инструмента 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], то