Арифметичне кодування - один з алгоритмів ентропійного стиснення.

На відміну від алгоритму Гоффмана, не має жорсткого постійної відповідності вхідних символів - групам біт вихідного потоку. Це дає алгоритмом велику гнучкість в поданні дрібних частот зустрічальності символів.

Як правило, перевершує алгоритм Хаффмана по ефективності стиску, дозволяє стискати дані з ентропією, меншою 1 біта на кодований символ, але деякі версії мають патентні обмеження від компанії IBM. [1]


1. Характеристики

Забезпечує майже оптимальну ступінь стиснення з точки зору ентропійної оцінки кодування Шеннона. На кожен символ потрібно майже H біт, де H - інформаційна ентропія джерела.

На відміну від алгоритму Хаффмана, метод арифметичного кодування показує високу ефективність для дрібних нерівномірних інтервалів розподілу ймовірностей кодованих символів. Однак у випадку рівноймовірно розподілу символів, наприклад для рядка біт 010101 ... 0101 довжини s метод арифметичного кодування наближається до префіксних кодом Хаффмана і навіть може займати на один біт більше. [1]


2. Принцип дії

Нехай є якийсь алфавіт, а також дані про частотність використання символів (опціонально). Тоді розглянемо на координатній прямій відрізок від 0 до 1.

Назвемо цей відрізок робочим. Розташуємо на ньому точки таким чином, що довжини утворених відрізків будуть рівні частоті використання символу, і кожен такий відрізок буде відповідати одному символу.

Тепер візьмемо символ з потоку і знайдемо для нього відрізок серед щойно сформованих, тепер відрізок для цього символу став робочим. Розіб'ємо його таким же чином, як розбили відрізок від 0 до 1. Виконаємо цю операцію для деякого числа послідовних символів. Потім виберемо будь-яке число з робочого відрізка. Біти цього числа разом з довжиною його бітової запису і є результат арифметичного кодування використаних символів потоку.


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

3.1. Імовірнісна модель

Використовуючи метод арифметичного кодування, можна досягти майже оптимального представлення для заданого набору символів і їх ймовірностей (згідно теорії ентропійного кодування джерела Шеннона оптимальне представлення буде прагнути до числа-log 2 P біт на кожен символ, ймовірність якого P). Алгоритми стиснення даних, що використовують у своїй роботі метод арифметичного кодування, перед безпосереднім кодуванням формують модель вхідних даних на підставі кількісних або статистичних характеристик, а також, знайдених в кодованого послідовності повторень або патернів - будь додаткової інформації, що дозволяє уточнити ймовірність появи символу P в процесі кодування. Очевидно, що чим точніше визначена або передвіщена ймовірність символу, тим вища ефективність стиснення.

Розглянемо найпростіший випадок статичної моделі для кодування інформації, що надходить з системи обробки сигналу. Типи сигналів і відповідні їм ймовірності розподілені наступним чином:

  • 60% вірогідність нейтрального значення сигналу або NEUTRAL.
  • 20% вірогідність позитивного значення сигналу або POSITIVE.
  • 10% вірогідність негативного значення сигналу або NEGATIVE.
  • 10% вірогідність ознаки кінця кодованого послідовності або END-OF-DATA.

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

Слід також відзначити, що в якості алфавіту ймовірнісної моделі методу можна розглядати будь-який набір символів, виходячи з особливостей розв'язуваної задачі. Більше евристичні підходи, що використовують основну схему методу арифметичного кодування, застосовують динамічні або адаптивні моделі. Ідея даних методів полягає в уточненні ймовірності кодованого символу за рахунок обліку ймовірності попереднього або майбутнього контексту (тобто, ймовірність появи кодованого символу після певного k-го числа символів зліва чи справа, де k - це порядок контексту).


3.2. Кодування повідомлення.

3.3. Декодування повідомлення

На діаграмі представлено декодування підсумкового інтервального значення 0.538 згідно моделі в наведеному прикладі. Область інтервалу розбивається на подінтервальние області згідно імовірнісним характеристикам появи відповідних символів. Потім, черговий обраний інтервал розбивається аналогічним способом.

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

Початковий стан процесу декодування збігається з процесом кодування і розглядається інтервал [0,1). На підставі відомої ймовірнісної моделі дробове значення 0.538 потрапляє в інтервал [0, 0.6). Це дозволяє визначити перший символ, який був обраний кодувальником, тому його значення виводиться як перший символ декодованого повідомлення.



Примітки

  1. Історія розвитку теорії стиснення інформації - www.compression.ru / arctest / descript / comp-hist.htm