BWT¶

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

¶История

Идея преобразования, основанного на циклических сдвигах строки, восходит к более ранним работам по комбинаторике и теории кодирования, однако именно Барроуз и Уилер формализовали и предложили практический алгоритм. Первоначально BWT разрабатывался для сжатия текстовых данных в системах хранения и передачи информации. В 1994 году вышла статья «A Block-sorting Lossless Data Compression Algorithm», где описывался метод, сочетающий BWT, move-to-front (MTF) и кодирование Хаффмана. Этот подход лёг в основу популярного архиватора bzip2, выпущенного в 1996 году. С тех пор BWT используется во многих программах сжатия, включая 7-Zip, Zstandard (в режиме BWT) и специализированные утилиты для сжатия геномных данных.

¶Описание алгоритма

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

Прямое BWT (forward BWT) преобразует исходную строку S длины N в строку L той же длины. Алгоритм состоит из следующих шагов:

Формирование всех циклических сдвигов. Строка S дописывается сама к себе, и из неё выделяются все возможные циклические сдвиги (ротации). Каждый сдвиг представляет собой строку, полученную переносом первых k символов в конец, где k от 0 до N-1.
Лексикографическая сортировка. Все N сдвигов сортируются в лексикографическом порядке (по алфавиту). Для этого обычно используется алгоритм сортировки суффиксов (например, суффиксный массив) или специализированные методы с учётом циклической природы.
Извлечение последнего столбца. После сортировки из каждого сдвига берётся последний символ. Полученная строка L и является результатом BWT. Дополнительно запоминается индекс I исходного сдвига (позиция, в которой исходная строка оказалась в отсортированном списке).

Пример. Для строки S = «BANANA» (N=6):

Циклические сдвиги: BANANA, ANANAB, NANABA, ANABAN, NABANA, ABANAN.
После сортировки (лексикографически): ABANAN, ANANAB, ANABAN, BANANA, NABANA, NANABA.
Последние символы: N, B, N, A, A, A → строка L = «NBNAAA». Индекс I = 3 (исходная строка BANANA на 4-й позиции, нумерация с 0).

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

Обратное BWT (inverse BWT) восстанавливает исходную строку S из строки L и индекса I. Алгоритм основан на свойстве, что столбец L и отсортированный столбец F (первый столбец отсортированных сдвигов) однозначно определяют исходную последовательность. Шаги:

Построение столбца F. Символы строки L сортируются в лексикографическом порядке. Это даёт первый столбец F отсортированной матрицы сдвигов.
Построение таблицы перехода. Для каждого символа в L и F строится массив «next», который указывает, какой символ из F соответствует данному символу из L. Обычно это делается путём подсчёта количества вхождений каждого символа и использования массива индексов.
Восстановление строки. Начиная с индекса I, последовательно выбираются символы из L: первый символ — L[I], затем по таблице перехода находится следующий индекс, и так далее, пока не будет получена строка длины N. Полученная последовательность является исходной строкой S.

Пример. Для L = «NBNAAA», I = 3:

F = сортировка L: A, A, A, B, N, N.
Построение next: для каждого символа в L (N, B, N, A, A, A) определяем соответствующую позицию в F. Получается последовательность индексов: 4, 3, 5, 0, 1, 2.
Начиная с I=3: L[3]=A, next[3]=0 → L[0]=N, next[0]=4 → L[4]=A, next[4]=1 → L[1]=B, next[1]=3 → L[3]=A, next[3]=0 → L[0]=N, next[0]=4 → L[4]=A. Строка: A, N, A, B, A, N → «ANABAN» — это исходная строка BANANA, но в обратном порядке? На самом деле обратное BWT даёт строку в обратном порядке, поэтому после разворота получается «BANANA». В корректной реализации для восстановления прямой последовательности используется другой порядок обхода.

На практике обратное BWT реализуется с помощью алгоритма, известного как «LF-mapping» (last-to-first mapping), который использует массив C (кумулятивные суммы) и массив Occ (количество вхождений символа в префиксе L). Это позволяет выполнять преобразование за линейное время O(N).

¶Свойства

Обратимость. BWT является биективным преобразованием: по L и I однозначно восстанавливается исходная строка.
Группировка повторяющихся символов. В строке L повторяющиеся символы часто оказываются рядом, особенно если исходная строка содержит повторяющиеся подстроки. Например, в тексте на естественном языке часто встречаются последовательности пробелов, букв «е» и т.д.
Зависимость от контекста. BWT эффективно группирует символы, которые встречаются в одном и том же контексте (окружении), что делает его полезным для сжатия с предсказанием контекста.
Размер блока. BWT обычно применяется к блокам данных фиксированного размера (например, 900 Кбайт в bzip2). Размер блока влияет на степень сжатия и скорость работы.
Сложность. Прямое и обратное BWT могут быть реализованы за O(N log N) или O(N) с использованием суффиксных массивов или алгоритмов сортировки строк.

¶Применение

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

BWT является ключевым компонентом архиватора bzip2, который использует следующую цепочку: BWT → Move-to-front (MTF) → Zero-length encoding (RLE) → Кодирование Хаффмана. bzip2 обеспечивает степень сжатия, сравнимую с LZMA, но с меньшей скоростью. BWT также используется в:

7-Zip (режим BWT, опция «bzip2»);
Zstandard (экспериментальный режим);
Компрессия геномных данных (например, в программах GDC, CRAM);
Сжатие текстовых файлов в системах резервного копирования.

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

В биоинформатике BWT применяется для построения индексов строк (суффиксных массивов) в алгоритмах поиска подстрок, таких как FM-index (Full-text index in Minute space). FM-index позволяет эффективно искать точные и неточные совпадения в геномных последовательностях и используется в популярных выравнивателях (например, Bowtie, BWA, SOAP). BWT здесь выступает как основа для сжатого представления текста, позволяющего выполнять поиск без полного разжатия.

¶Обработка естественного языка

BWT может применяться для анализа повторяющихся структур в тексте, например, для выявления частотных n-грамм или для сжатия словарей. Однако в NLP он используется реже, чем в сжатии и биоинформатике.

¶Варианты и модификации

ST (Suffix Tree) BWT. Модификация, использующая суффиксное дерево для ускорения сортировки.
BWT с блоками переменного размера. Для адаптации к разным типам данных.
Bijective BWT. Вариант, при котором преобразование является биективным без необходимости хранения индекса I (используется специальная маркировка конца строки).
BWT с контекстным моделированием. Комбинация BWT с PPM (prediction by partial matching) для улучшения сжатия.

¶Критика

Основной недостаток BWT — необходимость работы с блоками данных, что требует памяти O(N) для хранения матрицы сдвигов. Для больших блоков (например, 1 Гбайт) сортировка может быть ресурсоёмкой. Кроме того, BWT неэффективен для коротких строк (менее 100 символов) из-за накладных расходов на сортировку. В сжатии BWT уступает по скорости алгоритмам LZ77/LZ78 (например, Deflate), но может превосходить их по степени сжатия на определённых типах данных (например, тексты с повторяющимися структурами).

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

BWT был запатентован в США (патент 5,574,722), но срок действия патента истёк, и алгоритм свободен для использования.
Алгоритм вдохновлён сортировкой суффиксов, используемой в комбинаторике для построения суффиксных массивов.
В bzip2 используется блок размером до 900 Кбайт, что даёт хорошее сжатие для текстовых файлов.
BWT является основой для алгоритма BWCA (Burrows-Wheeler Compression Algorithm), который используется в некоторых архиваторах.

¶Источники

Burrows M., Wheeler D. J. A Block-sorting Lossless Data Compression Algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
Manzini G. The Burrows-Wheeler Transform: Theory and Practice. Lecture Notes in Computer Science, 2001.
Adjeroh D., Bell T., Mukherjee A. The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Bioinformatics. Springer, 2008.
Li H., Durbin R. Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics, 2009.
Документация архиватора bzip2 (версия 1.0.6).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →