9.5 Стиснення інформації

Вважаю, що усі читачі знайомі з архіваторами файлів, ймовірно, багато з вас неодноразово ними користувалися. Метою архівації файлів є економія місця на жорсткому або гнучкому магнітному диску. Кому не доводилося час від часу замислюватися над тим, чи увійде цей файл на дискету? Існує велике число програм-архіваторів, є і спеціальні системні програмні засоби типу Stacker або Doublespace і так далі, що вирішують цю проблему.

Перші теоретичні розробки в області стискування інформації відносяться до кінця 40-х років. У кінці сімдесятих з'явилися роботи Шенона, Фано і Хафмана. До цього часу відноситься і створення алгоритму FGK (Faller, Gallager, Knuth), де використовується ідея "спорідненості", а одержувач і відправник динамічно міняють дерево кодів (дивися, наприклад, http://www.ics.uci.edu/~dan/plus/DC - Sec4.html).

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

Існують методи, які припускають деякі втрати початкових даних, інші алгоритми дозволяють перетворити інформацію без втрат. Стискування з втратами використовується при передачі звукової або графічної інформації, при цьому враховується недосконалість органів слуху і зору, які не помічають деякого погіршення якості, пов'язаної з цими втратами. Детальніше ці методи розглянуті в розділі "Перетворення, кодування і передача інформації".

Стискування інформації без втрат здійснюється статистичним кодуванням або на основі заздалегідь створеного словника. Статистичні алгоритми (напр. схема кодування Хафмана) привласнюють кожному вхідному символу певний код. При цьому найбільш часто використовуваному символу привласнюється найбільш короткий код, а найбільш рідкісному - довший. Таблиці кодування створюються заздалегідь і мають обмежений розмір. Цей алгоритм забезпечує найбільшу швидкодію і найменші затримки. Для отримання високих коефіцієнтів стискування статистичний метод вимагає великих об'ємів пам'яті.

Альтернативою статистичному алгоритму являється схема стискування, заснована на динамічно змінюваному словнику (напр., алгоритми Лембеля-Зива). Цей метод припускає заміну потоку символів кодами, записаними в пам'яті у вигляді словника (таблиця тієї, що перекодувала). Співвідношення між символами і кодами міняється разом із зміною даних. Таблиці кодування періодично міняються, що робить метод гнучкішим. Розмір невеликих словників лежить в межах 2-32 кілобайт але вищих коефіцієнтів стискування можна досягти при помітно великих словниках до 400 кілобайт.

Реалізація алгоритму можлива в двох режимах: безперервному і пакетному. Перший використовує для створення і підтримки словника безперервний потік символів. При цьому можливий багатопротокольний режим (наприклад, TCP/IP і DECnet). Словники стискування і декомпресії повинні змінюватися синхронно, а канал має бути досить надійний (напр., X.25 або PPP) що гарантує відсутність спотворення словника при ушкодженні або втраті пакету. При спотворенні одного із словників обоє ліквідовуються і мають бути створені знову.

Пакетний режим стискування також використовує потік символів для створення і підтримки словника, але потік тут обмежений одним пакетом і з цієї причини синхронізація словників обмежена межами кадру. Для пакетного режиму досить мати словник об'ємом, близько 4 Кбайт. Безперервний режим забезпечує кращі коефіцієнти стискування але затримка отримання інформації (сума часів стискування і декомпресії) при цьому більше, ніж в пакетному режимі.

При передачі пакетів іноді застосовується стискування заголовків, наприклад, алгоритм Ван Якобсона (RFC - 1144). Цей алгоритм використовується при швидкостях передачі менше 64 Kбит/с. При цьому досяжне підвищення пропускної спроможності на 50% для швидкості передачі 4800 біт/с. Стискування заголовків залежить від типу протоколу. При передачі великих пакетів на понад високих швидкостях по регіональних мережах використовуються спеціальні канальні алгоритми, незалежні від робочих протоколів. Канальні методи стискування інформації не можуть використовуватися для мереж, що базуються на пакетній технології, SMDS (Switched Multi - megabit Data Service), ATM, X.25 і Frame Relay. Канальні методи стискування дають добрі результати при з'єднанні за схемою точка-точка а при використанні маршрутизаторів виникають проблеми - адже треба виконувати процедури стискування/декомпресії в кожному маршрутизаторі, що помітно збільшує сумарний час доставки інформації. Виникає і проблема сумісності маршрутизаторів, яка може бути усунена процедурою ідентифікації при у становленні віртуального каналу.

Іноді для стискування інформації використовують апаратні засоби.