Базовые стратегии сжатия

Базовых стратегий сжатия три:

1. Преобразование потока ("Скользящее окно-словарь").

Описание посту­пающих данных через уже обработанные. Сюда входят LZ-методы для потоков "слов", т. е. когда комбинации поступающих элементов предска­зуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wavelet Transform - для потоков "элементов", т. е. когда не имеет смысла рас­сматривать комбинации длиной два и более элемента или запоминать эти комбинации, как в случае Linear Prediction Coding.

Никаких вероятностей, в отличие от второй стратегии, не вычисляет­ся. В результате преобразования может быть сформировано несколько потоков. Даже если суммарный объем потоков увеличивается, их струк­тура улучшается и последующее сжатие можно осуществить проще, бы­стрее и лучше.

2. Статистическая стратегия.

а) Адаптивная (поточная). Вычисление вероятностей для поступаю­щих данных на основании статистики по уже обработанным данным.
Кодирование с использованием этих вычисленных вероятностей. Семей­ство РРМ-методов - для потоков "слов", адаптивные варианты методов Хаффмана и Шеннона - Фано, арифметического кодирования - для по­токов "элементов". В отличие от первого случая, давно собранная стати­ стика имеет тот же вес, что и недавняя, если метод не борется с этим специально, что гораздо сложнее, чем в случае LZ. Кроме того, считают­ся вероятными все комбинации, даже те, которые еще не встречались в потоке и скорее всего никогда не встретятся.

б) Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические варианты методов Хаффмана, Шеннона - Фанои арифметического кодирования - для потоков "элементов". Статиче­ское СМ - для "слов".

3. Преобразование блока. Входящие данные разбиваются на блоки, кото­рые затем трансформируются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков ("BlockSorting''-методы: ST, BWT, PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразова­ния, Enumerative Coding.

Как и при первой стратегии, в результате могут формироваться не­сколько блоков, а не один. Опять же, даже если суммарная длина блоков не уменьшается, их структура значительно улучшается и последующее сжатие происходит проще, быстрее и лучше.

Резюмируя одним предложением: метод сжатия может быть или стати­стическим, или трансформирующим и обрабатывать данные либо поточно, либо блоками, причем

■ чем больше и однороднее данные и память¹, тем эффективнее блочные методы;

■ чем меньше и неоднороднее данные и память, тем эффективнее поточ­ные методы;

■ чем сложнее источник, тем сильнее улучшит сжатие оптимальная преоб­разование;

■ чем проще источник, тем эффективнее прямолинейное статистическое решение (математические модели "источник Бернулли" и "источник Маркова").