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

Чтобы убедиться в мощи преобразования 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>.