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

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

История

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

В 1996 году алгоритм был интегрирован в утилиту bzip2, которая стала стандартной в операционных системах Linux и Unix. Позднее BWT нашёл применение в задачах хранения геномных последовательностей (секвенирование ДНК), где требуется эффективное сжатие больших объёмов данных с сохранением точности.

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

Преобразование Барроуза — Уилера выполняется над блоком данных фиксированной длины. Оно состоит из двух этапов: построение матрицы всех циклических сдвигов и извлечение последнего столбца отсортированной матрицы.

Построение матрицы сдвигов

Пусть имеется строка \( S \) длины \( n \). Строится матрица \( M \) размером \( n \times n \), где каждая строка \( i \) (\( 0 \leq i < n \)) является циклическим сдвигом \( S \) на \( i \) позиций влево. Другими словами, строка \( i \) содержит символы \( S[i], S[i+1], ..., S[n-1], S[0], ..., S[i-1] \).

Сортировка строк

Все строки матрицы \( M \) сортируются в лексикографическом порядке (в порядке возрастания кодов символов). Полученная матрица называется матрицей BWT.

Извлечение последнего столбца

Из отсортированной матрицы извлекается последний столбец \( L \) (последний символ каждой строки). Этот столбец \( L \) и является результатом преобразования BWT. Дополнительно сохраняется индекс исходной строки в отсортированной матрице — то есть номер строки, которая соответствует исходной строке \( S \) (до сортировки). Этот индекс необходим для обратного преобразования.

Пример

Рассмотрим строку BANANA.

1. Исходная строка: BANANA (длина \( n = 6\)).
2. Циклические сдвиги (все 6 возможных):

• 0: B A N A N A
• 1: A N A N A B
• 2: N A N A B A
• 3: A N A B A N
• 4: N A B A N A
• 5: A B A N A N

1. Сортировка в лексикографическом порядке:

• 0: A B A N A N
• 1: A N A B A N
• 2: A N A N A B
• 3: B A N A N A
• 4: N A B A N A
• 5: N A N A B A

1. Последний столбец \( L \): символы последних позиций строк в порядке сортировки: N, N, B, A, A, A. Получается строка NNBAAA.
2. Индекс исходной строки: исходная строка BANANA находится в отсортированной матрице на позиции 3 (строка BANANA). Сохраняется число 3.

Результат BWT: L = NNBAAA, первичный индекс = 3.

Таким образом, BWT преобразовал исходную строку BANANA в строку NNBAAA. В результирующей строке символы A оказались сгруппированы, что облегчает их кодирование.

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

Обратное BWT восстанавливает исходную строку по \( L \) и первичному индексу. Оно использует алгоритм, основанный на свойствах циклических сдвигов и счётчика символов. Суть обратного преобразования заключается в следующем:

1. Построить массив первых символов \( F \) строк отсортированной матрицы. Для этого \( L \) сортируется в лексикографическом порядке.
2. Создать массив \( T \) (префиксное отображение), где для каждого символа из \( L \) записывается его позиция в \( F \). Для этого используется подсчёт количества вхождений каждого символа в \( L \).
3. Начиная с первичного индекса \( I \), последовательно двигаться назад по массиву \( T \), извлекая символы из \( L \) в обратном порядке. Полученная последовательность символов является исходной строкой.

Алгоритм обратного преобразования гарантирует однозначное восстановление исходных данных при условии, что известен первичный индекс. Без этого индекса восстановление невозможно, так как разные исходные строки могут давать одинаковые \( L \) при разных индексах.

Свойства и особенности

Преимущества

• Локализация повторяющихся символов: BWT эффективно перегруппировывает символы так, чтобы одинаковые символы оказывались рядом, особенно в строках с повторяющимися подстроками (например, в текстовых файлах). Это позволяет последующим алгоритмам (RLE, MTF) сжимать данные с высокой степенью.
• Обратимость: Преобразование полностью обратимо без потери информации.
• Независимость от контекста: В отличие от некоторых других методов (например, LZW), BWT не требует построения словаря или модели данных перед применением.
• Применимость к блокам фиксированной длины: Алгоритм может обрабатывать данные по блокам, что удобно для потокового сжатия.

Недостатки

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

Классификация и варианты

Преобразование Барроуза — Уилера можно классифицировать по способу реализации сортировки и типу данных:

• Прямое BWT: Описанный выше алгоритм.
• BWT в составе bzip2: Реализован с использованием суффиксных массивов и сортировки слиянием (основной алгоритм).
• BWT в биоинформатике: Используется для сжатия геномных последовательностей, например, в формате FASTQ. В этой области применяется модификация — BWT-индекс (индекс сжатия), который используется для быстрого поиска подстрок в огромных текстах (например, алгоритм FM-индекса, 2000 г.).
• BWT с препроцессингом: Иногда перед BWT применяется преобразование run-length encoding (RLE) или move-to-front (MTF) для улучшения сжатия.

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

Применение

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

Основная область применения BWT — сжатие данных без потерь. Наиболее известный пример — архиватор bzip2, который использует BWT совместно с RLE, MTF и арифметическим кодированием. bzip2 обеспечивает высокую степень сжатия для текстовых файлов (например, HTML, исходного кода, текстовых документов). В тестах bzip2 часто опережает gzip (LZ77-основанный) по степени сжатия, но уступает по скорости. Используется в протоколах передачи данных (например, в HTTP сжатие bzip2 ограничено).

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

В биоинформатике BWT используется для сжатия и индексации геномных последовательностей. Разработанный на основе BWT FM-индекс (Ferragina–Manzini index) позволяет выполнять поиск подстрок (например, определённых генов или мутаций) в полном геноме за линейное время от длины запроса. Этот подход лежит в основе многих инструментов секвенирования, таких как bowtie, BWA (Burrows–Wheeler Aligner) и SOAP. Формат FASTQ, используемый для хранения данных секвенирования, часто сжимается с помощью bzip2 или специализированных BWT-кодеков.

Другие области

• Обработка естественного языка: BWT применяется для сжатия текстовых корпусов и для построения суффиксных массивов в задачах полнотекстового поиска.
• Компьютерное зрение: В некоторых системах сжатия изображений (например, в формате JPEG LS) BWT может использоваться как дополнительный этап.
• Архивация: BWT используется в некоторых архиваторах, таких как 7-Zip (в режиме LZMA, где BWT может применяться для сжатия метаданных).

Критика и ограничения

Хотя BWT является мощным инструментом сжатия, он не лишён недостатков. Основные критические замечания:

• Высокая вычислительная сложность: Для блоков большого размера (например, 900 килобайт, как в bzip2) сортировка требует значительных ресурсов процессора и памяти. Это делает BWT менее пригодным для потокового сжатия в реальном времени или на устройствах с ограниченными ресурсами.
• Неоптимальность для некоторых типов данных: BWT плохо сжимает данные с высокой энтропией (например, зашифрованные или сжатые файлы). Также он неэффективен для коротких строк (длиной до 100 символов).
• Чувствительность к порядку символов: Алгоритм чувствителен к регистру, пробелам и пунктуации. Разные кодировки могут давать разные результаты.
• Отсутствие гарантии максимального сжатия: BWT не гарантирует, что сжатие будет оптимальным; на некоторых строках (например, случайных) он может даже увеличивать объём данных.

Тем не менее, BWT остаётся одним из стандартных методов сжатия без потерь, особенно для текстов и геномных данных, благодаря своей эффективности и обратимости.

Источники

• Burrows, M., Wheeler, D. J. A Block-sorting Lossless Data Compression Algorithm. Digital Equipment Corporation, Technical Report 124, 1994.
• Manzini, G., Ferragina, P. Engineering a Lightweight Suffix Array Construction Algorithm. Algorithmica, 40(1), 2004.
• Salomon, D. Data Compression: The Complete Reference. 4th ed., Springer, 2007.
• Научно-технические публикации по bzip2 и алгоритмам сжатия.
• Документация GNU bzip2.