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

(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.