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

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

Пример 2. Пусть s = mississippi и k = 1. На рис. 1 показано, что s [1, 4] = pssm является перестановкой is =mssp. Кроме того, s[6, 7] = pi является перестановкой ps = ip, а s[8,11] = ssii – перестановкой ss = isis.