Лекция 6. Преобразование Барроуза-Уилера

Определение матрицы BWT, строки BWT. Построение BWT(S) за O(N) через SA(SS). Восстановление матрицы по строке BWT (много radix-sort). обращение BWT с точностью до цикл. сдвига. Алгоритм обращения за O(N). Перестановка shl на строках матрицы при циклическом сдвиге влево, её предподсчёт за O(N). Добавление sentinel-а для однозначного обращения BWT. Поиск образца за O(P). Отрезок строк матрицы [l;r]. Добавление к образцу символа слева и изменение отрезка. Сведение к операции rank на строке BWT. Сведение перестановки shl к операции select. Задача rank/select для строки (запросы только rank). Случай бинарного алфавита: префиксные суммы, префиксные суммы для машинных слов, алгоритм RRR (O(N log log N / log N) бит памяти, O(1) времени). Сведение случая произвольного алфавита к бинарному алфавиту (O(log C) времени, суммарная длина N log C бит). Определение позиции в исходной строке по строке в матрице. Решение с O(N/K) слов памяти, O(K) времени.