Изменения
Новая страница: «==Обратное преобразование Барроуза-Уиллера== Если отсортировать символы последнего столб…»
==Обратное преобразование Барроуза-Уиллера==
Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, после чего выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
{|
|
{| border="1"
|а||...||р
|-
|а||...||д
|-
|а||...||а
|-
|а||...||к
|-
|а||...||р
|-
|б||...||а
|-
|б||...||а
|-
|д||...||а
|-
|к||...||а
|-
|р||...||б
|-
|р||...||б
|}
| ||
|
{| border="1"
|аа||...||р
|-
|аб||...||д
|-
|аб||...||а
|-
|ад||...||к
|-
|ак||...||р
|-
|бр||...||а
|-
|бр||...||а
|-
|да||...||а
|-
|ка||...||а
|-
|ра||...||б
|-
|ра||...||б
|}
| ||
|
{| border="1"
|ааб||...||р
|-
|абр||...||д
|-
|абр||...||а
|-
|ада||...||к
|-
|ака||...||р
|-
|бра||...||а
|-
|бра||...||а
|-
|даб||...||а
|-
|кад||...||а
|-
|раа||...||б
|-
|рак||...||б
|}
| ||
|
{| border="1"
|аабр||...||р
|-
|абра||...||д
|-
|абра||...||а
|-
|адаб||...||к
|-
|акад||...||р
|-
|браа||...||а
|-
|брак||...||а
|-
|дабр||...||а
|-
|када||...||а
|-
|рааб||...||б
|-
|рака||...||б
|}
| ||
|
{| border="1"
|аабра||...||р
|-
|абраа||...||д
|-
|абрак||...||а
|-
|адабр||...||к
|-
|акада||...||р
|-
|брааб||...||а
|-
|брака||...||а
|-
|дабра||...||а
|-
|кадаб||...||а
|-
|раабр||...||б
|-
|ракад||...||б
|}
| ||
|
{| border="1"
|аабрак||...||р
|-
|абрааб||...||д
|-
|абрака||...||а
|-
|адабра||...||к
|-
|акадаб||...||р
|-
|браабр||...||а
|-
|бракад||...||а
|-
|дабраа||...||а
|-
|кадабр||...||а
|-
|раабра||...||б
|-
|ракада||...||б
|}
| ||
|
{| border="1"
|аабрака||...||р
|-
|абраабр||...||д
|-
|абракад||...||а
|-
|адабраа||...||к
|-
|акадабр||...||р
|-
|браабра||...||а
|-
|бракада||...||а
|-
|дабрааб||...||а
|-
|кадабра||...||а
|-
|раабрак||...||б
|-
|ракадаб||...||б
|}
| ||
|
{| border="1"
|аабракад||...||р
|-
|абраабра||...||д
|-
|абракада||...||а
|-
|адабрааб||...||к
|-
|акадабра||...||р
|-
|браабрак||...||а
|-
|бракадаб||...||а
|-
|дабраабр||...||а
|-
|кадабраа||...||а
|-
|раабрака||...||б
|-
|ракадабр||...||б
|}
| ||
|
{| border="1"
|аабракада||...||р
|-
|абраабрак||...||д
|-
|абракадаб||...||а
|-
|адабраабр||...||к
|-
|акадабраа||...||р
|-
|браабрака||...||а
|-
|бракадабр||...||а
|-
|дабраабра||...||а
|-
|кадабрааб||...||а
|-
|раабракад||...||б
|-
|ракадабра||...||б
|}
| ||
|
{| border="1"
|аабракадаб||р
|-
|абраабрака||д
|-
|абракадабр||а
|-
|адабраабра||к
|-
|акадабрааб||р
|-
|браабракад||а
|-
|бракадабра||а
|-
|дабраабрак||а
|-
|кадабраабр||а
|-
|раабракада||б
|-
|ракадабраа||б
|}
|}
Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>.
Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции.
Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, после чего выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
{|
|
{| border="1"
|а||...||р
|-
|а||...||д
|-
|а||...||а
|-
|а||...||к
|-
|а||...||р
|-
|б||...||а
|-
|б||...||а
|-
|д||...||а
|-
|к||...||а
|-
|р||...||б
|-
|р||...||б
|}
| ||
|
{| border="1"
|аа||...||р
|-
|аб||...||д
|-
|аб||...||а
|-
|ад||...||к
|-
|ак||...||р
|-
|бр||...||а
|-
|бр||...||а
|-
|да||...||а
|-
|ка||...||а
|-
|ра||...||б
|-
|ра||...||б
|}
| ||
|
{| border="1"
|ааб||...||р
|-
|абр||...||д
|-
|абр||...||а
|-
|ада||...||к
|-
|ака||...||р
|-
|бра||...||а
|-
|бра||...||а
|-
|даб||...||а
|-
|кад||...||а
|-
|раа||...||б
|-
|рак||...||б
|}
| ||
|
{| border="1"
|аабр||...||р
|-
|абра||...||д
|-
|абра||...||а
|-
|адаб||...||к
|-
|акад||...||р
|-
|браа||...||а
|-
|брак||...||а
|-
|дабр||...||а
|-
|када||...||а
|-
|рааб||...||б
|-
|рака||...||б
|}
| ||
|
{| border="1"
|аабра||...||р
|-
|абраа||...||д
|-
|абрак||...||а
|-
|адабр||...||к
|-
|акада||...||р
|-
|брааб||...||а
|-
|брака||...||а
|-
|дабра||...||а
|-
|кадаб||...||а
|-
|раабр||...||б
|-
|ракад||...||б
|}
| ||
|
{| border="1"
|аабрак||...||р
|-
|абрааб||...||д
|-
|абрака||...||а
|-
|адабра||...||к
|-
|акадаб||...||р
|-
|браабр||...||а
|-
|бракад||...||а
|-
|дабраа||...||а
|-
|кадабр||...||а
|-
|раабра||...||б
|-
|ракада||...||б
|}
| ||
|
{| border="1"
|аабрака||...||р
|-
|абраабр||...||д
|-
|абракад||...||а
|-
|адабраа||...||к
|-
|акадабр||...||р
|-
|браабра||...||а
|-
|бракада||...||а
|-
|дабрааб||...||а
|-
|кадабра||...||а
|-
|раабрак||...||б
|-
|ракадаб||...||б
|}
| ||
|
{| border="1"
|аабракад||...||р
|-
|абраабра||...||д
|-
|абракада||...||а
|-
|адабрааб||...||к
|-
|акадабра||...||р
|-
|браабрак||...||а
|-
|бракадаб||...||а
|-
|дабраабр||...||а
|-
|кадабраа||...||а
|-
|раабрака||...||б
|-
|ракадабр||...||б
|}
| ||
|
{| border="1"
|аабракада||...||р
|-
|абраабрак||...||д
|-
|абракадаб||...||а
|-
|адабраабр||...||к
|-
|акадабраа||...||р
|-
|браабрака||...||а
|-
|бракадабр||...||а
|-
|дабраабра||...||а
|-
|кадабрааб||...||а
|-
|раабракад||...||б
|-
|ракадабра||...||б
|}
| ||
|
{| border="1"
|аабракадаб||р
|-
|абраабрака||д
|-
|абракадабр||а
|-
|адабраабра||к
|-
|акадабрааб||р
|-
|браабракад||а
|-
|бракадабра||а
|-
|дабраабрак||а
|-
|кадабраабр||а
|-
|раабракада||б
|-
|ракадабраа||б
|}
|}
Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>.
Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции.
