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