Что такое арифметическое кодирование

Частотное кодирование вообще, как я его понимаю, есть попытка перену-
меровать все файлы, имеющие данную таблицу частот символов и записать
вместо данного файла его номер.
Для бинарного случая, как я показал в ark1.doc, существует вполне
прямолинейный способ это сделать. Надо сказать, в не дошедший до
ru.compress "полный комплект" этой текстовки входила программка на асме,
которая упаковывала блок размером где-то в 768 битов, пользуясь длинной
арифметикой. Но это непрактично.
Напомню алгоритм: существует ровно F(a,b)=(a+b)!/a!/b! последова-
тельностей битов, имеющих таблицу частот {0:a;1:b}. Т.е., все такие пос-
ледовательности можно перенумеровать числами в интервале [0..F(a,b)).
Таким же образом известно, что таких последовательностей с нулевым пер-
вым битом ровно F(a-1,b), из чего следует, что можно присвоить последо-
вательностям 0... интервал [0..F(a-1,b)), а 1... - интервал
[F(a-1,b)..F(a,b)) и это не будет ничему противоречить. Очевидно, что
этот процесс можно легко продолжить и получить полный номер последова-
тельности, а не интервал. И обратить этот процесс столь же просто.
Но для прямого воплощения вышеописанного требуется длинная арифмети-
ка, применять которую мы себе позволить не можем. Поэтому эвристика1:
принципиально важным свойством функции F(a,b) является лишь то, чтобы
F(a,b) не было меньше суммы F(a-1,b) и F(a,b-1) - это требуется для од-
нозначного декодирования. Таким образом, мы можем рассчитать аппроксима-
цию "правильной" функции, имеющую нужную разрядность мантиссы. Скажем,
можно просто так и вычислять F(a,b) как сумму F(a-1,b) и F(a,b-1) с ок-
руглением вверх. Это уже позволяет применять данный алгоритм практически
- точности, обеспечиваемой таблицей F(x,y), помещающейся в 64k вполне
достаточно для сжатия, очень близкого к обеспечиваемого традиционной
реализацией битового арифметического кодера.
Существует и альтернативный вариант реализации вышеописанного, не
требующий таблиц. Дело в том, что из F(a,b) мы можем получить F(a-1,b)
путем умножения на (a) и деления на (a+b). Аналогично и F(a,b-1). А что-
бы не пересекались интервалы [0..F(a-1,b)) и [F(a-1,b)..F(a,b)) мы можем
просто взять в них округления F(a,b)*a/(a+b) в разные стороны.
Вот. Только вот, как ни печально, последнее уже называется не ark (c)
Eugene D. Shelwien, а "арифметическое кодирование" (c) IBM и черт знает
кто еще :).
Ari, таким образом, - это всего лишь способ эвристической _комбина-
торной_ нумерации блоков данных, имеющих одинаковые таблицы частот.
Впрочем, есть и маленькое отличие/упрощение - эвристика2: если заменить
первоначальный коэффициент F(a,b) на 1, то этого никто не заметит. ;-),
разница в размере кода будет не всегда и в худшем случае на несколько
бит).

2. Чисто ari'шые эвристики

Теперь, пожалуй, можно расписать, как приблизительно выглядит арифме-
тический кодер. Только, пожалуй, сразу "нормальный", а не бинарный.
Бинарность, вообще-то, потребовалась мне больше для упрощения. Ну, кроме
того, таблицу мультиномиальных коэффициентов даже для трехсимвольного
алфавита помещать абсолютно некуда :). Тем не менее,
F(a1,...,aI-1,...,aN) все так же равно F(a1,...,aN)*aI/Sum(aX,x=1..N),
так что:

// нижняя граница интервала кодового пространства, соответствующего
// уже закодированному отрезку данных
low = 0
// вместо F(a1,...,aN). Всегда можно успеть на него домножить ;).
rng = 1 ;
T = SymbolNumber
for all c = SourceChar
L = low(c)
R = freq(c)
hai = low + int(rng*(L+R)/T) // (Я _знаю_, как пишется high :)
low = low + int(rng*L/T) + 1
rng = hai - low
freq(c)--, T--
next c

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

int(rng*low(x))+1 <= low-DecodeLow < int(rng*(low(x)+freq(x))

Эвристика3: поскольку разрядность границ этого интервала все равно
фиксированная, то можно их сравнивать лишь с соответствующим числом
старших бит low - остальные ничего не изменят.
Эвристика4: rng никогда не возрастает, только убывает. Кроме того,
понятно, что если старшие биты low и hai совпадают, то в low они уже ни-
когда не изменятся. А поскольку во все формулы они входят лишь аддитив-
но, то их свободно можно хранить отдельно :).
Тем не менее, не все так просто, как кажется. Ari присущ неприятный
эффект, которого ark избегает за счет более свободного подбора коэффи-
циентов (они должны лишь удовлетворять неравенству; не обязательно
должна быть возможность получать их один из другого) - переносы в low.
Т.е., вполне реальна такая ситуация, что low не совпадает с hai ни в од-
ном бите, хотя точность rng уже упала ниже допустимых пределов. Для ре-
шения этой проблемы применяется
Эвристика5: (стандартная) старшие биты low можно все же отбрасывать,
но наличие несовпадения все же учитывать. Фишка в том, что если сдвинуть
старшие биты low в выходной поток несмотря на то, что они не совпадают с
hai, то весьма вероятно, что через некоторое время возникнет ситуация,
когда low+rng>maxint :). Конечно же, возникнет бит переноса, который на-
до будет куда-то девать. Так вот, стандартное средство для этого случая
- кэшировать непрерывную последовательность единичных битов (и один ноль
перед ними), выдвинутую из low непосредственно перед этим и инвертиро-
вать ее (ноль менять на единицы, а единицы - на нули) при возникновении
переноса. В общем, обычный эффект сложения - перенос не идет дальше бли-
жайшего нулевого бита. С одной стороны, запрограммировать такое кэширо-
вание не очень сложно. Но с другой, смысла в этом нет, т.к. существует
Эвристика6: (хочу знать, кто придумал; я увидел у Субботина) можно
просто так срезАть rng, чтобы перенос _не возникал_ :). Действительно,
делать rng меньше можно когда нам удобно - лишь бы в декодере можно было
делать это синхронно; работоспособности алгоритма это не повредит. Таким
образом, если мы хотим несколько старших бит low записать в выходной по-
ток (т.к. rng уже слишком уменьшился), то достаточно просто проследить,
чтобы в них _не происходил_ перенос, пересчитав при необходимости значе-
ние rng соответствующим образом.
Эвристика7: (моя собственная :) можно совместить #5 и #6, т.к. приме-
нение #6 самой по себе заметно портит коэффициент сжатия на некоторых
данных. Т.е., просто закэшировать несколько старших байт low, уже как бы
"закодированных" и выполнять отсечение rng только в случае, если перенос
проходит еще дальше. Надо сказать, что при достаточной точности вычисле-
ний отсечение практически не требуется. Так, мой кодер CL-A с 32 бит на
low и rng и 32 бит "кэша" low таких отсечений требовал лишь около пяти
штук даже на pic из Calgary Corpus, весьма этому эффекту способствующем.
Последний же кодер CL-F на FPU с 64-битной точностью (64+24 на low и 64
на rng) поймать на выполнении отсечения мне пока не удалось :). А, ну и
Эвристика8: (Shindler's rangecoder) если дожидаться, пока не зафикси-
руются старшие _восемь_ (а не один, как в традиционном ari) бит low, то
с битами кодеру работать не придется и насчет операций битового i/o ду-
мать тоже не нужно.

Powered by Drupal - Design by artinet