4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 11:25, 24 января 2017
, 24 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
$mississippi s sissippi$m i | $mississippi s sissippi$m i | ||
Рисунок 1 | Рисунок 1. Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>. | ||
Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>. | |||
| Строка 52: | Строка 50: | ||
'''Определение 1.''' Для 1 | '''Определение 1.''' Для <math>1 \le i \le n \;</math> обозначим за <math>s[k_i, n - 1] \;</math> суффикс строки s, являющейся префиксом строки i матрицы <math>\mathcal{M} \;</math>, и определим <math>\Psi(i) \;</math> как индекс строки, которой предшествует префикс <math>s[k_{i + 1}, n - 1] \;</math>. | ||
Например, на рис. 1 | Например, на рис. 1 <math>\Psi(2) = 7 \;</math>, так как строка 2 матрицы <math>\mathcal{M} \;</math> имеет префикс ippi, а строка 7 – ppi. Отметим, что <math>\Psi(i) \;</math> не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s. ''[В [3] вместо <math>\Psi \;</math> авторы используют отображение, в сущности, являющееся инверсией <math>\Psi \;</math>. Использование <math>\Psi \;</math> было предложено в литературе, посвященной сжатым индексам, где <math>\Psi \;</math> и его обращение играют важную роль (см. [14]).]'' | ||
'''Лемма 1. Для i = 1, ... , n имеет место F[i] = s[ | '''Лемма 1. Для i = 1, ... , n имеет место <math>F[i] = \hat{s}[ \Psi(i)] \;</math>.''' | ||
Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является s[ki + 1, n - 1], является s[ki]. Из этого, согласно определению 1, следует s[&(i)] = s[ki] = F[i], что и требовалось доказать. □ | Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является s[ki + 1, n - 1], является s[ki]. Из этого, согласно определению 1, следует s[&(i)] = s[ki] = F[i], что и требовалось доказать. □ | ||
| Строка 87: | Строка 85: | ||
Доказательство. Из леммы 4 следует, что столбец F и отображение 4> могут быть получены из bwt(s). Обозначим за j0 индекс специального символа $ в строке s. По построению строка j0 матрицы bwt имеет префикс s[0, n - 1], из чего следует s[0] = F[j0]. Пусть j1 = ^(/o). Согласно определению 1, префиксом строки j1 является s[1, n - 1], следовательно, s[1] = F[j1]. Продолжая аналогичные рассуждения, по индукции получаем j0)] для i = 1, ..., n - 1. □ | Доказательство. Из леммы 4 следует, что столбец F и отображение 4> могут быть получены из bwt(s). Обозначим за j0 индекс специального символа $ в строке s. По построению строка j0 матрицы bwt имеет префикс s[0, n - 1], из чего следует s[0] = F[j0]. Пусть j1 = ^(/o). Согласно определению 1, префиксом строки j1 является s[1, n - 1], следовательно, s[1] = F[j1]. Продолжая аналогичные рассуждения, по индукции получаем j0)] для i = 1, ..., n - 1. □ | ||