105
правок
Изменения
м
==Обратное преобразование #перенаправление [[Преобразование Барроуза-Уиллера==Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, после чего выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 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>.Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции.Уилера]]
Перенаправление на Преобразование Барроуза-Уилера
