·17·08·2000·····15·05·2002···············································
Эвристики арифметического кодирования
·········································································
1. Что такое арифметическое кодирование
2. Чисто ari'шые эвристики
3. Примеры
4. Библиография
·········································································
· if (sym == Stats->Symbol)
· {
· rc.Encode(0, Stats->Freq, SummFreq);
· Stats->Freq += 8;
· SummFreq += 8;
· return;
· }
········································
- Д. Шкарин
1. Что такое арифметическое кодирование
Частотное кодирование вообще, как я его понимаю, есть попытка перену-
меровать все файлы, имеющие данную таблицу частот символов и записать
вместо данного файла его номер.
Для бинарного случая, как я показал в 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, то этого никто не заметит. ;-),
разница в размере кода будет не всегда и в худшем случае на несколько
бит).
[Btw, по поводу сравнения ari и ark см. mark#1/text/notables.txt]
·········································································
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 ду-
мать тоже не нужно.
·········································································
3. Примеры
_Мои_ кодеры написаны на ассемблере. Некоторые люди говорят, что ас-
семблер трудно читать :). Поэтому пусть читают субботинский же кодер из
coder.hpp, содержащегося в исходниках ppmd v.F by Dmitry Shkarin. Впро-
чем, я его немножко переделал, для понятности :)
#define TOP (1<<24)
#define BOT (1<<16)
void Encode (uint cumFreq, uint freq, uint totFreq)
{
rng /= totFreq
low += cumFreq * rng;
rng *= freq;
hai = low + rng
// проверить, не слишком ли мал rng; если да - workaround переноса
if (low^hai>=TOP && rng<BOT) rng = (low | (BOT-1)) - low;
// зафиксировался байт?
while (low^hai<TOP)
{
// выбрасываем старший байт, совпадающий в Low и Hai
OutByte(low>>24);
// перемещаем "плавающую точку"
rng<<=8, low<<=8;
}
}
void Decode (uint cumFreq, uint freq, uint totFreq)
{
rng /= totFreq;
low += cumFreq * rng;
rng *= freq;
if (low^hai>=TOP && rng<BOT) rng = (low | (BOT-1)) - low;
while (low^hai<TOP)
{
// передвигаем отрезок кода, используемый для предсказания символов
code = code<<8 | InByte();
rng<<=8, low<<=8;
}
}
Впрочем, эвристика9: (моя, вроде бы) при делении теряется информация;
во избежание деление рекомендуется всегда выполнять _после_ всех умноже-
ний в формуле. Все виденные мною арифметические кодеры же относятся к
этому правилу наплевательски, т.к. результат предварительного умножения
может не поместиться в разрядную сетку используемого типа данных. Таков
практический вред от применения языков программирования высокого уровня
- ассемблерная команда MUL _всегда_ вычисляет результат с удвоенной раз-
рядностью операндов. А команда DIV ей в пару выполняет деление двойного
слова, содержащегося в двух регистрах, на одинарное. Но на ЯВУ, соблюдая
портабельность, этим воспользоваться нельзя, увы :).
Такие дела. :)
·········································································
4. Библиография
1. ark1.doc
http://compression.graphicon.ru/sh/ark1.rar
2. mark#1, демонстрационная упаковка мультисимвольного Ark-кодера.
http://compression.graphicon.ru/sh/mark1.rar
3. Исходники компрессора PPMD Дмитрия Шкарина
ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmde.rar
(coder.hpp по Шиндлеру)
ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdf.rar
(coder.hpp по Субботину)
4. Исходники order0 и order1 rangecoder'ов Дмитрия Шкарина
http://compression.graphicon.ru/sh/aridemo0.rar
5. Исходники (и пояснительный текст) order0-кодера Владимира Семенюка.
http://compression.graphicon.ru/sh/vs4.rar
·········································································