дь-яке число з діапазону, отриманого на кроці 4. В якості коду ми можемо вибрати, наприклад, найкоротший код з інтервалу, рівний 0.1 і отримати чотириразове скорочення обсягу тексту. Для порівняння, код Хаффмана не зміг би стиснути подібне повідомлення, однак, на практиці виграш зазвичай невеликий і перевага віддається більш простому і швидкому алгоритмом з попереднього розділу. p align="justify"> Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0, 1), він послідовно визначає символи вхідного ланцюжка. Зокрема, в нашому випадку він спочатку поділить (пропорційно частотам символів) інтервал [0, 1) на [0, 0.11) і [0.11, 1). Оскільки число 0.1 (переданий кодером код ланцюжка aaba ) знаходиться в першому з них, можна отримати перший символ: a . Потім ділимо перший підінтервал [0, 0.11) на [0, 0.1001) та [0.1001, 0.1100) (пропорційно частотам символів). Знову вибираємо перший, тому що 0 <0.1 <0.1001. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи.
При розгляді цього методу виникають дві проблеми: по-перше, необхідна речова арифметика, взагалі кажучи, необмеженої точності, і по-друге, результат кодування стає відомий лише при закінченні вхідного потоку. Подальші дослідження, однак, показали, що можна практично без втрат обійтися целочисленной арифметикою слабкий точності (16-32 розряди), а також домогтися інкрементальною роботи алгоритму: цифри коду можуть видаватися послідовно в міру читання вхідного потоку. p align="justify"> Подібно алгоритму Хаффмана, арифметичний кодер також є двупроходним та вимагає передачі разом з закодованим текстом ще і таблиці частот символів. Взагалі, ці алгоритми дуже схожі і можуть легко взаимозаменяться. Отже, існує адаптивний алгоритм арифметичного кодування з усіма витікаючими перевагами та недоліками. Його основна відмінність від статичного в тому, що нові інтервали ймовірності перераховуються після отримання кожного наступного символу з вхідного потоку. br/>
АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без потерьПро-ходиРОВІАріфмет. статіч.5-688Да2ДаРедкоАріфмет. дінаміч.4-567Да1ДаРедко
Робота: в реальному масштабі часу і в потоці (крім статичного).
Основне застосування: універсальний, стиснення текстів. Використовується в архіватор LZARI, для стиснення зображень (JPEG). p align="justify"> 5) Ймовірнісний стиск.
Надзвичайно цікавий і найшвидший з відомих (поряд з RLE) методів стиснення інформації, що дає, до того ж непогані результати. Ймовірнісний стиск в чому нагадує ворожіння на кавовій гущі чи передбачення погоди, тільки більш ефективно.
Працює алгоритм наступним чином: є достатньо велика, динамічно оновлюється таблиця пророкувань, в якій для кожної можливої в...
