В.Семенюк Приложение к адаптивному арифметическому кодировщику нулевого порядка Пока я расскажу про order-0 adaptive arithmetic model и его реализации. Итак, идея состоит в том, чтобы проинициализировать множество счетчиков повеления символов единицами, а потом после обработки очередных символов добавлять к ним некий INC. Почему INC, а не 1? Для того, чтобы быстро снизить роль инициализации, которая в представленной форме оправдана только при равновероятном появлении символов. Почему бы не сделать INC очень большим? Так как есть ограничение на totFreq. Рано или поздно нам надо производить масштабирование значений счетчиков (я уже не говорю про то, что масштабирование способствует адаптации, что очень сильно повышает эффективность). Чем меньше INC, тем реже мы это делаем и тем выше производительность. Далее возникает вопрос: как научиться быстро вычислять cumFreq? Если просто каждый раз суммировать значения счетчиков, то при размере алфавита N в среднем понадобится N/2 сложений. Но стоп! Это в среднем, а на практике все зависит от того, какие символы встречаются чаще, а какие реже. Если те, которые встречаются чаще, находятся в начале массива счетчиков, нам потребуется меньше операций суммирования. Значит, логично перемещать часто появляющиеся счетчики в начало массива. Эта идея легла в основу шкаринской реализации. Ее недостаток состоит в том, что, если символы появляются с примерно одинаковой частотой, операция перемещения может оказаться бесполезной. Но это не главный недостаток. При равномерном появлении символов количество суммирований будет по-прежнему оцениваться как N/2. Надо как-то сократить это число. Здесь есть несколько подходов. Наиболее очевидный - разделить символы по порядку следования в массиве счетчиков на группы. Каждой группе необходимо сопоставить групповой cumFreq. При вычислении обычной cumFreq надо к групповой cumFreq (группа соответствует обрабатываемому символу) добавить freq-и символов, находящихся в группе до обрабатываемого символа. При увеличении значения счетчика появления символа следует увеличить cumFreq-и всех групп, которые находятся после группы, которой принадлежит обработанный символ. Пример. Пусть N = 256, кол-во групп - 16, кол-во элементов в группе - 16. При обработке очередного символа нам потребуется примерно 8-9 сложений для определения cumFreq и где-то 8 для обновления cumFreq-ов групп. Всего - примерно 16-17 сложений. Развивая этот подход, можно пойти несколько дальше. Сначала можно разделить массив на две группы, потом каждую группу еще на две и т. д. Интуитивно понятно, что это более прогрессивный подход. Однако, к сожалению, условия его реализации могут наложить существенные ограничения. Я, как можно заметить, предпочел именно такое решение. Как можно его усовершенствовать? Можно попытаться совместить данный подход со шкаринским. Как? Например, можно выбирать оптимальную реализацию модели в зависимости от обрабатываемой информации. Можно еще размещаться символы в порядке, наиболее соответствующем особенностям архитектуры переходов процессора и т. п. В общем еще процентов 30 отыграть можно, но, скорее всего, не более. Это что касается адаптивного подхода. Существует еще так называемый полуадаптивный подход, сущность которого я излагал недавно в эхе [RU.COMPRESS] (это другая модель). Ясно, что если ансамбль оценок вероятностей появления символов определен заранее и не меняется, скорость возрастает в разы. Однако, естественно, страдает эффективность. Майкл [Шиндлер] в связи с этим предлагает использовать квазиадаптивный подход. При таком подходе обновление ансамбля происходит не на каждом шаге, а через M шагов, где M само может адаптивно меняться. Да, совсем забыл. Еще имеется проблема поиска символов по накопленным частотам при декодировании. Тут подходы полностью аналогичны предложенным.