Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Классификация стратегий моделирования

Перед рассмотрением контекстных методов моделирования следует сказать о классификации стратегий моделирования источника данных по способу по­строения и обновления модели. Выделяют 4 варианта моделирования:

■ статическое;

■ полуадаптивное;

■ адаптивное (динамическое);

■ блочно-адаптивное.

При статическом моделировании для любых обрабатываемых данных-
используется одна и та же модель. Иначе говоря, не производится адаптация;
модели к особенностям сжимаемых данных. Описание заранее построенной,
модели хранится в структурах данных кодера и декодера; таким образом;
достигается однозначность кодирования, с одной стороны, и отсутствие не-i
обходимости в явной передаче модели, с другой. Недостаток подхода также;
очевиден: мы можем получать плохое сжатие и даже увеличивать размер;
представления, если обрабатываемые данные не соответствуют выбранной;
модели. Поэтому такая стратегия используется только в специализирован-i
ных приложениях, когда тип сжимаемых данных неизменен и заранее из-;
вестей. j

Полуадаптивное сжатие является развитием стратегии статического мо-i делирования. В этом случае для сжатия заданной последовательности выби-j рается или строится модель на основании анализа именно обрабатываемых; данных. Понятно, что кодер должен передавать декодеру не только закодированные данные, но и описание использованной модели. Если модель выбирается из заранее созданных и известных как кодеру, так и декодеру, то это просто порядковый номер модели. Иначе если модель была нас­троена или построена при кодировании, то необходимо передавать либо значения параметров настройки, либо модель полностью. В общем случае полуадаптивный подход дает лучшее сжатие, чем статический, так как обес­печивает приспособление к природе обрабатываемых данных, уменьшая ве­роятность значительной разницы между предсказаниями модели и реаль­ным поведением потока данных.

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

Блочно-адаптивное моделирование можно рассматривать как частный случай адаптивной стратегии (или наоборот, что сути дела не меняет). В за­висимости от конкретного алгоритма обновления модели, оценки вероят­ностей символов, метода статистического кодирования и самих данных из­менение модели после обработки каждого символа может быть сопряжено со следующими неприятностями:

■ потерей устойчивости (робастности) оценок, если данные "зашумлены", или имеются значительные локальные изменения статистических взаи­мосвязей между символами обрабатываемого потока; иначе говоря, че­ресчур быстрая, "агрессивная" адаптация модели может приводить к ухудшению точности оценок;

■ большими вычислительными расходами на обновление модели (как при­мер - в случае адаптивного кодирования по алгоритму Хаффмана);

■ большими расходами памяти для хранения структур данных, обеспечи­вающих быструю модификацию модели.

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

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