4446
правок
Преобразование Барроуза-Уилера: различия между версиями
Материал из WEGA
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 13:52, 24 января 2017
, 24 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 186: | Строка 186: | ||
Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение | Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение <math>\Psi \;</math>, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива <math>[1, | \Sigma] | \;</math>, который изначально содержит в позиции count[i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения <math>j_0 \;</math>. | ||
'''Теорема 6. Пусть s[1, 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) ) бит рабочего пространства при помощи, например, алгоритма из [ ]. Суффиксный массив представляет собой строку целых чисел sa[1, n], такую, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы <math>\mathcal{M} \;</math> является уникальный суффикс s, за которым идет | Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) ) бит рабочего пространства при помощи, например, алгоритма из [ ]. Суффиксный массив представляет собой строку целых чисел 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] – строка над алфавитом | '''Теорема 7. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. При наличии bwt(s) строка s может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | ||
Доказательство. Алгоритм вычисления s практически дословно воспроизводить процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения 4> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа c 2 E счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс l-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi [h] значение i = Ф(И). После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5. | Доказательство. Алгоритм вычисления s практически дословно воспроизводить процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения 4> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа c 2 E счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс l-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi [h] значение i = Ф(И). После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5. | ||
