4430
правок
Преобразование Барроуза-Уилера: различия между версиями
Материал из WEGA
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 13:40, 24 января 2017
, 24 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 135: | Строка 135: | ||
'''Лемма 4. Для любого i значение <math>\ | '''Лемма 4. Для любого i значение <math>\Psi(i) \;</math> может быть вычислено из <math>\hat{s} = bwt(s) \;</math>.''' | ||
Доказательство. Получить F можно в результате простой алфавитной сортировки символов <math>\hat{s} \;</math>. Затем вычислим <math>\Psi(i) \;</math> следующим образом: (1) положим с = F[i]; (2) вычислим <math>\ell \;</math>, такое, что F[i] является <math>\ell</math>-м вхождением c в F; (3) возвратим индекс <math>\ell</math>-го вхождения c в <math>\hat{s} \;</math>. □ | Доказательство. Получить F можно в результате простой алфавитной сортировки символов <math>\hat{s} \;</math>. Затем вычислим <math>\Psi(i) \;</math> следующим образом: (1) положим с = F[i]; (2) вычислим <math>\ell \;</math>, такое, что F[i] является <math>\ell</math>-м вхождением c в F; (3) возвратим индекс <math>\ell</math>-го вхождения c в <math>\hat{s} \;</math>. □ | ||
Вернемся к рис. 1. Для вычисления | Вернемся к рис. 1. Для вычисления <math>\Psi(10) \;</math> достаточно положить c = F[10] = s и заметить, что F[10] является вторым вхождением s в F. Тогда достаточно локализовать индекс j второго символа "s" в <math>\hat{s} \;</math>, в данном случае это j = 4. Следовательно, <math>\Psi(10) = 4 \;</math>; префиксом строки 10 является sissippi, а строки 4 – issippi. | ||
'''Теорема 5. Исходную строку можно восстановить из bwt(s).''' | '''Теорема 5. Исходную строку s можно восстановить из bwt(s).''' | ||
Доказательство. Из леммы 4 следует, что столбец F и отображение | Доказательство. Из леммы 4 следует, что столбец F и отображение <math>\Psi \;</math> могут быть получены из bwt(s). Обозначим за <math>j_0 \;</math> индекс специального символа $ в строке <math>\hat{s} \;</math>. По построению строка <math>j_0 \;</math> матрицы bwt имеет префикс s[0, n - 1], из чего следует <math>s[0] = F[j_0] \;</math>. Пусть <math>j_1 = \Psi(j_0) \;</math>. Согласно определению 1, префиксом строки <math>j_1 \;</math> является s[1, n - 1], следовательно, <math>s[1] = F[j_1] \;</math>. Продолжая аналогичные рассуждения, по индукции получаем <math>s[i] = F[\Psi^i (j_0)] \;</math> для i = 1, ..., n - 1. □ | ||
