1. Введение:

Сделав небольшое отступление от текущей серии статей о сравнении строк, мы собираемся рассмотреть алгоритм преобразования Берроуза-Уилера, который составляет сердце многих механизмов сжатия в современных технологических стеках.

Преобразование Берроуза-Уилера пытается собрать вместе одинаковые символы в строке, т. е. сгруппировать вместе общие символы. Это может быть особенно важно в таких случаях, как секвенирование ДНК, где существует ограниченное количество алфавитов только из {A, T, C, G}. Например, преобразование BWT «ATCGATGCGCATCCGAT$» будет «TGC$GGTCTGCCCTAAAA». Здесь мы видим, что общие символы имеют тенденцию слипаться, как четыре буквы «А» в конце последовательности. BWT сам по себе не является алгоритмом сжатия, но помогает во многих алгоритмах сжатия.

2. Реализация :: Создание BWT заданной строки:

Для преобразования Берроуза-Уилера мы берем строку S[0…n] и добавляем разделитель «$» в конце. Разделители могут быть вставлены в начале, в конце, в обоих случаях или без них. Знак-разделитель будет знаком наименьшего веса, т.е. значения. Его также можно рассматривать как символ наивысшего веса. Его тоже можно вообще исключить.

Мы вращаем строку и генерируем таблицу вращений. Таблица сортируется в лексикографическом порядке, и строка создается из всех последних символов в строках из отсортированной таблицы. Получено BWT-преобразование строки. Давайте посмотрим на это в действии.

Для строки «яблоко» имеем:

$apple
e$appl
le$app
ple$ap
pple$a
apple$
Note that each following string is the right rotation of the preceding string. i.e. $apple --> e$appl when rotated right.

Отсортированная таблица становится:

$apple
apple$
e$appl
le$app
ple$ap
pple$a
Original String Position: 2

Помните, что символ $ предшествует всем остальным символам. Это то, что я имел в виду ранее, когда говорил, что у него самый низкий вес.

Из таблицы видно, что BWT-преобразование строки станет «e$lppa». Наряду с преобразованной строкой мы берем позицию исходной строки, т.е. 2 в таблице, которая позже будет использоваться при декодировании преобразования BWT.

2. Декодирование BW-преобразования строки.

Теперь, когда мы создали BWT-преобразование строки, пришло время сделать с ней такие вещи, как сжатие. Например, преобразованная строка BWT «AAAAATTTTCCCGGGGG» может быть представлена ​​как «5A4T3C5G». Это всего лишь пример, и для этой цели существуют очень эффективные алгоритмы.

Получив преобразованную строку, нам нужно декодировать ее в исходный текст шаблона. Строка BWT, сопровождаемая позицией исходной строки, используется для декодирования полученной преобразованной строки в исходный текст.

Начнем с исходной матрицы. Мы повернули исходный текст вправо при кодировании BWT. На этот раз мы просто повернем шаблон влево. И мы продолжим добавлять шаблон в таблицу матрицы и сортировать список.

Возьмем пример преобразованной строки «epa» с индексом 0.

Шаг 1: Создайте матрицу:

E
P
A

Шаг 2: Сортировка матрицы:

A
E
P

Шаг 3: Сдвиньте матрицу вправо.

-A
-E
-P

Шаг 4: Добавьте оригинальные символы:

EA
PE
AP

Шаг 5: Выполните шаги с 1 по 4 до длины строки.

В итоге получаем следующую матрицу:

ape
eap
pea

Из нашего исходного индекса мы видим, что ape — это исходная строка.

Реализация кода:

Вот реализация кода как для преобразования, так и для обратного преобразования строки из BWT. Коды не требуют пояснений (после того, как вы их запустите, они дадут полезные результаты) и размещены на gist под GNU GPL.

Код трансформации БВТ:

Код обратного преобразования BWT:

Временные сложности кодов могут быть значительно минимизированы. Я настоятельно рекомендую читателю найти их и обсудить в комментариях.