Изменения

Перейти к: навигация, поиск

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

35 байт убрано, 13:05, 31 октября 2018
м
Delete some wrong "$".
== Пример работы алгоритма ==
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA".
{| class="wikitable"
|}
Результат можно записать так: <tex>$BWT(s) = $(</tex>"BCABAAA", <tex>3)</tex>, где <tex>3</tex> {{---}} номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA$".
{| class="wikitable"
При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так: <tex>$BWT(s) =$</tex> "$CBBAAAA".
== Обратное преобразование ==
===Наивный алгоритм===
Пусть нам дано: <tex>$BWT(s) =$(</tex>"BCABAAA", <tex>3)</tex>. Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно [[Сортировки | отсортируем]] матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических сдвигов строки, которую нам надо найти. Выстроив полный отсортированный список сдвигов, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
Алгоритм обратного преобразования описан в таблице ниже:
|}
Следует также заметить, что если нам было бы дано <tex>$BWT(s) = $</tex> "$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки <tex>\$</tex> на конце: ABACABA$.
Временная сложность данного алгоритма <tex>O(N^3\log{N}) </tex>, пространственная <tex>O(N^2)</tex>.
====Доказательство корректности====
Пусть дана строка <tex>$s$</tex>, к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических сдвигов исходной строки, методом математической индукции.* '''База'''. Циклически сдвинем все строки исходной таблицы на <tex>1</tex> влево. Тогда в столбце <tex>n</tex> будут находиться символы, добавленные на первом шаге алгоритма, а в столбце <tex>n - 1</tex> символы, изначально стоявшие в таблице до первого шага алгоритма. Таким образом, полученные на первом шаге алгоритма строки являются суффиксами циклических сдвигов строки <tex>$s$</tex>.* '''Предположение'''. Пусть на <tex>k</tex> шаге алгоритма все полученные строки являются суффиксами циклических сдвигов строки <tex>$s$</tex>.
* '''Переход'''. Рассмотрим <tex>k+1</tex>-ый шаг алгоритма. Все строки отсортированы, поэтому самый левый столбец совпадет с <tex>1</tex> столбцом исходной таблицы. Циклически сдвинем все строки исходной таблицы на <tex>n - k</tex> символов вправо. Теперь по предположению первые <tex>k</tex> символов справа в каждой строке совпадают у исходной таблицы и у таблицы, полученной в результате работы алгоритма. <tex>k</tex>-ые справа столбцы также совпадают. Добавленный на <tex>k+1</tex>-ом шаге столбец также совпадает с <tex>k+1</tex>-ым справа столбцом сдвинутой исходной таблицы, так как совпадает с последним столбцом исходной таблицы, которая была сдвинута на <tex>n-k</tex>.
{| class="wikitable"
!colspan="3" | <tex>$k+1$</tex> шаг алгоритма при <tex>$k=3$</tex>
|-
! Исходная <br /> таблица || Сдвинутая <br /> таблица || Результат <br /> работы <br /> алгоритма
|}
Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических сдвигов <tex> $s$ </tex>, после последнего шага получившиеся строки будут совпадать с циклическими сдвигами <tex> $s$ </tex>.
===Оптимизированный наивный алгоритм===
===Алгоритм за линейное время===
Будем обозначать <tex>s^i</tex> <tex>i</tex>-ую циклический сдвиг <tex>$s$</tex>. Пусть <tex>s^0 = s_0 s_1 \ldots s_{n-1}</tex>, <tex>$BWT(s)$\;= L</tex> и <tex>L = L_0L_1\ldots L_{n-1}</tex>, <tex>I</tex> -- номер строки <tex>s^0</tex> в таблице. Предподсчитаем следующие величины:
* Для каждого <tex>L_i</tex> количество символов на подстроке <tex>l_0, \ldots , l_{i-1}</tex>, равных <tex>L_i</tex>
* Для каждого уникального <tex>L_i</tex> количество символов в <tex>L</tex>, лексикографически меньших, чем <tex>L_i</tex>
Пример для <tex>$BWT(s) =$</tex> "BCABAAA":
{| class="wikitable"
Для удобства пронумеруем известные нам данные:
# <tex>L</tex>, последний столбец таблицы сдвигов
# <tex>I</tex>, номер строки <tex>$s$</tex> в таблице сдвигов
# Частота, с которой символ <tex>L_{i}</tex> встречается в подстроке <tex>l_0, \ldots , l_{i-1}</tex>
# Для каждого уникального символа количество лексикографически меньших символов в <tex>L</tex>
Предподсчёт занимает <tex>O(n)</tex> времени, восстановление каждого из <tex>n</tex> символов занимает <tex>O(1)</tex> времени. Суммарное время работы алгоритма <tex>O(n)</tex>.
Пример работы для <tex>$BWT(s) = ($</tex>"BCABAAA", 2<tex>)</tex> (нумерация с 0):
* <tex>s^0 = .......</tex>
* <tex>s_6=L_2 = A</tex>. Тогда <tex>s^0=......</tex>A
66
правок

Навигация