Автор: Шелвин, <sh@compression.ru>
Харьков, Украина, 29 февраля 2004 года в 14:38:48
В ответ на : Бинарный поиск в алгоритме арифметического декодирования от Мимошёл
в 28 февраля 2004 года в 20:56:48:
> сам собой напрашивается бинарный поиск
> (aka метод деления отрезка пополам).
> Но ни в одной из реализаций я его не нашёл.
> Неужто я первый до этого додумался? %)Плохо смотрел. Впрочем, бинарный
поиск действительно не так уж
распространен - его использовал только
я в ранних (ассемблерных) версиях и
В.Семенюк.
http://compression.ru/sh/clddemo.rar
http://compression.ru/sh/vs4.rar
http://compression.ru/sh/aridemo6.rar А фишка в том, что если таблицу
символов хранить отсортированной
по убыванию вероятностей
(или mtf-рангам, не суть важно),
то, в типичных случаях, кодер
работает быстрее (не говоря уже
о том, что в контекстных моделях
бинарный вариант вообще менее
эффективен): ──────────────────────────────────────────────────────
CODER MODEL Enc.Time Dec.Time Sum.Time Code Size
──────────────────────────────────────────────────────
Schindler o0c_v0 2790A4CC 3A979584 62283A50 1,853,543
Schindler o0c_v1 178508A7 1ECBDDB1*3650EC58*1,776,555
Schindler o0c_v2 285A9991 4FBD239D 7817BD2E 1,764,692
Schindler o0c_vs4 19325C3B 239B72DC 3CCDCF17 1,765,271
──────────────────────────────────────────────────────
(*) Best in column About models:
- o0c_v0 (array), o0c_v1 (MtF-array), o0c_v2 (array,order(-1)) (c) D.Shkarin
- o0c_vs4 (binary tree) (c) V.Semenyuk Данные из aridemo5.rar, время
в шестнадцатиричных процессорных
тактах ;)
|