4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 21:37, 8 января 2017
, 8 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
Пример 1 Пусть строка s = mississippi. Для k = 1 имеем | Пример 1. Пусть строка s = mississippi. Для k = 1 имеем <math>i_s = mssp, s_s = isis, p_s = ip \;</math>. Следовательно, <math>H_1(s) = \frac{4}{11} H_0 (mssp) + \frac{4}{11} H_0 (isis) + \frac{2}{11} H_0 (ip) = \frac{6}{11} + \frac{4}{11} + \frac{2}{11} = \frac{12}{11}.</math> | ||
6 | |||
Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для s = an имеет место sj Hk(s) = 0 для любого k > 0. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [ ] было введено понятие модифицированной эмпирической энтропии нулевого порядка H*(s), имеющей следующее свойство: s\H*(s) по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. Модифицированная эмпирическая энтропия k-го порядка H* определяется как максимальная степень сжатия, которой можно достичь при просмотре не более чем k символов, следующих за кодируемым. | Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для s = an имеет место sj Hk(s) = 0 для любого k > 0. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [ ] было введено понятие модифицированной эмпирической энтропии нулевого порядка H*(s), имеющей следующее свойство: s\H*(s) по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. Модифицированная эмпирическая энтропия k-го порядка H* определяется как максимальная степень сжатия, которой можно достичь при просмотре не более чем k символов, следующих за кодируемым. | ||