Обратное преобразование Барроуза-Уиллера — различия между версиями
(Новая страница: «==Обратное преобразование Барроуза-Уиллера== Если отсортировать символы последнего столб…») |
|||
| Строка 253: | Строка 253: | ||
|} | |} | ||
|} | |} | ||
| − | Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>. | + | Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>, также он требует <tex>0(N^2)</tex> памяти. |
| − | Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции. | + | Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции. Теперь если определить порядок получения символов 1ого столбца из символов последнего, то полученные значения будут являться вектором обратного преобразования. Для получения исходной строки надо выписать символы из преобразованной строки в порядке, соответствующему данному вектору, начиная с номера, содержащегося в исходных данных. Рассмотрим данный алгоритм на том же примере. |
| + | {| | ||
| + | | | ||
| + | {| 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 | ||
| + | |} | ||
| + | | || | ||
| + | | | ||
| + | {| border="1" | ||
| + | |9|| ||2 | ||
| + | |- | ||
| + | |7||||5 | ||
| + | |- | ||
| + | |0||||6 | ||
| + | |- | ||
| + | |8||||7 | ||
| + | |- | ||
| + | |10||||8 | ||
| + | |- | ||
| + | |1||||9 | ||
| + | |- | ||
| + | |2||||10 | ||
| + | |- | ||
| + | |3||||1 | ||
| + | |- | ||
| + | |4||||3 | ||
| + | |- | ||
| + | |5||||0 | ||
| + | |- | ||
| + | |6||||4 | ||
| + | |} | ||
| + | |} | ||
Версия 08:35, 2 января 2011
Обратное преобразование Барроуза-Уиллера
Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке. Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, после чего выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
|
|
|
|
|
|
|
|
|
|
Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма , также он требует памяти. Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции. Теперь если определить порядок получения символов 1ого столбца из символов последнего, то полученные значения будут являться вектором обратного преобразования. Для получения исходной строки надо выписать символы из преобразованной строки в порядке, соответствующему данному вектору, начиная с номера, содержащегося в исходных данных. Рассмотрим данный алгоритм на том же примере.
|
|
