Реферат: Сжатие данных

Деление интервала легко осуществляется посредством накопления вероятностей

каждой буквы алфавита и ее предшественников. Дан сжатый текст 0.6 (

представленный в виде десятичной дроби ), тогда первой его буквой должна быть D,

потому что это число лежит в интервале [ 0.5, 1 ). Пересчет дает результат:

( 0.6 - 0.5 ) / 0.5 = 0.2

Второй буквой будет B, т.к. новая дробь лежит в интервале [ 0.125, 0.25 ).

Пересчет дает:

( 0.2 - 0.125 ) / 0.125 = 0.6.

Это значит, что 3-я буква есть D, и исходный текст при отсутствии информации о

его длине, будет повторяющейся строкой DBDBDB ...

Первоочередной проблемой здесь является высокая точность арифметики для

понимания и опеpиpования со сплошным битовым потоком, каковым выглядит сжатый

текст, рассматриваемый в качестве числа. Эта проблема была решена в 1979 году.

Эффективность сжатия методом статичного арифметического кодирования будет равна

H , только при использовании арифметики неограниченной точности. Но и

ограниченной точности большинства машин достаточно, чтобы позволять осуществлять

очень хорошее сжатие. Целых переменных длиной 16 битов, 32-битовых произведений

и делимых достаточно, чтобы результат адаптивного арифметического сжатия лежал в

нескольких процентах от предела и был едва ли не всегда немного лучше, чем у

оптимального адаптированного кода Хаффмана, предложенного Уитером.

Как и в случае кодов Хаффмана, статичные арифметические коды требуют двух

проходов или первоначального знания частот букв. Адаптированные арифметические

коды требуют эффективного алгоритма для поддержания и изменения информации о

бегущей и накапливаемой частотах по мере обработки букв. Простейший путь для

этого - завести счетчик для каждой буквы, увеличивающий свое значение на единицу

всякий раз, когда встречена сама эта буква или любая из следующих после нее в

алфавите. В соответствии с этим подходом, частота буквы есть разница между

числом ее появлений и числом появлений ее предшественников. Этот простой подход

может потребовать O(n) операций над буквой n-арного алфавита. В реализованном на