Аноним

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

Материал из WEGA

Преобразование Барроуза-Уилера (посмотреть исходный код)

Версия от 16:41, 22 января 2017

4168 байт добавлено ,  22 января 2017
→‎Основные результаты
Строка 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], то'''
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/12182