Ђ‹вЂ‹пари послідовних вхідних символів вказується що передбачається наступний (третій) символ. Якщо символ передбачений правильно - генерується код у вигляді однобітного префікса, рівного 1. Якщо ж ми не вгадали - видається код у вигляді префікса, рівного 0 і Неугаданное символу. При цьому Неугаданное символ заміщає в таблиці колишній там до цього, забезпечуючи постійне оновлення статистичної інформації. p align="justify"> Алгоритм є адаптивним і тому він однопроходний і не вимагає зберігання таблиці спільно з стисненим текстом.
декомпресора працює за аналогічною програмою, підтримуючи і оновлюючи таблицю синхронно з компресором. Якщо надійшов префікс 1, чергова вихідна буква витягується з таблиці за індексом, отриманому з двох попередніх букв, інакше-просто копіюється код з вхідного потоку у вихідний. Для невеликого підвищення ступеня стиснення рекомендується ініціалізувати таблицю перед початком роботи якимись часто зустрічаються буквосполученнями. p align="justify"> Схожий алгоритм, заснований на моделі Маркова 1 порядку, використовувався в архіватор PKZIP Ver.1.5 під ім'ям Reducing. Він є майже по всіх параметрах гірше, ніж Fin (двупроходний, вимагає передачі таблиці разом з текстом), але тим не менш гідний згадки. Таблиця програми Reducing містить масив символів V [256] [32], тобто для кожної вхідної літери на першому проході знаходяться не більше, ніж 32 (але може бути і менше) найбільш часто зустрічаються наступних літери. На другому проході справа йде подібно з Fin-якщо черговий символ b, наступний за символом a знаходиться серед 32 очікуваних, генерується код , prefix = 1, position = положенню символу b в масиві V [a] [] з 32 букв. Інакше видається префікс 0 і сам символ b. Алгоритм статичний, тому таблиця не оновлюється в процесі роботи. br/>
Висновки
АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без
Робота: в реальному масштабі часу і в потоці.
Основне застосування: універсальний.
6) LZ77
Найефективніший алгоритм стиснення інформації, що є одночасно і дуже простим для розуміння і дуже складним в реалізації, був запропонований Лемпелом і Зівом (Lempel, Ziv) в 1977 р. (LZ77).
Полягає він в наступному: мається ковзний (sliding) словник V об'ємом | V | = 2 ... 32 кБ. Якщо чергова вхідний рядок s тексту співпадає з рядком зі словника, то вона замінюється на покажчик ptr на цей рядок виду ptr = , для якої prefix = 1, після чого поточна позиція в початковому тексті pos зсувається на length символів далі. Поняття словника і рядки дещо відрізняється від повсякденного: під рядком мається на увазі будь-яка безперервна послідовність символів (літер), що починається з певної позиції в словнику або в тексті, дов...
