Як було показано, жоден з них не є значним. В порядку виділення результатів арифметичного кодування, модель буде розглядатися як сувора (в визначеному вище сенсі).

Арифметичне кодування повинне досилати додаткові біти в кінець кожного тексту, здійснюючи таким чином додаткові зусилля на завершення тексту. Для ліквідації непорозуміння з останнім символом процедура 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 останніми різними словами. Слово, що знаходиться в кеш-буфері, визначається по цілочисельному індексу буфера. Слово, яке в ньому не знаходиться, передається в кеш-буфер через пересилання його маркера, який йде наступним за самими символами цього слова. Це чудова модель для тексту, в якому слова часто використовуються на протязі деякого короткого часу, а потім вже довго не використовуються. Їх стаття обговорює декілька кодувань змінної довжени вже для цілочисельних індексів кеш-буфера. В якості основи для кодів змінної довжини аріфметичний метод дозволяє використовувати будь-яке розподілення ймовірностей, в тому числі серед багатьох інших й ті, які навадені тут. Крім того, він допускає для індексів кеш-буфера застосування адаптивної моделі, що є бажаним у випадку, коли розподілення доступів до кеш-буферу важкопередбачуване.

Додаток 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

/*