4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 18:57, 22 января 2017
, 22 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 64: | Строка 64: | ||
'''Лемма 2. Если 1 < i < j < n и F[i] = F[j], то''' | '''Лемма 2. Если 1 < i < j < n и F[i] = F[j], то''' | ||
Доказательство. Пусть s[ki, n - 1] (соответственно, s[kj, n - 1]) обозначает суффикс s, являющийся перфиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что s[ki, n - 1] -< s[kj, n - 1]. Из гипотезы F[i] = F[j] следует, что s[ki] = s[kj], поскольку должно иметь место s[ki + 1, n - 1] -< s[kj + 1, n - 1]. Из этого следует утверждение леммы, поскольку по построению ^(i) (&(j), соответственно) является лексикографической позицией строки, префиксом которой является s[ki + 1, n - 1] (s[kj + 1, n - 1], соответственно). □ | |||
'''Лемма 3. Для любого символа c 2 X1 верно: если F[j] _0 £-f/i-е вхождением c в F, то s[4^(j)] является l-м вхождением c в s.''' | |||
Доказательство. Возьмем индекс h, такой, что h < j и F[h] = F[j] = c (случай с h > j является симметричным). Из леммы 2 следует, что <^(fc) < Ф()), а из леммы 1 – что s[W(h)] = s[W(j)] = c. Следовательно, количество символов c, предшествующих F[j] в F, совпадает с количеством символов c, предшествующих s[^(j)] в s (аналогичная ситуация имеет место для последущих символов), из чего следует справедливость формулировки леммы. □ | |||
На рис. 1 имет место Ф(2) = 7, и F[2] и s[7] занимают вторую позицию в соответствующих строках. Это свойство обычно формулируется так: соответствующим символы имеют один и тот же относительный порядок в строках F и s. | |||
'''Лемма 4. Для любого i значение может быть вычислено из s = bwt(s).''' | |||
Доказательство. Получить F можно в результате простой алфавитной сортировки символов s. Затем вычислим ^(i) следующим образом: (1) положим с = F[i]; (2) вычислим £, такое, что F[i] является £-м вхождением c в F; (3) возвратим индекс l-го вхождения cms. □ | |||
Вернемся к рис. 1. Для вычисления ^(10) достаточно положить c = F[10] = s и заметить, что F[10] является вторым вхождением s в F. Тогда достаточно локализовать индекс j второго s в s, в данном случае это j = 4. Следовательно, ^(10) = 4; префиксом строки 10 является sissippi, а строки 4 –issippi. | |||
'''Теорема 5. Исходную строку можно восстановить из bwt(s).''' | |||