Преобразование Барроуза-Уилера: различия между версиями

Доказательство. Суффиксный массив строки 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. □

'''Теорема 7. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. При наличии bwt(s) строка s может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.'''

Доказательство. Алгоритм вычисления s практически дословно воспроизводит процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения <math>\Psi \;</math> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа <math>c \in \Sigma \;</math> счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс <math>\ell</math>-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi[h] значение <math>i = \Psi(h) \;</math>. После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5.