Усиление степени сжатия текста: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 40: Строка 40:
Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа:
Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа:


(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в S;
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>;


(2) сформировать концептуальную матрицу M, строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке;
(2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке;


(3) построить преобразованный текст s = bwt(s), взяв последний столбец матрицы M (см. рис. 1).
(3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1).




В работе [ ] Барроуз и Уилер доказали, что s является перестановкой s и что можно восстановить s из I за время O(jsj).
В работе [2] Барроуз и Уилер доказали, что <math>\hat{s} \;</math> является перестановкой s и что можно восстановить s из <math>\hat{s} \;</math> за время O(|s|).




Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикограчфически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s длины k символы, непосредственно предшествующие каждому вхождению w в s, сгруппированы вместе в множество последовательных позиций в s, поскольку они являются последними символами строк матрицы M, которым предшествуют символы w. Используя нотацию, предложенную при определении Нь, можно перефразировать это свойство так, чтобы символы ws были последовательными в строке s или, что эквивалентно, что s содержит в качестве подстроки перестановку JIW{WS) строки ws.
Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикограчфически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s длины k символы, непосредственно предшествующие каждому вхождению w в s, сгруппированы вместе в множество последовательных позиций в s, поскольку они являются последними символами строк матрицы <math>\mathcal{M} \;</math>, которым предшествуют символы w. Используя нотацию, предложенную при определении Нь, можно перефразировать это свойство так, чтобы символы ws были последовательными в строке s или, что эквивалентно, что s содержит в качестве подстроки перестановку JIW{WS) строки ws.




4511

правок

Навигация