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

'''Нотация. Эмпирическая энтропия'''

Пусть s – строка над алфавитом <math>\Sigma = \{ a_1, ..., a_h \} \;</math>. Обозначим для каждого <math>a_i \in \Sigma \;</math> за <math>n_i \;</math> количество вхождений <math>a_i \;</math> в s. ''Эмпирическая энтропия нулевого порядка'' строки s определяется как <math>H_0(s) = - \sum^h_{i = 1} (n_i / |s|) \; log (n_i / |s|)</math>, где все алгоритмы берутся по основанияю 2, а 0 log 0 = 0. Хорошо известно, что <math>H_0 \;</math> представляет собой максимальный уровень сжатия, которого можно достичь при использовании уникального декодируемого кода, в котором каждому символу алфавита назначается уникальное кодовое слово. Более высокой степени сжатия можно достичь, если кодовое слово символа зависит от k символов, следующих за ним (то есть от его ''контекста''). [''Большинство алгоритмов сжатия данных обычно рассматривают контекст, '''предшествующий''' кодируемым символам. В данном описании используется нестандартный «прямой» контекст для упрощения нотации в последующих разделах. Работа с «прямым» контекстом эквивалентна работе с традиционным «обратным» контекстом для обращенной строки s (подробнее см. в [3]).''] Определим <math>w_s \;</math> как строку единичных символов, непосредственно предшествующих вхождениям w в s. Например, для s = bcabcabdca получим <math>ca_s = bbd \;</math>. Значение