Материал из Викиконспекты
Обратное преобразование Барроуза-Уиллера
Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, после чего выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
| а |
... |
р
|
| а |
... |
д
|
| а |
... |
а
|
| а |
... |
к
|
| а |
... |
р
|
| б |
... |
а
|
| б |
... |
а
|
| д |
... |
а
|
| к |
... |
а
|
| р |
... |
б
|
| р |
... |
б
|
|
|
|
| аа |
... |
р
|
| аб |
... |
д
|
| аб |
... |
а
|
| ад |
... |
к
|
| ак |
... |
р
|
| бр |
... |
а
|
| бр |
... |
а
|
| да |
... |
а
|
| ка |
... |
а
|
| ра |
... |
б
|
| ра |
... |
б
|
|
|
|
| ааб |
... |
р
|
| абр |
... |
д
|
| абр |
... |
а
|
| ада |
... |
к
|
| ака |
... |
р
|
| бра |
... |
а
|
| бра |
... |
а
|
| даб |
... |
а
|
| кад |
... |
а
|
| раа |
... |
б
|
| рак |
... |
б
|
|
|
|
| аабр |
... |
р
|
| абра |
... |
д
|
| абра |
... |
а
|
| адаб |
... |
к
|
| акад |
... |
р
|
| браа |
... |
а
|
| брак |
... |
а
|
| дабр |
... |
а
|
| када |
... |
а
|
| рааб |
... |
б
|
| рака |
... |
б
|
|
|
|
| аабра |
... |
р
|
| абраа |
... |
д
|
| абрак |
... |
а
|
| адабр |
... |
к
|
| акада |
... |
р
|
| брааб |
... |
а
|
| брака |
... |
а
|
| дабра |
... |
а
|
| кадаб |
... |
а
|
| раабр |
... |
б
|
| ракад |
... |
б
|
|
|
|
| аабрак |
... |
р
|
| абрааб |
... |
д
|
| абрака |
... |
а
|
| адабра |
... |
к
|
| акадаб |
... |
р
|
| браабр |
... |
а
|
| бракад |
... |
а
|
| дабраа |
... |
а
|
| кадабр |
... |
а
|
| раабра |
... |
б
|
| ракада |
... |
б
|
|
|
|
| аабрака |
... |
р
|
| абраабр |
... |
д
|
| абракад |
... |
а
|
| адабраа |
... |
к
|
| акадабр |
... |
р
|
| браабра |
... |
а
|
| бракада |
... |
а
|
| дабрааб |
... |
а
|
| кадабра |
... |
а
|
| раабрак |
... |
б
|
| ракадаб |
... |
б
|
|
|
|
| аабракад |
... |
р
|
| абраабра |
... |
д
|
| абракада |
... |
а
|
| адабрааб |
... |
к
|
| акадабра |
... |
р
|
| браабрак |
... |
а
|
| бракадаб |
... |
а
|
| дабраабр |
... |
а
|
| кадабраа |
... |
а
|
| раабрака |
... |
б
|
| ракадабр |
... |
б
|
|
|
|
| аабракада |
... |
р
|
| абраабрак |
... |
д
|
| абракадаб |
... |
а
|
| адабраабр |
... |
к
|
| акадабраа |
... |
р
|
| браабрака |
... |
а
|
| бракадабр |
... |
а
|
| дабраабра |
... |
а
|
| кадабрааб |
... |
а
|
| раабракад |
... |
б
|
| ракадабра |
... |
б
|
|
|
|
| аабракадаб |
р
|
| абраабрака |
д
|
| абракадабр |
а
|
| адабраабра |
к
|
| акадабрааб |
р
|
| браабракад |
а
|
| бракадабра |
а
|
| дабраабрак |
а
|
| кадабраабр |
а
|
| раабракада |
б
|
| ракадабраа |
б
|
|
Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма [math] 0(N^3logN) [/math].
Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции.
