го не можна розбити на коди окремих символів. p align="justify"> Текст, стиснене арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0, 1). Результат стиснення можна представити як послідовність двійкових цифр із запису цього дробу. Кожен символ вихідного тексту представляється відрізком на числовій осі з довжиною, що дорівнює ймовірності його появи і початком, що збігається з кінцем відрізка символу, що передує йому в алфавіті. Сума всіх відрізків, очевидно повинна дорівнювати одиниці. Якщо розглядати на кожному кроці поточний інтервал як ціле, то кожен знову надійшов вхідний символ вирізає з нього підінтервал пропорційно своїй довжині і положенню.
Пояснимо роботу методу на прикладі.
Нехай алфавіт складається з двох символів: a і b з імовірностями відповідно 3/4 і 1/4.
Розглянемо (відкритий праворуч) інтервал [0, 1). Розіб'ємо його на частини, довжина яких пропорційна ймовірностям символів. У нашому випадку це [0, 3/4) і [3/4, 1). Суть алгоритму в наступному: кожному слову у вхідному алфавіті відповідає деякий підінтервал з [0, 1). Порожньому слову відповідає весь інтервал [0, 1). Після отримання кожного чергового символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає знову надійшов символу. Кодом повідомлення є інтервал, виділений після обробки всіх його символів, точніше, число мінімальної довжини, що входить в цей інтервал. Довжина отриманого інтервалу пропорційна ймовірності появи кодованого тексту. br/>В
Побудова інтервалу для повідомлення АВГ ....
Виконаємо алгоритм для ланцюжка aaba
Побудова арифметичного коду.
ШагПросмотренная цепочкаІнтервал0. [0, 1) = [0, 1) 1. a < span align = "justify"> [0, 3/4) = [0, 0.11) 2. aa [0, 9/16) = [0, 0.1001) 3. aab [27/64, 36/64) = [0.011011, 0.100100) 4. aaba [108/256, 135/256) = [0.01101100, 0.10000111)
На першому кроці ми беремо перші 3/4 інтервалу, відповідні символу а , потім залишаємо від нього ще тільки 3 /4. Після третього кроку від попереднього інтервалу залишиться його права чверть відповідно до положення і ймовірністю символу b . І, нарешті, на четвертому кроці ми залишаємо лише перші 3/4 від результату. Це і є інтервал, якому належить вихідне повідомлення.
В якості коду можна взяти бу...
