Методи стиснення

Сучасні архіватори, як правило, використовують кілька методів одночасно. Можна виділити деякі основні.

Кодування довжин серій (RLE — скорочення від run – length encoding – кодування довжин серій).

Дуже простий метод. Послідовна серія однакових елементів даних замінюється на два символи: елемент і число його повторень. Широко використовується як додатковий, так і проміжний метод. Як самостійний метод застосовується, наприклад, у графічному форматі BMP.

Словниковий метод (LZ — скорочення від Lempel Ziv – імена авторів).

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

Основним параметром словникового методу є розмір словника. Чим більше словник, тим більше ефективність. Однак для неоднорідних даних надмірно великий розмір може бути шкідливий, тому що при різкій зміні типу даних словник буде заповнений неактуальними словами. Для ефективної роботи цього методу при стисненні потрібна додаткова пам’ять приблизно на порядок більше, ніж потрібно для вихідних даних словника. Істотною перевагою словникового методу є проста і швидка процедура розпакування. Додаткова пам’ять при цьому непотрібна. Така особливість дуже важлива, якщо необхідний оперативний доступ до даних.

Ентропійний метод(Huffman — кодування Хаффмена, Arithmetic coding – арифметичне кодування).

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

Широко використовується як додатковий метод. Як самостійний метод застосовується, наприклад, у графічному форматі JPG.

Метод контекстного моделювання (CM — скорочення від context modeling – контекстне моделювання).

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

Для побудови ефективної моделі потрібно багато пам’яті. При розпакуванні приходиться будувати точно таку ж модель. Тому швидкість і вимоги до обсягу оперативної пам’яті для упакування і розпакування майже однакові. Нині методи контекстного моделювання дозволяють одержати найкращий ступінь стиснення, але вони відрізняються надзвичайно низькою швидкістю.

PPM (PPM — Prediction by Partial Matching – пророкування за частковим збігом).

Це особливий підвид контекстного моделювання. Пророкування виконується на підставі визначеної кількості попередніх елементів даних. Основним параметром є порядок моделі, що задає цю кількість елементів. Чим більше порядок моделі, тим вище ступінь стиснення, але потрібно більше оперативної пам’яті для збереження цієї моделі. Якщо оперативної пам’яті недостатньо, то така модель з великим порядком показує низькі результати. Метод PPM особливо ефективний для стиснення текстових даних.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Принцип роботи архіваторів	\|	Попередні перетворення або фільтрація.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.