4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 19:23, 2 февраля 2017
, 2 февраля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 191: | Строка 191: | ||
'''Теорема 6. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. Строка <math>\hat{s} = bwt(s) \;</math> может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | '''Теорема 6. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. Строка <math>\hat{s} = bwt(s) \;</math> может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | ||
Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n | Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) бит рабочего пространства при помощи, например, алгоритма из [11]. Суффиксный массив представляет собой массив целых чисел sa[1, n], такой, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы <math>\mathcal{M} \;</math> является уникальный суффикс s, за которым идет специальный символ $, суффиксный массив обеспечивает упорядочение строк в <math>\mathcal{M} \;</math>. Следовательно, bwt(s) можно вычислить из sa за линейное время при помощи процедуры sa2bwt на рис. 2. □ | ||