16
правок
Изменения
Алгоритм за O(n)
Временная сложность данного алгоритма <tex>O(N^3\log{N}) </tex>, пространственная <tex>O(N^2)</tex>.
====Доказательство корректности====
Пусть дана строка <tex>$s$</tex>, к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических перестановок исходной строки, методом математической индукции.
Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических перестановок <tex> $s$ </tex>, после последнего шага получившиеся строки будут совпадать с циклическими перестановками <tex> $s$ </tex>.
===ОптимизацияОптимизированный наивный алгоритм===
{| border="1"
|а
|}
====Сложность оптимизированного алгоритма====
Данный алгоритм работает за <tex>O(N\log{N})</tex> времени и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> — размер алфавита.
j = t[j]
====Доказательство корректности====
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</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":
{|border ="1"
!colspan="3" | Таблица первого предподсчёта
|-
! Позиция || Символ || Результат
|-align="center"
! 0 || B || 0
|-
! 1 || C || 0
|-
! 2 || A || 0
|-
! 3 || B || 1
|-
! 4 || A || 1
|-
! 5 || A || 2
|-
! 6 || A || 3
|}
{|border ="1"
!colspan="2" | Таблица второго предподсчёта
|-
! Символ || Количество <br /> меньших
|-align="center"
! A || 0
|-
! B || 4
|-
! C || 6
|}
Для удобства пронумеруем известные нам данные:
# <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>s_{n-1}</tex> находится в строке <tex>L</tex> под номером <tex>I</tex>, так как в таблице строка <tex>s^0</tex> имела номер <tex>I</tex>. Найдём символ <tex>s_{n-2}</tex>.
Символ <tex>s_{n-2}</tex> имеет в строке <tex>L</tex> тот же номер, что строка <tex>s^{n-1}</tex> имела в таблице перестановок: строка <tex>s^{n-1}</tex> начинается с символа <tex>s_{n-1}</tex>, <tex>s_{n-2}</tex> находится на 1 левее его и из-за циклического сдвига оказывается в последнем столбце. Нам известен символ <tex>s_{n-1}</tex>. Посчитаем, на каком месте в таблице будет стоять строка, начинающаяся с этого символа.
Из 4 известно количество символов, меньших <tex>s_{n-1}</tex>. Все строки, начинающиеся с этих символов, стоят в таблице раньше <tex>s^{n-1}</tex>. Кроме того, в таблице есть строки, начинающиеся с того же символа, что и <tex>s^{n-1}</tex>. Из 3 известно, сколько их: если символ, равный <tex>s_{n-1}</tex>, встречался в <tex>L</tex> раньше, чем <tex>s_{n-1}</tex>, то в таблице строка, начинающаяся с этого символа, тоже стоит раньше строки, начинающейся с <tex>s_{n-1}</tex>, так как префикс строки, оканчивающейся на этот символ, меньше префикса строки, оканчивающейся на <tex>s_{n-1}</tex>.
Тогда сумма этих двух величин является номером символа <tex>s_{n-2}</tex> в строке <tex>L</tex>. Зная <tex>s_{n-1}</tex> и <tex>s_{n-2}</tex>, аналогично найдём <tex>s_{n-3}\ldots s_0</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
* Суммируем значения из двух таблиц: <tex>0+0=0</tex>, <tex>s_5=L_0=B</tex>, <tex>s^0=.....</tex>BA
* Суммируем: <tex>0+4=4</tex>, <tex>s_4=L_4=A</tex>, <tex>s^0=....</tex>ABA
* Суммируем: <tex>1+0=1</tex>, <tex>s_3=L_1=C</tex>, <tex>s^0=...</tex>CABA
* Суммируем: <tex>0+6=6</tex>, <tex>s_2=L_6=A</tex>, <tex>s^0=..</tex>ACABA
* Суммируем: <tex>3+0=3</tex>, <tex>s_2=L_3=B</tex>, <tex>s^0=.</tex>BACABA
* Суммируем: <tex>1+4=5</tex>, <tex>s_2=L_5=A</tex>, <tex>s^0=</tex>ABACABA
== Дополнительно ==
