Нека например имаме следната последователност от символи:

00000000000000000000000000000000

00000000111111111111110000000000

00000001111111111111111000000000

00000011111111111111111000000000

00000011111111111111111000000000

00000011111111111111110000000000

00000011111111111111100000000000

00000011111110000000000000000000

00000011111110000000000000000000

00000011111110000000000000000000

00000011111111111100000000000000

00000011111111111111000000000000

00000011111111111111100000000000

00000011111111111111110000000000

00000001111111111111110000000000

00000000111111111111111000000000

00000000000000001111111000000000

00000000000000001111111000000000

00000000000000000111111000000000

00000000000000000111111000000000

00000000000000000111111000000000

00000000000000001111111000000000

00000001111100011111111000000000

00000011111111111111111000000000

00000011111111111111110000000000

00000001111111111111110000000000

00000001111111111111100000000000

00000000111111111111000000000000

00000000001111111000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

Имаме 2 възможни символа - 0 и 1. Ако преброим единиците и нулите в горното изображение ще получим:
336 единици и 688 нули, (общо са 1024).
Ако с помощта на тази статистика сметнем вероятностите за срещане на 0 и 1 ще получим:
вероятност на 0: f0=688/1024=0.671875
вероятност на 1: f1=336/1024=0.328125
Тогава можем да кодираме всяка 0 с -log2(0.671875)=0.57373524529790206 бита, а всяка единица с -log2(0.328125)=1.60768257722123970 бита. (вероятността да срещнем единица е по-малка и затова за нея "изразходваме" повече битове) За кодиране на цялото изображение ще ни трябват общо: 688*0.57373524529790206 + 336*1.60768257722123970 =(приблизително) 935 бита. (т.е. по този начин ще компресираме изображението, състоящо се от 1024 символа 0 или 1 с помощта на 935 бита, възползвайки се от факта че вероятностите на нулата и единицата са различни. Ако бяха равни, т.е. 0.5 щяхме да имаме -log2(0.5)=1 бит за нулата и -log2(0.5)=1 бит за единицата, т.е. 1024 бита, и никаква компресия. Колкото по-различни са вероятностите на нулата и единицата, толкова по-добре.
Ето как работи аритметичното кодиране: инициализираме: A := 0 B := 1 Повтаряме следното: Разглеждаме числовия интервал [A;B) (т.е. A включително, B невключително, говорим само за реални числа) Разделяме този интервал на K части: (където K е броят на различните символи, в случая K=2) [A;L1) [L1;L2) [L2;L3) ... [Lk-1;B) такива че големините им са пропорционални на вероятностите на символите. Например в частния случай за K=2 имаме само 2 подинтервала [A;L) и [L;B) и то такива че големините им (L-A и B-L) са пропорционални на вероятностите на нулата и единицата (f0 и f1). Според това какъв е символът на входа, който ще кодираме избираме или първия или втория интервал. (при K възможни символа- един от K-те интервала, според това кой от тези K символа имаме на входа) И на променливите A и B присвояваме границите на интервала който сме избрали. ....докато има още символи на входа. Когато входният поток от символи свърши имаме 2 реални числа A и B, (между 0 и 1) и във изходния файл трябва да запишем реално число, което е в интервала [A;B) (с необходимата точност). Оказва се че за да го запишем (например като двоична дроб) са ни необходими точно толкова битове колкото сметнахме по-горе. 1.5 Huffman Кодирането на Хъфман е може би най-известният алгоритъм за вероятностно кодиране. Има го обяснен навсякъде и няма да се впускам в подробности, но само ще спомена, че той дава кодиране с цяло_число_брой_битове за символ, т.е. най-доброто приближение на -log2(f) до цяло число. Когато възможните символи са много хъфмановото кодиране се справя не много по-лошо от аритметичното и се предпочита заради това че се реализира по-лесно и работи по-бързо (при аритметичното има проблеми от загуба на точност, скорост на кодиране/декодиране и освен това алгоритъмът е патентован в САЩ (доколкото знам от обща култура :-) ) и заради това се използва рядко) Когато символите са 2 (нула и единица) хъфмановото кодиране кодира и двата символа с по 1 бит, каквито и да са им вероятностите, и винаги се получават 1024 бита, т.е. безполезен е за нашите цели. Ето защо моята програма използва *само* аритметично кодиране. 2. Намиране на контурите Нека извършим следната операция над картинката дадена по-горе: по редове: записваме 0 ако съответната клетка е равна на предишната и 1 ако е различна.
Получава се следното:

00000000000000000000000000000000

00000000100000000000001000000000

00000001000000000000000100000000

00000010000000000000000100000000

00000010000000000000000100000000

00000010000000000000001000000000

00000010000000000000010000000000

00000010000001000000000000000000

00000010000001000000000000000000

00000010000001000000000000000000

00000010000000000010000000000000

00000010000000000000100000000000

00000010000000000000010000000000

00000010000000000000001000000000

00000001000000000000001000000000

00000000100000000000000100000000

00000000000000001000000100000000

00000000000000001000000100000000

00000000000000000100000100000000

00000000000000000100000100000000

00000000000000000100000100000000

00000000000000001000000100000000

00000001000010010000000100000000

00000010000000000000000100000000

00000010000000000000001000000000

00000001000000000000001000000000

00000001000000000000010000000000

00000000100000000000100000000000

00000000001000000100000000000000

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

Операцията е обратима, очевидно, и броят на единиците намалява доста сериозно- имаме 58 единици и 966 нули.
Ако това нещо го кодираме по описаният начин ще ни трябват:
f0=966/1024=0.943359375
f1=58/1024=0.056640625
bits0=-log2(f0)=0.08412062116422684
bits1=-log2(f1)=4.14201900487242790
bits_total=966*bits0 + 58*bits1=322 322 бита, сериозно подобрение, близо 3 пъти! Моята програма винаги компресира *това* изображение. 3. По-добър вероятностен модел По-горе използвахме една и съща вероятност навсякъде: f1=(брой_единици/общ брой символи) А не можем ли да използваме различна вероятност според "контекста", т.е. горе съвсем ясно се вижда че където има единица и на следващия ред под нея също е много вероятно да има единица. Аз на всяка точка от картинката съпоставям число, равно на разстоянието до най-близката единица от предния ред - число между 0 и 31 или числото 32, ако на предния ред изобщо няма единици или няма предишен ред, т.е. сме си на първия ред. Например кодирали сме следното:

00000000000000000000000000000000

00000000100000000000001000000000

00000001000000000000000100000000

00000010000000000000000100000000

00000010000000000000000100000000

00000010000000000000001000000000

00000010000000000000010000000000

00000010000001000000000000000000

00000010000001000000000000000000

00000010000001000000000000000000

00000010000000000010000000000000

00000010000000000000100000000000

000000*

..предстои да кодираме звездичката, *но* преди това намираме на какво разстояние от горния ред е най-близката единица (в случая на разстояние 0-единицата е точно над нея) и си казваме разстояние 0, значи сега е много вероятно да има единица. Всъщност имаме си таблица на вероятността да има единица според разстоянието до най-близката единица от горния ред. Специално за картинката по-горе тя изглежда така:

f1[ 0]= 0.66379310344827586

f1[ 1]= 0.18260869565217391

f1[ 2]= 0.02654867256637168

f1[ 3]= 0.02020202020202020

f1[ 4]= 0.02222222222222222

f1[ 5]= 0.01111111111111111

f1[ 6]= 0.02325581395348837

f1[ 7]= 0.03225806451612903

f1[ 8]= 0.03448275862068966

f1[ 9]= 0.05882352941176471

f1[10]= 0.00000000000000000

.........

f1[31]= 0.00000000000000000

f1[32]= 0.03125000000000000

CODE.EXE прави статистика на нулите и единиците във всеки от 32-те случая и попълва вероятностите. За да може да бъде обратно декодирано изображението е необходимо да запишем във файла и самата таблица f1[0..32]. Тя представлява някаква характерна особеност на шрифта а не на отделната цифра, т.е. когато вземем различни цифри от един шрифт, тази таблица е почти една и съща и затова я изчисляваме и използваме за всички цифри които кодираме, като я записваме само веднъж във NUM.COD. Още повече лесно се забелязва че повечето вероятности в таблицата са малки числа близки до 0 и много от тях не са важни, т.е. влияят много слабо на степента на компресия, всъщност значещи се оказват само първите 5-6 и последната - f1[32], затова записвам само тях, като цялата таблица отнема само 30 бита ;-). 4. Симетрия В много шрифтове цифрите 0, 1, 3 и 8 са симетрични и програмата ми се възползва от това. Една цифра се брои за симетрична, ако разликите между двете огледални половини са <=16, тогава записвам спрямо коя права (хоризонтална или вертикална) е симетрията и само половината от изображението. Търся също и т.нар. четворна симетрия, при която е достатъчно да запиша една четвърт от изображението и която се среща много често при нулата и при единицата. 5. Загуба на точност при аритметичното кодиране, Escape-кодове и др. Понеже компресирам максимум 10240 бита, а вероятностите ми са цяло_число/1024 и ползвам 102400 битова аритметика, никога не страдам от загуба на точност. Не ползвам Escape кодове, нито код за край на файла, тъй като предварително знам колко бита трябва да кодирам/декодирам: = брой_на_уникалните_цифри_в_числото*1024, (без да се има предвид симетрията, но стига подробности :-) ). 6. Компресиране на последователността от цифри Освен изображенията на 10-те цифри трябва да се запише и N-цифрено число, N<=1000. Тъй като за него нямаме никаква информация, се предполага че то ще е случайна последователност от цифри и няма да може да се компресира. Все пак моята програма опитва да го компресира с аритметично кодиране (10 символно) или със Burrows-Wheeler Transformation -> Lift To Front -> аритметично кодиране, в общи линии, алгоритмите с които работи програмата bzip2 с тази разлика че при нея вместо аритметично се използва хъфманово кодиране.