Моделі вхідного потоку.

Як вже згадувалося вище, кодування являє собою лише частину процесу стискання. Не менш важливим є т. зв. моделювання (modelling). Ми вже говорили про те, що арифметичне кодування має мінімальну надлишковість за певного розподілу. Але звідки береться цей розподіл? І про який алфавіт йдеться?

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

Значно цікавіші так звані адаптивні моделі, які враховують поточний контекст. Такі моделі дозволяють будувати швидкі однопрохідні алгоритми стискання, що не вимагають апріорних знань про вхідний потік даних і будують розподіл під час роботи. Також виділяють клас “локально адаптивних” алгоритмів, які під час побудови розподілу відмічають більшою вагою частоти останніх символів із тих, що надійшли.

Можливі різні підходи до цієї проблеми: найпростіший з них – збір статистики появи кожного символа незалежно від інших (моделювання лічильником Бернуллі: ймовірність появи символа не залежить від того, які символи зустрілися перед ним). Інший варіант – використання марківської моделі, коли розподіл ймовірностей символів будується з урахуванням деякої кількості попередніх символів (у марківському джерелі першого порядку ймовірність появи першого символа залежить тільки від одного останнього отриманого символа, і т.д.). Марковські моделі дають більш точну картину джерела, але кількість станів у них істотно більша, відповідно більший обсяг таблиць частот, що зберігаються. Окрім того, при використанні кодування Хаффмена вони можуть навіть зменшити ступінь стискання, оскільки ймовірності, що породжуються ними, зазвичай гірше наближуються ступенями 1/2.

Стискання за допомогою купки книжок

Говорячи про моделі вхідного потоку та адаптивні алгоритми стискання, не можна не згадати простий та досить ефективний метод кодування джерела з невідомим розподілом частот, відомий як стискання за допомогою купки книжок.

Метод було вперше відкрито та досліджено Рябко в 1980 р., а потім перевідкрито Бентлі, Слейтером, Тар’яном і Веі в 1986 р.

Ідея методу полягає в наступному: нехай алфавіт джерела складається з N символів із номерами 1,2,.....,N. Кодер зберігає список символів, що являє собою деяку перестановку алфавіту. При надходженні на вхід символа с, що має в цьому списку номер і, кодер передає номер і. Потім кодер переміщує символ с на початок списку, збільшуючи на 1 номери всіх символів, що стояли перед с. Таким чином, найбільш “популярні” символи сконцентруються на початку списку і матимуть коротші коди.

В якості коду для метода купки книжок можна використовувати так званий монотонний код – універсальний код джерела, для якого відома лише впорядкованість імовірностей символів (самі ймовірності невідомі).

Дворівневе кодування. Алгоритм Лемпеля-Зіва.

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

В найпростішому випадку можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому відносно невеликий – близько 50% для текстових файлів.

Значно якісніше стискання можна отримати виділенням із вхідного потоку ланцюжків, що повторюються, і кодування посилань на ці ланцюжки.

Цей метод, про який піде мова, належить Лемпелю та Зіву і називається LZ77-compression (за роком публікації). Він полягає в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим словником – sliding dictionary). Назва “ковзаючий” зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує наступний ланцюжок, він дописує її в кінець словника та “відрізає” відповідну кількість символів на початку буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.

Розміри цього буфера є різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає на вихід пару (length, distance), де length – довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного потоку просто копіюється черговий символ вхідного потоку.

У найпершій версії алгоритму пропонувалося виконувати найпростіший пошук по всьому словнику. Час стискання за такої реалізації був пропорційний добутку довжини вхідного потоку на розмір буфера, що не є придатним для практичного використання. Але потім було запропоновано використовувати двійкове дерево для пошуку в словнику, що дозволило на порядок збільшити швидкість роботи.

Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вхідних символів на два паралельних потоки length та distance. Очевидно, що ці потоки є потоками символів в алфавітах L та D, і до них можна застосувати один із вищенаведених методів (RLE, кодування Хаффмена, арифметичне кодування). Це підводить нас до ідеї дворівневого кодування, найефективнішій серед усіх, що використовуються сьогодні на практиці. Під час реалізації цього методу необхідно домогтися узгодженого виводу обох потоків в один файл. Ця проблема зазвичай розв’язується шляхом почергового запису кодів символів із