Розділ 5   АРИФМЕТИЧНЕ КОДУВАННЯ

 

Алгоритми Шеннона-Фано і Хаффмена в найкращому випадку не можуть кодувати кожний символ повідомлення менш ніж одним бітом інформації. Припустимо, що в повідомленні з 0 та 1 одиниці трапляються в 10 разів частіше. Ентропія такого повідомлення (що визначає верхню границю стиснення даних) HX≈0,469 (біт/сим) суттєво менше одиниці, тому кодування таких повідомлень оптимальними алгоритмами буде не достатньо ефективним. У таких випадках бажано використовувати алгоритми, що дозволяють кодувати символи повідомлення менш ніж 1 бітом інформації. Одним із найкращих таких алгоритмів є алгоритм арифметичного кодування.

За розподілом ймовірностей дискретної випадкової величини (далі д. в. в.) складається таблиця з пересічних в граничних точках відрізків для кожного із значень д. в. в. Об'єднання цих відрізків утворює інтервал [0; 1], а їхні довжини пропорційні ймовірностям значень д. в. в.

Алгоритм кодування полягає в побудові інтервалу, що однозначно визначає конкретну послідовність значень д. в. в. Інтервали повідомлення будуються так. Якщо є відрізок повідомлення завдовжки n-1 символів, то для побудови відрізка повідомлення завдовжки n попередній інтервал розбивається на стільки частин, скільки можливих значень має д. в. в. Для знаходження початку і кінця нового інтервалу повідомлення до початку попереднього інтервалу необхідно додати значення добутків його ширини на відповідні границі відрізка поточного нового символу з таблиці символів і їхніх інтервалів (таблиці кодера). З отриманих інтервалів вибирається той, що відповідає конкретному повідомленню завдовжки n символів.

Для побудованого таким чином інтервалу повідомлення знаходиться число, що належить цьому відрізку, як правило, це ціле число, розділене на мінімальний степінь 2. Це дійсне число і буде кодом даного повідомлення. Усі можливі коди - це числа, строго більші 0 і менші 1, тому лідируючий 0 і десяткову крапку можна не враховувати.

У міру надходження символів повідомлення його інтервал звужується, відповідно кількість розрядів, необхідна для подання інтервалу збільшується. Більш імовірні символи меншою мірою звужують інтервал, ніж менш імовірні, і, отже, додають менше розрядів до результату.

Основна відмінність арифметичного кодування від алгоритмів Шеннона-Фано і Хаффмена полягає в його неперервності, тобто відсутності необхідності блокування повідомлення. Ефективність арифметичного кодування зростає із зростанням довжини повідомлення, проте й потребує значно більших обчислювальних ресурсів. Пояснимо ідею арифметичного кодування на прикладах.

Приклад 1  Закодуємо за арифметичним алгоритмом рядок «МАТЕМАТИКА». 

Алфавіт повідомлення містить такі символи: {М, А, Т, Е, И, К}. Знайдемо частоту кожного з цих символів у повідомленні і призначимо кожному з них відрізок, довжина якого визначається імовірністю відповідного символу (табл. 2.7).

                Таблиця 2.7

Символ  Імовірність            Інтервал

М            0,2           [0; 0,2)

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

Т             0,2           [0,5; 0,7)

Е             0,1           [0,7; 0,8)

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

К             0,1           [0,9; 1,0)

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

Після надходження першого символу повідомлення «М» кодер звужує початковий інтервал [0; 1) до нового [0; 0,2). Отже, після надходження першої букви результат кодування знаходитиметься в інтервалі [0; 0,2).

Наступний символ «А» кодується підінтервалом усередині інтервалу попередньої послідовності символів повідомлення, звужуючи цей інтервал до [0,04; 0,1) (верхня і нижня границі нового інтервалу знаходяться додаванням до початку попереднього інтервалу добутків його ширини на відповідні границі відрізка, що відповідає поточному символу повідомлення в таблиці кодера (табл. 2.7)), таким чином, нижня границя інтервалу повідомлення «МА» lowi=0+0,2*0,2=0,04; а верхня – highi=0+0,2*0,5=0,1).

Наступний символ, що надходить на вхід кодера, - це буква «Т». Символу «Т» відповідає інтервал [0,5; 0,7) з таблиці кодера (табл. 2.7). Стосовно вже наявного інтервалу послідовності з попередніх букв повідомлення новим інтервалом буде [0,07; 0,082) (lowi=0,04+0,06*0,5=0,07; highi=0,04+0,06*0,7=0,082).

Послідовність інтервалів, відповідних процесу кодування повідомлення «МАТЕМАТИКА» за арифметичним алгоритмом, зручно подати у вигляді такої таблиці (табл. 2.8).

Таблиця 2.8

Символ – інтервал                Інтервал повідомлення        Ширина інтервалу

М -  [0; 0,2)            [0; 0,2)    0,2

А - [0,2; 0,5)          [0,04; 0,1)               0,06

Т - [0,5; 0,7)           [0,07; 0,082)           0,012

Е - [0,7; 0,8)           [0,0784; 0,0796)     0,0012

M - [0; 0,2)             [0,0784; 0,07864)   0,00024

А - [0,2; 0,5)          [0,078448; 0,07852)              0,7210-4

Т - [0,5; 0,7)           [0,078484; 0,0784984)          0,14410-4

И - [0,8; 0,9)          [0,07849552; 0,07849696)    0,14410-5

К - [0,9; 1,0)           [0,078496816; 0,07849696)  0,14410-6

А - [0,2; 0,5)          [0,0784968448; 0,078496888)              0,43210-7

 

Остаточний результат кодування повідомлення «МАТЕМАТИКА» - це дійсне число, що належить інтервалу [0,0784968448; 0,078496888). Це число знаходиться як частка від ділення цілого числа на мінімальний степінь 2 - це . Степінь 2 визначає розрядність коду повідомлення.

Отже, двійковий 24-розрядний код числа 131625910 = =0001010000011000010111112 і є арифметичним кодом даного повідомлення:

Code(МАТЕМАТИКА)=00010100000110000101111.

Довжина коду L(X)=24 (біт).

Середня довжина коду (біт/сим).

Приклад 2  Д. в. в. може набувати два значення – 0 і 1 з ймовірностями відповідно 2/3 і 1/3. Побудуємо арифметичний код для повідомлень завдовжки 3 символи.

Коди за арифметичним алгоритмом для всіх можливих повідомлень завдовжки 3 символи для заданої д. в. в. подаються такою таблицею (табл. 2.9):

Таблиця 2.9

Повідомлення та  їх інтервали            Код         pi

1              [2/3; 1)   

11           

[8/9; 1)    111          [26/27; 1]  31/32              11111      1/27

                                                               110          [8/9; 26/27]  15/16           1111        2/27

                              

10           

[2/3; 8/9) 101          [22/27; 8/9]  7/8               111          2/27

                                                               100          [2/3; 22/27]  3/4               11            4/27

0              [0; 2/3)   

01           

[4/9; 2/3) 101          [16/27; 2/3]  5/8               101          2/27

                                                               100          [4/9; 16/27]  1/2               1              4/27

                              

00           

[0; 4/9]    001          [8/27; 4/9]  3/8  011          4/27

                                                               000          [0; 8/27]  1/4     01            8/27

                Середня довжина коду  =(51+42+32+24+32+14+34+28)=0,8025 (біт/сим).

Наведемо процедуру кодування за арифметичним алгоритмом (у наближеному варіанті):

Set low to 0.0

Set high to 1.0

While there are still input symbols do

    get an input symbol

    code_range = high - low.

    high = low + code_range*high_range(symbol)

    low = low + code_range*low_range(symbol)

End of While

output low

Декодеру, як і кодеру, відома таблиця розподілу інтервалів символів алфавіту. Декодування арифметичного коду повідомлення здійснюється за таким алгоритмом:

Крок 1  За таблицею інтервалів символів алфавіту визначається відрізок, що містить значення поточного коду, - і за цим інтервалом з тієї самої таблиці однозначно визначається символ повідомлення. Якщо це маркер кінця повідомлення, то кінець, інакше - перехід до кроку 2.

Крок 2  Від поточного коду віднімається нижня границя його інтервалу. Різниця ділиться на довжину цього інтервалу. Отримане значення вважається новим значенням поточного коду. Перехід до кроку 1.

Приклад 3  Довжина повідомлення 10 символів, його арифметичний код 0001010000011000010111112= 131625910. Символи і інтервали повідомлення наведені у табл. 2.7. Розкодуємо це повідомлення. 

Дійсне число, яке належить інтервалу, що однозначно визначає закодоване повідомлення 0,07849687. Це число є значенням поточного коду. З таблиці символів і інтервалів (табл. 2.7) визначається відрізок, якому належить це число, - [0; 0,2) і відповідно, що перший закодований символ – це «М».

Виключимо з результату декодування вплив тепер відомого символу «М»: для цього віднімемо від поточного коду нижню границю інтервалу розкодованого символу і розділимо отриманий результат на ширину цього інтервалу, тобто наступне значення поточного коду = 0,39248435. Це число належить відрізку [0,2; 0,5), що відповідає символу «А» (табл.2. 7), отже, другим символом декодованої послідовності буде «А».

Виключимо з отриманого інтервалу [0,2; 0,5) вплив букви «А». Для цього віднімемо від поточного коду нижню границю цього інтервалу і розділимо на його ширину: =0,6416145. Результат належить відрізку [0,5; 0,7) символу «Т» - це черговий декодований символ і т. д., поки не декодуємо всі символи (табл. 2.10).

Таблиця 2.10

Декодоване число Символ на виході Інтервал Ширина інтервалу

0,07849687            М            [0; 0,2)    0,2

0,39248435            А             [0,2; 0,5) 0,3

0,6416145              Т             [0,5; 0,7) 0,2

0,7080725              Е             [0,7; 0,8) 0,1

0,080725 М            [0; 0,2)    0,2

0,403625 А             [0,2; 0,5) 0,3

0,67875   Т             [0,5; 0,7) 0,2

0,89375   И             [0,8; 0,9) 0,1

0.9375     К             [0,9; 1,0) 0,1

0.375       А             [0,2; 0,5) 0,3

 

Наведемо процедуру декодування арифметичного коду:

get encoded number Do

    find symbol whose range straddles the encoded number

    output the symbol

    range = high_range(symbol)- low_range(symbol)  

    subtract low_range(symbol) from encoded number

    divide encoded number by range

until no more symbols

 

Практична реалізація арифметичного кодування дещо складніша. По-перше, в процедурі декодування необхідно передбачити наявність ознаки кінця повідомлення. Це може бути довжина вектора даних, що потрібно стиснути, або ж спеціальний символ кінця блоку. По-друге, остаточний інтервал повідомлення стає відомим тільки після закінчення процесу кодування, проте передачу коду можна почати раніше, ніж надійде останній символ. У міру того, як інтервал повідомлення звужується, його старші розряди перестають змінюватися (табл. 2.8), і ці розряди вже можуть передаватися. Отже, передача коду здійснюється з незначною затримкою, яка не залежить від довжини повідомлення. По-третє, це питання точності представлення інтервалу, що кодує повідомлення. Кількість десяткових розрядів числа інтервалу необмежено зростає при збільшенні довжини повідомлення. Відтак, ця проблема вирішується використанням арифметики із скінченною розрядністю.