Реалізація ідеї арифметичного кодування

1. Вступ.

Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено.

В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, 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] Ймовірності представляються в моделі як цілочиселені лічильники частот, а накопичувані частоти зберігаються в масиві 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 =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 (i0) {

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.

Зміст.

1. Вступ.

2. Ідея арифметичного кодування.

3. Програма для арифметичного кодування.

3.1 Алгоритм арифметичного кодування.

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 Кодування довільно розподілених цілих чисел.

Додаток 1. Доведення декодуючої нерівності.

Додаток 2. Робочий код для адаптивного арифметичного стискання.

Література.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать