Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа: | Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа: | ||
(1) добавить в концу строки 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 из | В работе [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. | ||