Re: Бинарный поиск в алгоритме арифметического декодирования


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Шелвин, <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, время
в шестнадцатиричных процессорных
тактах ;)

Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.