4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 12:50, 23 января 2017
, 23 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 103: | Строка 103: | ||
'''Теорема 6. Пусть s[1, n] – строка над алфавитом S константного размера. Строка s = bwt(s) может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | '''Теорема 6. Пусть s[1, n] – строка над алфавитом S константного размера. Строка s = bwt(s) может быть вычислена за время 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 в лексикографическом порядке. Поскольку префиксом каждой строки матрицы M является уникальный суффикс s, за которым идет специальным символ $, суффиксный массив обеспечивает упорядочение строк в M. Следовательно, bwt(s) можно вычислить из sa за линейное время при помощи процедуры sa2bwt на рис. 2. □ | |||
'''Теорема 7. Пусть s[1, n] – строка над алфавитом S константного размера. При наличии bwt(s) строка s может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | |||
Доказательство. Алгоритм вычисления s практически дословно воспроизводить процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения 4> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа c 2 E счетчик count[c] выдает индекс первой строки матрицы M, префиксом которой является 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. | |||
Очевидно, что выполнение процедур bwt2psi и psi2text занимает время O(n). Объем рабочего пространства зависит главным образом от стоимости хранения массива psi, который занимает O(n log n) бит. □ | |||
'''Алгоритм сжатия Барроуза-Уилера''' | |||