4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 23:05, 7 января 2017
, 7 января 2017→Преобразование Барроуза-Уилера
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
== Преобразование Барроуза-Уилера == | == Преобразование Барроуза-Уилера == | ||
Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа: | |||
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в S; | |||
(2) сформировать концептуальную матрицу M, строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке; | |||
(3) построить преобразованный текст s = bwt(s), взяв последний столбец матрицы M (см. рис. 1). | |||
В работе [ ] Барроуз и Уилер доказали, что s является перестановкой s и что можно восстановить s из I за время O(jsj). | |||
Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикограчфически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s длины k символы, непосредственно предшествующие каждому вхождению w в s, сгруппированы вместе в множество последовательных позиций в s, поскольку они являются последними символами строк матрицы M, которым предшествуют символы w. Используя нотацию, предложенную при определении Нь, можно перефразировать это свойство так, чтобы символы ws были последовательными в строке s или, что эквивалентно, что s содержит в качестве подстроки перестановку JIW{WS) строки ws. | |||
Пример 2. Пусть s = mississippi и k = 1. На рис. 1 показано, что s [1, 4] = pssm является перестановкой is =mssp. Кроме того, s[6, 7] = pi является перестановкой ps = ip, а s[8,11] = ssii – перестановкой ss = isis. | |||
Поскольку перестановка строки не меняет ее (модифицированной) эмпирической энтропии нулевого порядка (то есть HQ{JIW{WS)) = H0(WS)), преобразование Барроуза-Уилера может рассматриваться как способ свести задачу сжатия строки s вплоть до энтропии k-го порядка к задаче сжатия отдельных фрагментов s вплоть до их энтропии нулевого порядка. Чтобы убедиться в этом, рассмотрим разбиение строки s на подстроки JIW{WS), изменяя w над Sk. Из этого следует, что s = \_\w€zk fw^s), где J – оператор конкатенации над строками.3 | |||
3 Помимо tw2 jjk 7iw(ws), строка s также содержит последние k символов s (не входящие ни в какой ws) и специальный символ $. Для простоты в дальнейшем изложении эти символы будут игнорироваться. | |||
Из (1) следует, что J2 \JIW{WS)\H0{JIW{WS)) = Xj wsjH0(ws) = jsjHk(s): w2 | |||
Следовательно, для сжатия строки s вплоть до js достаточно сжать каждую ее подстроку JIW{WS) вплоть до эмпирической энтропии нулевого порядка. Заметим, однако, что при использовании вышеприведенной схемы параметр k необходимы выбрать заранее. Более того, подобную схему нельзя применить к H*, определенной в терминах контекстов длины не более k. В результате на данный момент не известно эффеективной процедуры для вычисления разбиения s согласно H*(s). Усилитель сжатия [3] представляет собой естественное дополнение bwt и позволяет сжимать любую строку s до Hk(s) (или H*(s)) одновременно для всех k > 0. | |||
== Алгоритм усиления степени сжатия == | |||