Изменения
→Обратное преобразование
== Обратное преобразование ==
===Наивный алгоритм===
Пусть нам дано: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3). Тогда выпишем в столбик нашу преобразованную последовательность символов ''"BCABAAA"''. Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем ''"BCABAAA"''. Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
Следует также заметить, что если нам было бы дано <tex>BWT(s)=</tex>''"$CBBAAAA"'', то мы также получили бы нашу исходную строку, только с символом конца строки ''$'' на конце: ''ABACABA$''.
Как несложно посчитать сложность данного алгоритма <tex>O(N^3logN) </tex>, также он требует <tex>O(N^2)</tex> памяти.
===Оптимизация===
Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. Мы приписывали новый столбец и сортировали имеющиеся данные. На каждом шагу мы к строке, которая находилась на <tex> i </tex>-ом месте приписываем в начало <tex> i </tex> -ый элемент столбца входных данных. Пусть изначально мы знаем каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из предыдущего шага какое место занимала наша строка без этого первого символа (<tex> i </tex> -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером <tex> i </tex> всегда будет перемещаться на позицию с номером <tex> j </tex>.
{| border="1"
|0||а|| ||р||9
|-
|1||а||||д||7
|-
|2||а|| ||a||0
|-
|3||а|| ||к||8
|-
|4||а|| ||р||10
|-
|5||б|| ||a||1
|-
|6||б|| ||a||2
|-
|7||д|| ||a||3
|-
|8||к|| ||a||4
|-
|9||р|| ||б||5
|-
|10||р|| ||б||6
|}
Здесь слева это отсортированный данный столбец, чтобы мы знали какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку мы в нашем алгоритме новый столбец приписываем в начало, то мы из состояния <tex> i </tex> (левый столбец) переходим в состояние <tex> j </tex> (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из <tex> j </tex> в <tex> i </tex> восстановить строку.
{|
|
{| border="1"
|6
|→
|10
|→
|4
|→
|8
|→
|3
|→
|7
|→
|1
|→
|5
|→
|9
|→
|0
|→
|2
|-
|а
|
|б
|
|р
|
|а
|
|к
|
|а
|
|д
|
|а
|
|б
|
|р
|
|а
|}
===Сложность оптимизированного алгоритма===
Данный алгоритм работает за <tex>O(NlogN)</tex> действий и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> — размер алфавита.
===Псевдокод оптимизированного алгоритма===
Пусть <tex> N </tex> — количество символов во входной строке, <tex> M </tex> — количество символов в алфавите, <tex> k </tex> — номер исходной строки в матрице перестановок, <tex> s </tex> — входящая строка, <tex> count </tex> — массив для сортировки подсчетом, <tex> t </tex> — вектор обратного преобразования, <tex> x </tex> — номер данной нам строки в таблице.
// Cчитаем частоты символов
for i = 0 .. M
count[i] = 0
for i = 0 .. N
count[s[i]]++
// Упорядочиваем символы, чтобы получить первый столбец исходной матрицы
// count[i] указывает на первую позицию символа i в первом столбце
sum = 0
for i = 0 .. M
sum = sum + count[i]
count[i] = sum - count[i]
// Cоздаем вектор обратного преобразования
for i = 0 .. N
t[count[s[i]]] = i
count[s[i]]++
// И восстанавливаем исходный текст
j = t[x]
for i = 0 .. N
print(s[j])
j = t[j]
== Ссылки ==
