Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 95: | Строка 95: | ||
Важное свойство bwt заключается в том, что и прямая, и обратная версия преобразования позволяют разрабатывать эффективные алгоритмы, исключительно простые и элегантные. | Важное свойство bwt заключается в том, что и прямая, и обратная версия преобразования позволяют разрабатывать эффективные алгоритмы, исключительно простые и элегантные. | ||
Рисунок 2 | |||
Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение (?, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива [1, |27|], который изначально содержит в позиции count [i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения j0 | |||
'''Теорема 6. Пусть s[1, n] – строка над алфавитом S константного размера. Строка s = bwt(s) может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | |||