4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 15:07, 7 января 2017
, 7 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
== Основные результаты == | == Основные результаты == | ||
Нотация. Эмпирическая энтропия | |||
Пусть s – строка над алфавитом S = {a1, ..., ah}. Обозначим для каждого ai 2 S за ni количество вхождений ai в s. Эмпирическая энтропия нулевого порядка строки s определяется как H0(s) = - £?=1(M,7|S|) log(ni/jsj), где все алгоритмы берутся по основанияю 2, а 0 log 0 = 0. Хорошо известно, что H0 представляет собой максимальный уровень сжатия, которого можно достичь при использовании уникального декодируемого кода, в котором каждому символу алфавита назначается уникальное кодовое слово. Более высокой степени сжатия можно достичь, если кодовое слово символа зависит от k символов, следующих за ним (то есть от его контекста).2 Определим ws как строку единичных символов, непосредственно предшествующих вхождениям w в s. Например, для s = bcabcabdca получим cas = bbd. Значение | |||
(1) | |||
= 1 X jwsjH0(w | |||
w2 | |||
представляет эмпирическую энтропию k-го порядка для s и является нижней границей степени сжатия, которой можно достичь при использовании кодовых слов, которые зависят только от k символов, непоследственно следующих за кодируемым. | |||
2 Большинство алгоритмов сжатия данных обычно рассматривают контекст, предшествующий кодируемым символам. В данном описании используется нестандартный «прямой» контекст для упрощения нотации в последующих разделах. Работа с «прямым» контекстом эквивалентна работе с традиционным «обратным» контекстом для обращенной строки s (подробнее см. в [3]). | |||
Пример 1 Пусть строка s = mississippi. Для k = 1 имеем is = mssp, ss = isis, ps = ip. Следовательно, | |||
4 4 2 | |||
H1(s) = 4 H0(mssp) + 4 H0(isis) + 2 H0(ip) | |||
6 11 | |||
4 11 | |||
2 11 | |||
12 11 | |||
Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для s = an имеет место sj Hk(s) = 0 для любого k > 0. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [ ] было введено понятие модифицированной эмпирической энтропии нулевого порядка H*(s), имеющей следующее свойство: s\H*(s) по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. Модифицированная эмпирическая энтропия k-го порядка H* определяется как максимальная степень сжатия, которой можно достичь при просмотре не более чем k символов, следующих за кодируемым. | |||
== Преобразование Барроуза-Уилера == | |||