4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 23:24, 22 января 2017
, 22 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 85: | Строка 85: | ||
'''Теорема 5. Исходную строку можно восстановить из bwt(s).''' | '''Теорема 5. Исходную строку можно восстановить из bwt(s).''' | ||
Доказательство. Из леммы 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]). | |||
'''Алгоритмические вопросы''' | |||
Важное свойство bwt заключается в том, что и прямая, и обратная версия преобразования позволяют разрабатывать эффективные алгоритмы, исключительно простые и элегантные. | |||