5.2. Методи архівації

Потрібно писати так, щоб слів було тісно,

а думкам просторо.

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

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

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

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

Чим більший величинаKc,тим вище ступінь стиснення інформації.

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

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

В даний час розроблено багато алгоритмів архівації без втрат. Однак усі вони використовують дві прості ідеї.

Перша ідея, заснована на обліку частот появи символів у тексті, була розробленаХаффманом(D.A. Huffman) у 1952 р. Вона базується на тому факті, що у звичайному тексті частоти появи різних символів неоднакові.

При кодуванні символів ЕОМ використовують кодові таблиці. При цьому кожен символ кодується або одним байтом (CP-1251, КОІ-8) або двома байтами (Unicode). Кодові таблиці стандартизують процедуру кодування. Однак для передачі інформації по каналу зв'язку (або для довготривалого зберігання) можна використовувати складнішу процедуру кодування, яка забезпечить зменшення розміру файлу при повному збереженні вихідної інформації. При архівації не застосовуються стандартні кодові таблиці, а створюються власні. При цьому вид кодової таблиці щоразу змінюється і залежить від змісту документа, що архівується.

При упаковці за методом Хаффмана символи, що часто зустрічаються, кодуються (замінюються) короткими послідовностями бітів, а більш рідкісні символи — довгими послідовностями. До кожного стиснутого архіву прикладається таблиця відповідності наявних символів та кодів (чисел), які замінюють ці символи. Архіви хіба що скасовують стандартні кодові таблиці.

Припустимо, що вхідний алфавіт повідомлення складається з чотирьох символів: a, b, c, d, частоти появи яких у вихідному (несжатом) документі рівні відповідно: 1/2, 1/4, 1/8 і 1/8. Порядок кодування методом Хаффмана для зазначеного алфавіту ілюструється таблицею: