Київський національний університет ім. Тараса Шевченка
факультет кібернетики
кафедра теорії та технології програмування
Реалізація ідеї арифметичного кодування.
Курсова робота
студента четвертого курсу
Шевченка Андрія
Науковий керівник
доц. Зубенко В.В.
Київ – 2004
Зміст.
1. Вступ.........................................................................................стр.3
2. Ідея арифметичного кодування. стр. 5
3. Програма для арифметичного кодування. стр. 7
3.1 Алгоритм арифметичного кодування. стр. 8
3.2 Алгоритм арифметичного декодування.
4. Зауваження до реалізації.
4.1 Прирощувані передача і отримання інформації.
4.2 Бажане використання цілочисленої арифметики.
4.3 Ефективна реалізація моделі.
5. Реалізація моделі.
6. Доведення правильності декодування.
7. Проблема переповнення і завершення кодування.
7.1 Від’ємне переповнення.
7.2 Переповнення.
7.3 Завершення кодування.
8. Моделі для арифметичного кодування.
8.1 Фіксовані моделі.
8.2 Адаптивна модель.
9. Ефективність стискання.
10. Застосування арифметичного кодування.
10.1 Кодування чорно – білих зображень.
10.2 Кодування довільно розподілених цілих чисел.
11. Висновки стр. 13
Додаток 1. Доведення декодуючої нерівності.
Додаток 2. Робочий код для адаптивного арифметичного стискання.
Література. стр. 22
Вступ.
Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено.
В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації.
Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифрування. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску, - ентропії вхідного потоку.
2. Ідея арифметичного кодування.
При арифметичному кодуванні текст представляється числами з плаваючою комою в інтервалі від 0 до 1. В процесі кодування тексту інтервал, що його відображає – зменшується, а кількість бітів для його представлення збільшується. Наступні символи тексту зменшують величину інтервала, виходячи з значень їх ймовірностей, які визначаються моделлю. Більш ймовірні символи роблять це в меншій мірі ніж менш ймовірні та, таким чином, додають менше бітів до результату.
Перед початком роботи відповідний до тексту інтервал є [0 ; 1). При обробці наступного символу його ширина звужується за рахунок виділення цьому символу частини інтервалу. Наприклад, застосуемо до тексту “еаіі!” алфавіта {а, е, і, о, u, ! } модель з постійними ймовірностями, що задані в таблиці 1.
Таблиця 1. Приклад постійної моделі для алфавіта {а, е, і, о, u, ! }.
Символ
Ймовірність
Інтервал

А
0,2
[0,0; 0,2)

Е
0,3
[0,2; 0,5)

І
0,1
[0,5; 0,6)

О
0,2
[0,6; 0,8)

У
0,1
[0,8; 0,9)

!
0,1
[0,9; 1,0)


І кодувальнику, і декодувальнику відомо, що на самому початку інтервал є [0; 1). Після перегляду першого символу “е”, кодувальник звужує інтервал до [0,2; 0,5), який модель виділяє цьомк символу. Другий символ “а” звузить цей новий інтервал до першої його п’ятої частина, оскільки для “а” виділено фіксований інтервал [0,0; 0,2). В результаті отримаємо робочий інтервал [0,2; 0,26), бо попередній інтервал мав ширину в 0,3 одиниці та одна п’ята від нього є 0,06. Наступному символу “і” відповідає фіксований інтервал [0,5; 0,6), що застосовно до робочого інтервалу [0,2; 0,26) звужує його до інтервалу [0,23; 0,236). Продовжуючи таким саме способом маємо:
На початку
[0.0; 1.0 )

Після перегляду “е”
[0.2; 0.5 )

Після перегляду “а”
[0.2; 0.26 )

Після перегляду “і”
[0.23; 0.236 )

Після перегляду “і”
[0.233; 0.2336 )

Після перегляду “!”
[0.23354; 0.2336 )

Припустимо, що все те, що декодувальник знає про текст, це кінцевий інтервал [0,23354; 0,2336). Він відразу ж зрозуміє, що перший закодований символ – це “е”, тому що підсумковий інтервал цілком лежить в інтервалі, що був виділений цьому символу відповідно до Таблиці 1. Тепер повторимо дії кодувальника:
Спочатку
[0.0; 1.0 )

Після перегляду “е”
[0.2; 0.5 )


Звідси зрозуміло, що другий символ – це “а”, оскільки це призведе до інтервалу [0,2; 0,26), який цілком містить в собі підсумковий інтервал [0,23354; 0,2336). Працюючи в такий спосіб, декодувальник витягує весь текст.
Декодувальник не має потреби знати значення обох меж підсумкового інтервалу, який був одержаний від кодувальника. Навіть одного значення, що лежить всередині нього, наприклад, 0,23355 вже достатньо. (Інші числа – 0,23354, 0,23357 та навіть 0,23354321 – цілком придатні). Однак, щоб завершити процес, декодувальнику потрібно своєчасно розпізнати кінець тексту. Крім того, одне й те саме число 0,0 можна представити і як “а”, і як “аа”, і як “ааа” і т. д. Для усунення непорозуміння ми повинні позначати завершення кожного тексту спеціальним символом EOF, що відомий і кодувальнику, і декодувальнику. Для алфавіту з таблиці 1 з цією метою, і тільки з нею, буде використовуватися символ “!”. Коли декодувальник зустрічає цей символ, то він завершує свій процес.
Для фіксованої моделі, яка задається моделлю таблиці 1, ентропія 5-ти символьного тексту “еаіі!” буде –log 0,3 – log 0,2 – log 0,1 – log 0,1 – log 0,1 = – log 0,00006 ( 4,22. (Тут застосовуємо логариф з основою 10, бо вищенаведене кодування виконувалося для десяткових чисел). Це пояснює, чому потрібно 5 десяткових цифр для кодування цього тексту. Таким чином, ширина підсумкового інтервалу є 0,2336 – 0, 23354 = 0,00006, а ентропія – від’ємний десятковий логарифм цього числа. Звичайно ми працюємо з двійковою арифметикою, передаємо двійкові числа та вимірюємо ентропію в бітах.
П’яти десяткових цифр здається забагато для кодування тексту з чотирьох голосних! Мабуть не зовсім вдало бу закінчувати приклад розгортанням, а не зтисканням. Однак зрозуміло, що різні моделі дають різну ентропію. Краща модель, побудована на аналізі окремих символів тексту “еаіі!”, є така множина частот символів: {“е” (0,2), “а” (0,2), “і” (0,4), “!” (0,2) }. Вона дає ентропію, що дорівнює 2,89 в десятковій системі відліку, тобто кодує вихідний текст числом з трьох цифр. Однак, більш складні моделі, як відмічалося раніше, дають в загальному випадку набагато кращій результат.
3. Програма для арифметичного кодування.
На рисунку 1 показано фрагмент псевдокоду, який поєднує процедури кодування та декодування, які було викладено в попередньому розділі. Символи в ньому нумеруються як 1, 2, 3… Частотний інтервал для і-того символу задається від cum_freeq[i] до cum_freeq[i-1]. При зменшенні і cum_freeq[i] зростає так, що cum_freeq[0] = 1. (Причина такого “зворотнього” договору полягає в тому, що cum_freeq[0] буде потім містити нормалізуючий множник, який зручно зберігати на початку масиву). Поточний робочий інтервал задається в [low; high] і буде в самому початку дорівнювати [0; 1) і для кодувальника, і для декодувальника.
На жаль, цей псевдокод значно спрощений, тоді як в практичному застосуванні існує декілька чинників, які ускладнюють і кодування, і декодування.
3.1 Алгоритм арифметичного кодування.
/*З кожним наступним символом тексту звертатися */
/*до процедури encode_symbol() */
/*Перевірити, що термінальний символ закодований останнім*/
/*Вивести одержане значення інтервалу [low; high) */
encode_symbol(symbol, cum_freq)
range = high – low
high = low + range*cum_freq[symbol - 1]
low = low + range*cum_freq[symbol]
3.2 Алгоритм арифметичного декодування.
/* Value – це число, яке одержано на вхід*/
/*Звертання до процедури decode_symbol() до того моменту*/
/*поки вона не поверне термінальний символ*/
decode_symbol(cum_freq)
пошук такого символу, що
cum_freq[symbol] <= (value - low) / (high - low) < cum_freq[symbol - 1]
/*це забезпечує розміщення Value в межах нового інтервалу*/
/*[low; high], що відображено в завершенні програми*/
range = high – low
high = low + range*cum_freq[symbol - 1]
low = low + range*cum_freq[symbol]
return symbol
Рисунок 1. Псевдокод арифметичного кодування та декодування.
4. Зауваження до реалізації.
4.1 Прирощувані передача і отримання інформації.
Наведений алгоритм кодування нічого не передає до повного завершення кодування всього тексту, а також і декодувальник не починає цей процес, поки не отримає стиснений текст цілком. Для більшості випадків необхіден поетапний режим виконання .
4.2 Бажане використання цілочисленої арифметики.
Потрібна для представлення інтервалу [low; high] точність зростає разом з довжиною тексту. Поетапне виконання допомагає вирішити цю проблему, але вимагає при цьому уважного обліку можливого переповнення та від’ємного переповнення.
4.3 Ефективна реалізація моделі.
Реалізація моделі повинна мінімізувати час визначення наступного символу алгоритмом декодування. Крім того, адаптивні моделі повинні також мінімізувати час, який вимагається для підтримання накопичених частот.
5. Реалізація моделі.
Сама реалізація буде обговорюватися в наступному розділі, а тут треба лише торкнутися тільки інтерфейсу з моделлю. Як відомо, байт представляє собою ціле число від 0 до 255 (тип char). Тут ми представляємо байт як ціле число від 1 до 257 включно (тип index), де EOF трактується як 257-й символ. Було б добре відсортувати модель в порядку зменшення частот для мінімізації кількості виконання циклу декодування. Перетворення з типу char в index, та навпаки, реалізовано за допомогою двох таблиць – index_to_char[] i char_to_index[]. В адаптивній моделі виконується перекодування, яке присвоює найчастішим символам маленькі індекси.
Ймовірності представляються в моделі як цілочиселені лічильники частот, а накопичувані частоти зберігаються в масиві cum_freq[]. Як і в попередньому випадку, цей масив – “зворотній”, і лічильник загальної частоти, який використовується для нормалізації всіх частот, розміщується в cum_freq[0]. Накопичувані частоти не повинні перевищувати встановленний в Max_frequency максимум, а реалізація моделі повинна запобігати переповненню відповідним маштабуванням. Необхідно також принаймні на 1 забезпечити різницю між двома сусідними значеннями cum_freq[], в противному випадку символ, що переглядається, не буде переданий.
6. Доведення правильності декодування.
Перевіримо правильність визначення процедурою decode_symbol() наступного символу. З псевдокоду на рисунку 1 зрозуміло, що decode_symbol() повинна використовувати Value для пошуку символа, який при кодуванні скоротив робочий інтервал так, що він продовжує включати в себе Value. В робочій програмі в decode_symbol() визначається такий символ, для якого:
cum_freq [symbol] ( (((value – low +1)*cum_freq [0]–1)/(high – low + 1) ( < cum_freq [symbol - 1], де ( ( означає операцію взяття цілої частини – ділення з відкиданням дробової частини. Показано, що це передбачає:
low + ( ((high - low + 1)*cum_freq [symbol]) / cum_freq [0] ( ( value ( low + ( ((high – low +1)*cum_freq [symbol - 1]) / cum_freq [0](, таким чином, що value належить новому інтервалу, який вираховується процедурою decode_symbol(). Це гарантує коректність визначення кожного символу операцієй декодування.
7. Проблема переповнення і завершення кодування.
7.1 Від’ємне переповнення.
Як показано в псевдокоді, аріфметичне кодування працює за допомогою масштабування накопичених ймовірностей, які надаються моделю в інтервалі [low; high] для кожного символу, що передається. Припустимо, що low i high так близькі один до одного, що операція масштабування призводить одержані від моделі різні символи до одного цілого числа, яке входить в [low; high]. В такому випадку подальше кодування продовжувати неможливо. Тому кодувальник повинен слідкувати за тим, щоб інтервал [low; high] завжди був досить широким. Найпростішим засобом для цього є забезпечення ширини інтервалу не меншей Max_frequency – максимального значення суми всіх накопичуваних частот.
Проблема від’ємного переповнення розглядається тільки відносно кодувальника, тому що при декодуванні кожного символу процес крокує за операцієй кодування, і від’мне переповнення не виникне, якщо виконується таке саме масштабування з тими ж самими умовами.
7.2 Переповнення.
Тепер розглянемо можливість переповнення при цілочисленому множенні. Переповнення не виникне, якщо добуток range*Max_frequency вміщується в ціле слово, бо накопичені частоти не можуть перевищувати Max_frequency. Range має найбільше значення в Top_Value + 1, тому максимально можливий добуток є 2^16*(2^14 – 1), яке менше 2^30. Для визначення code_value та range використаний тип long, щоб забезпечити 32-х бітову точність арифметичних обчислень.
7.3 Завершення кодування.
При завершені процесу кодування необхідно послати унікальний термінальний символ (EOF-символ), а потім послати достатню кількістьбітів для гарантії того, що закодований рядок потрапить в підсумковий робочий інтервал. Через те, що процедура done_encoding() може бути “впевнена”, що low i high обмежені або так, що:
low < First_qtr < Half ( high, або
low < Half < Third_qtr ( high,
то значенню треба передати 01 або 10 відповідно, для видалення невизначеності, яка залишилась. Таким чином EOF унікально визначається останніми переданими бітами.
8. Моделі для арифметичного кодування.
Програма повинна працювати з моделлю, яка являє собою пару перекодуючих таблиць index_to_char [] i char_to_index [], і масив накопичених частот cum_freq []. До останнього масиву висуваються такі вимоги:
сum_freq [i – 1] ( cum_freq [i];
Ніколи не робиться спроба кодувати символ і, для якого сum_freq [i – 1] = cum_freq [i];
сum_freq [0] ( Max_frequency.
Якщо ці умови виконуються, значення в масиві не повинні мати зв’язку з дійснтми значеннями накопичених частот символів тексту. І декодування, і кодування будуть працювати коректно, при чому останньому буде треба менше місця, якщо частоти точні.(Згадаємо успішне кодування “еаіі!” у відповідності до моделі з таблиці 1, як, взагалі, не відображає справжньої частоти в тексті).
8.1 Фіксовані моделі.
Найпростішою моделлю є така модель, в якій частоти символів постійні. Модель з таблиці 1 задає постійні частоти символів для алфавіту {a, e, i, u, o, !}. Для стиску англійських текстів можна використати частоти з частини Свода Брауна. Процедура ініціалізації start_model () просто підраховує накопичену версію цих частот, спочатку ініціалізувавши таблиці перекодування. Швидкість виконання процесу кодування та декодування можна прискорити, якщо ці таблиці перевпорядкувати так, щоб найвживаніші символи розміщувалися на початку масиву cum_freq []. Через те, що модель є постійною, процедура update_model () буде просто пустою.
Строгою моделлю є така модель, в якій частоти символів тексту точно відповідають специфікації моделі. Наприклад, фіксована модель з програми близька до строгої моделі для деякого фрагмента з Свода Брауна, звідки її було взяти. Однак, для того, щоб бути істино строгою, її символи в цьому фрагменті, які не з’являються, повинні мати лічильники, що дорівнюють 0, а не 1 (і при цьому “жертвувати” можливостями вхідних текстів, які містять ці символи). Крім того, лічильники не повинні масштабуватися до заданої накопиченої частоти, як це зроблено в програмі. Взагалі, строга модель повинна бути вирахована й передана перед пересиланням власне тексту. Клірі і Уітнен показали, що при загальних умовах це не дасть загального покращення стиску порівняно з описаним нижче адаптивним кодуванням.
8.2 Адаптивна модель.
Вона змінює частоти вже знайдених в тексті символів. Спочатку всі лічильники можуть бути рівними, що відображує відсутність початкових даних, але при перегляді кожного вхідного символу вони змінюються, наближуючись до спостережуваних частот. І кодувальник, і декодувальник використовують однакові початкові значення (наприклад, рівні лічильники) і один і той самий алгоритм оновлення, що дозволить їх моделям завжди залишатися на одному рівні. Кодувальник отримує наступний символ, кодує його та змінює модель. Декодувальник з’ясовує наступний символ на основі своєї поточної моделі, а потім оновлює її.
Програма демонструє таку адаптивну модель, що рекомендується для використання при стиску та відновленні, оскільки на практиці вона є кращою ніж фіксована модель за ефективністю стиску. Ініціалізація проводиться таким саме чином, як для фіксованої моделі, за виключенням того, що всі частоти встановлюються в нулі. Процедура update_model (symbol), викликається з encode_symbol () та decode_symbol () після обробки кожного символу.
Оновлення моделі є досить дорогим з причини необхідності підтримки накопичених сум. В програмі використані лічильники частот, які оптимально розміщені в масиві в порядку зменшення своїх значень, що є ефективним видом самоорганізованого лінійного пошуку. Процедура update_model () спочатку перевіряє нову модель на предмет перевищення нею обмежень за величиною накопиченої частоти, і якщо воно присутнє, то зменшує всі частоти діленням на 2, зважаючи при цьому на те, щоб лічильники не перетворилися в 0, і переобчислює накопичені значення. Потім, якщо це необхідно, update_model () перевпорядковує символи для того, щоб розмістити поточний в його вірній категорії відносно частотного порядку, чергуючи для відображення змін перекодувальні таблиці. В результаті, процедура збільшує значення відповідного лічильника частоти і впорядковує відповідні накопичені частоти.
9. Ефективність стискання.
Взагалі, при кодуванні тексту аріфметичним методом, кількість бітів в закодованому рядку дорівнює ентропії цього тексту відносно використаної для кодування моделі. Три чинника викликають погіршення цієї характеристики: видатки на завершення тексту; використання арифметики з кінцевою точністю; таке масштабування лічильників, що їх сума не перевищує Max_frequency.
Як було показано, жоден з них не є значним. В порядку виділення результатів арифметичного кодування, модель буде розглядатися як сувора (в визначеному вище сенсі).
Арифметичне кодування повинне досилати додаткові біти в кінець кожного тексту, здійснюючи таким чином додаткові зусилля на завершення тексту. Для ліквідації непорозуміння з останнім символом процедура done_encoding () посилає два біти. В випадку, коли перед кодуванням поток бітів має блокуватися в 8-бітові символи, буде необхідно завершувати до кінця блоку. Таке комбінування може додатково потрібувати 9 бітів.
Видатки при використанні арифметики з обмеженою точністю проявляються в зменшені залишків при діленні. Це видно при порівнянні з теоретичною ентропією, яка виводить частоти із лічильників, які таким саме чином масштабуються при кодуванні. Тут видатки незначні – порядку 10^-4 бітів / символ. Додаткові видатки на масштабування лічильників дещо більші, але все одно досить малі. Для коротких текстів (менших 2^14 байт) їх немає. Але навіть з текстами в 10^5 – 10^6 байтів накладні видатки, підраховані експериментально, складають менше 0,25% від рядка, шо кодується.
Адаптивна модель в програмі, при загрозі перевищення загальною сумою накопичених частот значення Max_frequency, зменшує всі лічильники. Це призводить до того, що зважувати останні події важче, ніж більш ранні. Таким чином, показники мають тенденцію прослідковувати зміни у вхідній послідовності, які модуть бути дуже корисними (відомі випадки, коли обмеження лічильників до 6-7 бітів давало кращі результати, ніж підвищення точності арифметики). Звичайно, це залежить від джерела, до якого застосовується модель.
10. Застосування арифметичного кодування.
10.1 Кодування чорно – білих зображень.
Застосування з цією метою арифметичного кодування розглядалося Лангдоном та Риссаненом, що отримали при цьому чудові результати за допомогою моделі, що використовує оцінку ймовірності колбору точки відносно деякого шаблону, що її оточує. Він являє собою сукупність з 10 точок, що лежать зверху та спереду від поточної, тому при скануванні растру вони їй передують. Це дає 1024 можливих контексту, відносно яких, ймовірність чорного коліру в даній точці оцінюється адаптивно по мірі перегляду зображення. Після чого кожна полярність точки кодувалася арифметичним методом відповідно з цією ймовірністю. Такий підхід покращив стискання на 20 – 30% порівняно з більш ранніми методами. Для збільшення швидкості кодування Лангдон та Риссанен застосували приблизний метод арифметичного кодування, який обійшов операції множення шляхом представлення ймовірностей в вигляді цілих ступенів дробу 1/2/. Кодування Хаффмана для цього випадку не може бути використано напряму, оскільки воно ніколи не виконує стиснення двохсимвольного алфавіту. Іншу можливість для арифметичного кодування, що застосовується для такого алфавіту, дає популярний метод кодування довжин тиражів (run-length method). Модель тут приводить дані до послідовності довжин серій однакових символів (наприклад, зображення представляється довжинами послідовностей чорних точок, які йдуть за білими, які слідують за чорними, яким передують білим і т. д.). в результаті повинна бути передана послідовність довжин. Стандарт факсимільних апаратів ССІТТ будує код Хаффмана на основі частот, з якими чорні і білі послідовності різних довжин з’являються в зразках документів. Фіксоване арифметичне кодування, яке буде використовувати ті ж самі частоти, буде мати кращі характеристики, а адаптація таких частот для кожного окремого документу буде працювати ще краще.
10.2 Кодування довільно розподілених цілих чисел.
Воно часто розглядається на основі застосування більш складних моделей текстів, зображеняь або інших даних. Розглянемо, наприклад, локально адаптовану схему стискання Бентлі та ін., де кодування та декодування працює з N останніми різними словами. Слово, що знаходиться в кеш-буфері, визначається по цілочисельному індексу буфера. Слово, яке в ньому не знаходиться, передається в кеш-буфер через пересилання його маркера, який йде наступним за самими символами цього слова. Це чудова модель для тексту, в якому слова часто використовуються на протязі деякого короткого часу, а потім вже довго не використовуються. Їх стаття обговорює декілька кодувань змінної довжени вже для цілочисельних індексів кеш-буфера. В якості основи для кодів змінної довжини аріфметичний метод дозволяє використовувати будь-яке розподілення ймовірностей, в тому числі серед багатьох інших й ті, які навадені тут. Крім того, він допускає для індексів кеш-буфера застосування адаптивної моделі, що є бажаним у випадку, коли розподілення доступів до кеш-буферу важкопередбачуване.
11. Висновки
........................
Додаток 1. Доведення декодуючої нерівності.

Вважаємо:

або іншими словами:

де range = high – low + 1, (1)
(остання нерівність виразу (1) походить від того факту, що cum_freq[symbol - 1] повинне бути цілим). Потім ми хочемо показати, що low’ ( value ( high’, де low’ i high’ є оновлені значення для low i high як це визначено нижче.
(а) low’ :

З виразу (1) маємо: ,
тому low’ ( value, тому що і value, i low, i cum_freq [0] > 0.
(а) high:

З виразу (1) маємо:
.
Додаток 2. Робочий код для адаптивного арифметичного стискання.
Arithmetic_coding.h
/*Оголошення, необхідні для арифметичного*/
/*кодування та декодування*/
/*Інтервал значень арифметичного коду*/
#define Code_value_bits 16
typedef long code_value;
#define Top_value (((long) 1 << Code_value_bits) - 1)
/*Вказівники на середину і четверті інтервала значення коду*/
#define First_qtr (Top_value/4 + 1)
#define Half (2*First_qtr)
#define Third_qtr (3*First_qtr)
model.h
/* Інтерфейс з моделлю */
/* Множина кодуємих символів */
#define No_of_chars 256
#define EOF_symbol (No_of_chars + 1)
#define No_of_symbols (No_of_chars + 1)
/* Таблиці перекодування початкових та робочих символів */
int char_to_index[No_of_chars];
unsigned char index_to_char[No_of_symbols + 1];
/* Таблиця накопичених частот */
#define Max_frequency 16383
int cum_freq[No_of_symbols+1];
encode.c
/* Головна процедура кодування */
#include <stdio.h>
#include "model.h"
main()
{ start_model();
start_outputing_bits();
start_encoding();
for (;;) {
int ch; int symbol;
ch = getc(stdin);
if (ch==EOF) break;
symbol = char_to_index[ch];
encode_symbol(symbol,cum_freq);
update_model(symbol);
}
encode_symbol(EOF_symbol,cum_freq);
done_encoding();
done_outputing_bits();
exit(0);
}
Arithmetic_encode.c
/* Алгоритм арифметичного кодування */
#include "arithmetic_encoding.h"
static void bit_plus_follow();
/* Поточний стан кодування */
static code_value low, high;
static long bits_to_follow;
/* Початок кодування потока символів */
start_encoding()
{ low = 0;
high = Top_value;
bits_to_follow = 0;
}
/* Кодування символу */
encode_symbol(symbol,cum_freq)
int symbol;
int cum_freq[];
{ long range;
range = (long)(high-low)+1;
high = low + (range*cum_freq[symbol-1])/cum_freq[0]-1;
low = low + (range*cum_freq[symbol])/cum_freq[0];
for (;;) {
if (high<Half) {
bit_plus_follow(0);
}
else if (low>=Half) {
bit_plus_follow(1);
low -= Half;
high -= Half;
}
else if (low>=First_qtr && high<Third_qtr)
{ bits_to_follow +=1;
low -= First_qtr;
high -= First_qtr;
}
else break;
low = 2*low;
high = 2*high+1;
}
}
/* Завершення кодування потоку */
done_encoding()
{ bits_to_follow += 1;
if (low<First_qtr) bits_plus_follow(0);
else bit_plus_follow(1);
}
/* вивод біта разом з наступними за ним, оберненими до нього */
static void bit_plus_follow(bit)
int bit;
{ output_bit(bit);
while (bits_to_follow>0) {
output_bit(!bit);
bits_to_follow -= 1;
}
}
decode.c
/* Головна процедура для декодування */
#include <stdio.h>
#include "model.h"
main()
{ start_model();
start_inputing_bits();
start_decoding();
for (;;) {
int ch; int symbol;
symbol = decode_symbol(cum_freq);
if (symbol == EOF_symbol) break;
ch = index_to_char[symbol];
putc(ch,stdout);
update_model(symbol);
}
exit(0);
}


arithmetic_decode.c
/* Алгоритм арифметичного декодування */
#include "arithmetic_coding.h"
/* Потоковий стан декодування */
static code_value value;
static code_value low, high;
/* Початок декодування потока символів */
start_decoding();
{ int i;
value = 0;
for (i = 1; i<=Code_value_bits; i++) {
value = 2*value+input_bit();
}
low = 0;
high = Top_value;
}
/* Декодування наступного символа */
int decode_symbol(cum_freq)
int cum_freq[];
long range;
int cum;
int symbol;
range = (long)(high - low)+1;
cum = (((long) (value - low)+1)*cum_freq[0]-1)/range;
for (symbol = 1; cum_freq[symbol]>cum; symbol++);
high = low + (range*cum_freq[symbol-1])/cum_freq[0]-1;
low = low + (range*cum_freq[symbol])/cum_freq[0];
for (;;){
if (high<Half) {/*nothing*/}
else if (low>=Half)
{
value -= Half;
low -= Half;
high -= Half;
}
else if (low>=First_qtr && high<Third_qtr)
{
value -= First_qtr;
low -= First_qtr;
high -= First_qtr;
}
else break;
low = 2*low;
high = 2*high+1;
}
return symbol;
}

bit_input.c
/* Процедури вводу бітів */
#include <stdio.h>
#include "arithmetic_coding"
/* Бітовий буфер */
static int buffer;
static int bits_to_go;
static int garbage_bits;
/* Ініціацізація побітового вводу */
start_inputing_bits();
{ bits_to_go = 0;
garbage_bits = 0;
}
/* Ввод біта */
int input_bit();
{ int t;
if (bits_to_go==0) {
buffer = getc(stdin);
if (buffer==EOF) {
garbage_bits +=1;
if (garbage_bits>Code_value_bits-2) {
fprintf(stderr,"Bad input file\n");
exit(-1);
}
}
bits_to_go = 8;
}
t = buffer&1;
buffer >>= 1;
bits_to_go -= 1;
return t;
}

bit_output.c
/* Процедура виводу бітів */
#include <stdio.h>
/* Бітовий буфер */
static int buffer;
static int bits_to_go;
/* Ініціалізація бітового буфера */
start_outputing_bits()
{ buffer = 0;
bits_to_go = 8;
}
/* Вивід біта */
output_bit(bit)
int bit;
{ buffer >>=1;
if (bit) buffer |= 0x80;
bits_to_go -= 1;
if (bits_to_go==0) {
putc(buffer,stdout);
bits_to_go = 8;
}
}
/* Вимивання останніх бітів */
done_outputing_bits()
{ putc(buffer>>bits_to_go,stdout);
}
adaptive_model.c
/* Модель з адаптивним джерелом */
#include "model.h"
int freq[No_of_symbols+1];
/* Ініціалізація моделі */
start_model()
{ int i;
for (i = 0; i<No_of_chars; i++) {
char_to_index[i] = i+1;
index_to_char[i+1] = i;
}
for (i = 0; i<No_of_symbols; i++) {
freq[i] = 1;
cum_freq[i] = No_of_symbols - i;
}
freq[0] = 0;
/* Оновлення моделі у відповідності з новим символом */
update_model(symbol)
int symbol;
{ int i;
if (cum_freq[0]==Max_frequency) {
int cum;
cum = 0;
for (i = No_of_symbols; i>=0; i--) {
freq[i] = (freq[i]+1)/2;
cum_freq[i] = cum;
cum += freq[i];
}
}
for (i = symbol; freq[i]==freq[i-1];i-- );
if (i<symbol) {
int ch_i, ch_symbol;
ch_i = index_to_char[i];
ch_symbol = index_to_char[symbol];
index_to_char[i] = ch_symbol;
index_to_char[symbol] = ch_i;
char_to_index[ch_i] = symbol;
char_to_index[ch_symbol] = i;
}
freq[i] += 1;
while (i>0) {
i -= 1;
cum_freq[i] += 1;
}
}

Література.
Rubin F. Arithmetic stream coding using fixed precision registers, IEEE Transactions IT-25, #6, Nov79, pp. 672 – 675.
Кричевский Р. Е. Сжатие и поиск информации., Москва, 1989 г.
Кохманюк Д. Сжатие информации: как это делаеться., IndexPRO, Киев, №№1,2.