Методи стискання інформації: огляд та порівняльний аналіз, Детальна інформація

„

i

V

o

\x1900e

e



J

L

N

R

T

°

\x00B2

ae

e

e

i

\x00F0

\x34FF\x06D6\x0100\x030Al\xF661\x6C03\x6600\x0134\x0A00ення вхідного потоку. Однак, досліди показали, що можна практично без втрат обмежитися цілочисельною арифметикою невеликої точності (16-32 розряди), а також домогтися покрокової (інкрементальної) роботи алгоритми: цифри коду можуть видаватися послідовно під час читання вхідного потоку.

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

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

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

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

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

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

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

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

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