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

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

Поскольку перестановка строки не меняет ее (модифицированной) эмпирической энтропии нулевого порядка (то есть <math>H_0 (\pi_w (w_s)) = H_0 (w_s)) \;</math>), преобразование Барроуза-Уилера может рассматриваться как способ свести задачу сжатия строки s вплоть до энтропии k-го порядка к задаче сжатия ''различных фрагментов'' <math>\hat{s} \;</math> вплоть до их энтропии ''нулевого порядка''. Чтобы убедиться в этом, рассмотрим разбиение <math>\hat{s} \;</math> на подстроки <math>\pi_w (w_s) \;</math>, изменяя w над <math>\Sigma^k \;</math>. Из этого следует, что \hat{s} = \_\w€zk fw^s), где J – оператор конкатенации над строками.3

 

Следовательно, для сжатия строки s вплоть до js достаточно сжать каждую ее подстроку JIW{WS) вплоть до эмпирической энтропии нулевого порядка. Заметим, однако, что при использовании вышеприведенной схемы параметр k необходимы выбрать заранее. Более того, подобную схему нельзя применить к H*, определенной в терминах контекстов длины не более k. В результате на данный момент не известно эффеективной процедуры для вычисления разбиения s согласно H*(s). Усилитель сжатия [3] представляет собой естественное дополнение bwt и позволяет сжимать любую строку s до Hk(s) (или H*(s)) одновременно для всех k > 0.