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

Перейти к навигации Перейти к поиску
Строка 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 < i < n обозначим за s[ki, n-1] суффикс строки s, являющейся префиксом строки i матрицы <math>\mathcal{M} \;</math>, и определим ^(i) как индекс строки, которой предшествует префикс s[ki + 1, n - 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 это будет "^(2) = 7, поскольку строка 2 матрицы <math>\mathcal{M} \;</math> имеет префикс ippi, а строка 7 – ppi. Отметим, что ^(i) не определено для  i = 0, поскольку у строки 0 не имеется надлежащего суффикса s.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[W(i)].'''
'''Лемма 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. □
1 В [3] вместо Ф авторы используют карту, в сущности, являющуюся инверсией 9. Использование 9 было предложено в литературе, посвященной сжатым индексам, где 9 и его обращение играют важную роль (см. [14]).
   
   


Источник — http://pco.iis.nsk.su/wega/index.php/Преобразование_Барроуза-Уилера