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:
Временные сложности кодов могут быть значительно минимизированы. Я настоятельно рекомендую читателю найти их и обсудить в комментариях.