Преимущества алгоритма расширяющегося префикса нагляднее всего видны при сжатии графических данных. Локально адаптированный характер алгоритма позволяет сжимать изображение к меньшему количеству бит, чем самоэнтропия, измеренная у статичного источника. В итоге, простая модель Маркова, применяемая в алгоритме расширяющегося префикса, часто позволяет осуществить лучшее сжатие, чем широко используемый алгоритм Зива-Лемпела на сопоставимом объеме памяти. Алгоритмы арифметического сжатия данных могут выполняться за время O(H ) при использовании дерева накапливаемых частот, балансируемого эвристическим расширением для требуемой алгоритмом статистической модели. Это создает новое ограничение, поэтому простой эвристический метод помещения в начало ( move -to-front ) является более эффективным для маленьких типовых алфавитов(4). И алгоритм расширяющегося префикса, и использование расширения для управления деревом накапливаемых частот служат полезными иллюстрациями применения расширения для управления лексикогpафически неупорядоченными деревьями. Идея поворота, предваряющего расширение дерева, может найти применение и в нелексикографических деревьях, равно как и понятие полуобоpота для балансировки таких деревьев. Например, их можно применять для слияния, пpи использовании двоичного дерева с 2-я путями слияния для построения n-путевого слияния. У Сарасвата уже появлялись подобные идеи при разработке средств слияния деревьев на Прологе[7]. Интересно отметить, что по сравнению с другими адаптивными схемами сжатия, потеря здесь 1 бита из потока сжатых данных является катастрофой! Поэтому pешение проблемы восстановления этой потери представляет несомненный интерес, что кроме того предполагает возможность использования таких схем сжатия в криптографии. Хорошо известно, что сжатие сообщения перед его шифровкой увеличивает трудность взламывания кода просто потому, что поиск кода основан на избыточности информации в зашифрованном тексте, а сжатие сокращает это излишество. Новая возможность, представленная в описанных здесь алгоритмах сжатия, состоит в использовании начального состояния дерева префикса кодов или начального состояния дерева накапливаемых частот в качестве ключа для прямого шифрования в процессе сжатия. Алгоритм арифметического сжатия может кроме того усложнить работу взломщика кодов тем, что границы букв не обязательно находятся также и между битами. Ключевое пространство для такого алгоритма шифрования огромно. Для n букв алфавита существует n! перестановок на листьях каждого из C деревьев, содержащих n - 1 внутренних узлов, где C = ( 2i )! / i! ( i+1 )! есть i-ое число Каталана. Это произведение упрощается к ( 2( n-1 ) )! / ( n-1 )!. Для n = 257 ( 256 букв с символом end-of-file конца файла ) это будет 512!/256! или что-то меньшее 2 . Компактное целое представление ключа из этого пространства будет занимать 675 байт, поэтому несомненно такие большие ключи могут поставить в тупик. На практике одно из решение будет заключаться в начале работы с уже сбалансированным деревом, как и в рассмотренном здесь алгоритмах сжатия, а затем расширении этого дерева вокруг каждого символа из ключевой строки, предоставленной пользователем. Вpяд ли они будет вводить ключи длиной 675 байт, хотя, чтобы позволить расширению установить дерево во все возможные состояния, нужны ключи еще длиннее чем этот, но даже короткий ключ может позволить осуществить шифрование на приемлемом уровне. -----------------------------------------------------------------------------(1) Такие алгоритмы являются без помех. В этой статье алгоpитмы с помехами или приближенные не рассматриваются.(2) В [9] в случае тройственной реализации необходим лишний бит на узел, чтобы отличать только левого наследника от только правого, но поскольку дерево кодов префикса целиком двоичное, этот бит здесь не нужен.(3) Перемены в кодовых стандартах позволяют массиву иметь индексы от 0 до 255 вместо от 1 до 256, что ведет к экономию памяти в обоих алгоритмах.(4) Алистер Моффэт из мельнбургского университета независимо достиг тех же ре зультатов используя СД выведенную из имплицитной груды подобного материала.

http://algolist.manual.ru