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

Пример 2. Пусть s = mississippi и k = 1. На рис. 1 показано, что <math>\hat{s} [1, 4] = pssm \;</math> является перестановкой <math>i_s = mssp \;</math>. Кроме того, <math>\hat{s} [6, 7] = pi \;</math> является перестановкой <math>p_s = ip \;</math>, а <math>\hat{s} [8, 11] = ssii \;</math> – перестановкой <math>s_s = isis \;</math>.

Поскольку перестановка строки не меняет ее (модифицированной) эмпирической энтропии нулевого порядка (то есть HQ{JIW{WS)) = H0(WS)), преобразование Барроуза-Уилера может рассматриваться как способ свести задачу сжатия строки s вплоть до энтропии k-го порядка к задаче сжатия отдельных фрагментов s вплоть до их энтропии нулевого порядка. Чтобы убедиться в этом, рассмотрим разбиение строки s на подстроки JIW{WS), изменяя w над Sk. Из этого следует, что s = \_\w€zk fw^s), где J – оператор конкатенации над строками.3

3 Помимо tw2 jjk 7iw(ws), строка s также содержит последние k символов s (не входящие ни в какой ws) и специальный символ $. Для простоты в дальнейшем изложении эти символы будут игнорироваться.