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

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

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

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

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

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