Алгоритм Барроуза — Уилера

Алгоритм Барроуза — Уилера (BWT, Burrows–Wheeler transform) — это алгоритм обратимого преобразования строк, используемый в сжатии данных. Он переставляет символы исходной строки таким образом, что одинаковые символы оказываются сгруппированы, что повышает эффективность последующего кодирования (например, с помощью алгоритма MTF или арифметического кодирования). Преобразование не сжимает данные само по себе, но подготавливает их для более эффективного сжатия. Алгоритм был предложен Майклом Барроузом и Дэвидом Уилером в 1994 году.

История

Алгоритм был разработан в 1994 году сотрудниками исследовательского центра компании Digital Equipment Corporation (DEC) в Пало-Альто. Майкл Барроуз и Дэвид Уилер опубликовали технический отчёт «A Block-sorting Lossless Data Compression Algorithm», в котором описали метод, основанный на сортировке циклических сдвигов строки. Изначально алгоритм предназначался для сжатия текстовых данных, но впоследствии нашёл применение в сжатии произвольных двоичных данных, включая изображения, аудио и геномные последовательности.

В 1990-х годах BWT лёг в основу ряда популярных архиваторов, таких как bzip2 (разработан Джулианом Сьюардом в 1996 году). В 2000-х годах алгоритм стал использоваться в биоинформатике для построения индексов и поиска по тексту.

Принцип работы

Прямое преобразование

Прямое преобразование BWT выполняется в несколько этапов:

1. Формирование циклических сдвигов. Исходная строка длины \( n \) дополняется специальным символом-терминатором (обычно обозначается как $ или EOF), который считается меньше любого другого символа. Затем формируются все \( n \) циклических сдвигов строки, каждый из которых начинается с очередного символа исходной строки.

1. Сортировка сдвигов. Все полученные сдвиги сортируются в лексикографическом порядке (по возрастанию кодов символов). Символ-терминатор гарантирует, что каждый сдвиг уникален, и сортировка будет корректной.

1. Извлечение последнего столбца. После сортировки из каждого сдвига берётся последний символ. Полученная строка длиной \( n \) является результатом преобразования BWT. Также сохраняется индекс (номер строки) исходного сдвига в отсортированной матрице — он необходим для обратного преобразования.

Пример

Рассмотрим строку BANANA. Добавим терминатор $ (считаем, что $ < A < B < N). Циклические сдвиги:

• BANANA$
• ANANA$B
• NANA$BA
• ANA$BAN
• NA$BANA
• A$BANAN
• $BANANA

Отсортированные сдвиги:

1. $BANANA
2. A$BANAN
3. ANA$BAN
4. ANANA$B
5. BANANA$
6. NA$BANA
7. NANA$BA

Последние символы: A, N, N, B, $, A, A. Результат BWT: ANNB$AA. Исходный сдвиг (5-й) — индекс 5 (нумерация с 1).

Обратное преобразование

Обратное преобразование восстанавливает исходную строку по результату BWT и индексу исходного сдвига. Алгоритм обратного преобразования:

1. Создание таблицы. Строится таблица из \( n \) строк, изначально пустых. Каждая строка соответствует одному символу результата BWT.

1. Циклическое добавление. \( n \) раз выполняется операция: к каждой строке слева дописывается символ из результата BWT, после чего строки сортируются в лексикографическом порядке.

1. Извлечение результата. После \( n \) итераций строка с индексом, равным сохранённому индексу исходного сдвига, будет содержать исходную строку с терминатором в конце. Удаление терминатора даёт исходную строку.

Более эффективный метод обратного преобразования использует так называемую «LF-матрицу» (Last-to-First mapping), которая позволяет восстановить строку за линейное время без явного построения таблицы.

Свойства

Основные свойства

• Обратимость. Преобразование является биективным: по результату BWT и индексу исходного сдвига можно однозначно восстановить исходную строку.
• Группировка символов. BWT стремится сгруппировать одинаковые символы, особенно в строках с повторяющимися подстроками (например, в тексте на естественном языке). Это делает результат более поддающимся сжатию.
• Зависимость от размера блока. BWT применяется к блокам данных фиксированного размера (обычно от 100 КБ до 1 МБ). Размер блока влияет на степень сжатия и требуемую память.

Ограничения

• Высокая вычислительная сложность. Прямое преобразование требует сортировки \( n \) строк, что в наивной реализации имеет сложность \( O(n^2 \log n) \). Однако существуют алгоритмы, работающие за \( O(n \log n) \) или даже \( O(n) \) с использованием суффиксных массивов.
• Потребление памяти. Для хранения всех сдвигов требуется \( O(n^2) \) памяти в наивной реализации. На практике используются более эффективные структуры данных, такие как суффиксные массивы, которые требуют \( O(n) \) памяти.

Применение

Сжатие данных

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

1. BWT (преобразование Барроуза — Уилера).
2. MTF (Move-to-Front transform) — преобразование «перемещение в начало».
3. RLE (Run-Length Encoding) — кодирование длин серий.
4. Арифметическое кодирование или кодирование Хаффмана.

bzip2 обеспечивает степень сжатия, сравнимую с архиваторами на основе LZMA (7-Zip), но при более низкой скорости сжатия.

Биоинформатика

В биоинформатике BWT используется для построения индексов геномных последовательностей. Алгоритм FM-индекс (Ferragina–Manzini index) объединяет BWT с дополнительными структурами данных для эффективного поиска подстрок. FM-индекс лежит в основе популярных выравнивателей, таких как Bowtie, BWA и SOAP2, которые используются для картирования коротких прочтений (reads) на референсный геном.

Обработка текста

BWT применяется в задачах поиска по тексту, сжатия текстовых коллекций и построения суффиксных массивов. В частности, алгоритм используется в некоторых реализациях сжатия файлов в формате FASTQ (геномные данные).

Критика и альтернативы

Основным недостатком BWT является высокая вычислительная сложность и потребление памяти при работе с большими блоками данных. Альтернативными методами сжатия без потерь являются алгоритмы семейства LZ (LZ77, LZ78, LZMA), которые обеспечивают более высокую скорость сжатия при сопоставимой степени сжатия. Для специализированных задач (например, сжатие изображений) используются вейвлет-преобразования или дискретное косинусное преобразование (DCT).

В биоинформатике BWT конкурирует с методами на основе хеширования (например, BLAT) и суффиксных деревьев. Однако FM-индекс остаётся одним из наиболее эффективных инструментов для поиска по большим геномным последовательностям.

Интересные факты

• Алгоритм был назван в честь Майкла Барроуза и Дэвида Уилера, но сам Уилер впоследствии отмечал, что идея преобразования возникла из обсуждений с коллегами.
• BWT не является сжимающим алгоритмом в чистом виде — он лишь переупорядочивает символы. Сжатие достигается за счёт последующих этапов (MTF, RLE, энтропийное кодирование).
• В архиваторе bzip2 размер блока по умолчанию составляет 900 КБ, что позволяет достичь хорошего сжатия для текстовых файлов.
• BWT может быть применён к строкам, не содержащим терминатора, но в этом случае обратное преобразование может быть неоднозначным. Терминатор гарантирует единственность решения.

Источники

• Burrows M., Wheeler D. J. A block-sorting lossless data compression algorithm. — Technical Report 124, Digital Equipment Corporation, 1994.
• Seward J. The bzip2 home page. — 1996.
• Ferragina P., Manzini G. Indexing compressed text // Journal of the ACM. — 2005. — Vol. 52, No. 4. — P. 552–581.
• Li H., Durbin R. Fast and accurate short read alignment with Burrows–Wheeler transform // Bioinformatics. — 2009. — Vol. 25, No. 14. — P. 1754–1760.
• Nelson M. The Data Compression Book. — 2nd ed. — M&T Books, 1996.