4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 16:41, 22 января 2017
, 22 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
'''Преобразование Барроуза-Уилера''' | '''Преобразование Барроуза-Уилера''' | ||
В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов см. рис. 1): | |||
1. добавить в концу строки s специальный символ $, который меньше любого другого символа в S; | |||
2. сформировать концептуальную матрицу M, строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке; | |||
3. построить преобразованные текст J = bwt(s), взяв последний столбец матрицы M. | |||
Заметим, что каждый столбец матрицы M – и, следовательно, преобразованный текст s – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы M, состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss. | |||
mississippi$ $ mississipp i | |||
ississippi$m i $mississip P | |||
ssissippi$mi i ppi$missis s | |||
sissippi$mis i ssippi$mis s | |||
issippi$miss i ssissippi$ m | |||
ssippi$missi m —^ ississippi $ | |||
sippi$missis P i$mississi P | |||
ippi$mississ P pi$mississ i | |||
ppi$mississi s ippi$missi s | |||
pi$mississip s issippi$mi s | |||
i$mississipp s sippi$miss i | |||
$mississippi s sissippi$m i | |||
Рисунок 1 | |||
Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это s = bwt(s) = ipssm$pissii | |||
Хотя из определения это не очевидно, преобразование bwt является обратимым, и оба преобразования (bwt и его обращение) могут быть выполнены за оптимальное время O(n). Ради лучшего согласования с более современной литературой следующая нотация и техники доказательства будут несколько отличаться от изложенных в работе [3]. | |||
'''Определение 1.''' Для 1 < i < n обозначим за s[ki, n-1] суффикс строки s, являющейся префиксом строки i матрицы M, и определим ^(i) как индекс строки, которой предшествует префикс s[ki + 1, n - 1]. | |||
Например, на рис. 1 это будет "^(2) = 7, поскольку строка 2 матрицы M имеет префикс ippi, а строка 7 – ppi. Отметим, что ^(i) не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s.1 | |||
'''Лемма 1. Для i = 1, ... , n имеет место F[i] = s[W(i)].''' | |||
Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является s[ki + 1, n - 1], является s[ki]. Из этого, согласно определению 1, следует s[&(i)] = s[ki] = F[i], что и требовалось доказать. □ | |||
'''Лемма 2. Если 1 < i < j < n и F[i] = F[j], то''' | |||