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

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


1. Принципи стиснення даних

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

Всі методи стиснення даних поділяються на два основні класи:

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


2. Характеристики алгоритмів стиснення та їх застосовність

2.1. Коефіцієнт стиснення

Коефіцієнт стиснення - основна характеристика алгоритму стиснення. Вона визначається як відношення обсягу вихідних нестислих даних до обсягу стислих, тобто: k = \ frac {S_o} {S_c} , Де k - коефіцієнт стиснення, S o - обсяг вихідних даних, а S c - об'єм стислих. Таким чином, чим вище коефіцієнт стиснення, тим алгоритм ефективніше. Слід зазначити:

  • якщо k = 1, то алгоритм не виробляє стиснення, тобто вихідна повідомлення виявляється за обсягом рівним вхідному;
  • якщо k <1, то алгоритм породжує повідомлення більшого розміру, ніж нестиснене, тобто, здійснює "шкідливу" роботу.

Ситуація з k <1 цілком можлива при стисненні. Принципово неможливо отримати алгоритм стиснення без втрат, який за будь-яких даних утворював би на виході дані меншою або рівною довжини. Обгрунтування цього факту полягає в тому, що оскільки число різних повідомлень довжиною n біт становить рівно 2 n, число різних повідомлень з довжиною меншою або рівною n (при наявності хоча б одного повідомлення меншої довжини) буде менше 2 n. Це означає, що неможливо однозначно зіставити всі вихідні повідомлення стисненим: або деякі вихідні повідомлення не матимуть стиснутого представлення, або декільком вихідним повідомленнями буде відповідати одне і те ж стислий, а значить їх не можна відрізнити. Однак навіть коли алгоритм стиснення збільшує розмір вихідних даних, легко добитися того, щоб їх обсяг гарантовано не міг збільшитися більш, ніж на 1 біт. Тоді навіть у найгіршому випадку буде мати місце нерівність:
k \ geqslant \ frac {S_o} {S_o +1}
Робиться це в такий спосіб: якщо обсяг стиснутих даних менше обсягу вихідних, повертаємо стислі дані, додавши до них "1", інакше повертаємо вихідні дані, додавши до них "0"). Приклад того, як це реалізується на псевдо- C + +, показаний нижче:

 bin_data_t __ compess  (  bin_data_t input  )  / / Bin_data_t - тип даних, що означає довільну послідовність біт змінної довжини  {  bin_data_t output  =  arch  (  input  )  ;  / / Функція bin_data_t arch (bin_data_t input) реалізує певний алгоритм стиснення даних  if  (  output.  size  (  )  <  input.  size  (  )  )  / / Якщо обсяг стиснутих даних менше обсягу вихідних, функція bin_data_t :: size () повертає розмір даних  {  output.  add_begin  (  1  )  ;  / / Функція bin_data_t :: add_begin (bool __ bit__) додає біт, що дорівнює __ bit__ в початок послідовності  return  output  ;  / / Повертаємо стислу послідовність з доданою "1"  }  else  / / Інакше (якщо обсяг стиснутих даних більше або дорівнює обсягу вихідних)  {  input.  add_begin  (  0  )  ;  / / Додаємо "0" до вихідної послідовності  return  input  ;  / / Повертаємо вихідний файл з доданим "0"  }  } 

Коефіцієнт стиснення може бути як постійним (деякі алгоритми стиснення звуку, зображення тощо, наприклад А-закон, μ-закон, ADPCM, усічене блокове кодування), так і змінним. У другому випадку він може бути визначений або для кожного конкретного повідомлення, або оцінено за деякими критеріями:

  • середній (зазвичай по деякому тестовому наборі даних);
  • максимальний (випадок найкращого стиснення);
  • мінімальний (випадок найгіршого стиснення);

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


2.2. Допустимість втрат

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

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

2.3. Системні вимоги алгоритмів

Різні алгоритми можуть вимагати різної кількості ресурсів обчислювальної системи, на яких вони реалізовані:

  • оперативної пам'яті (під проміжні дані);
  • постійної пам'яті (під код програми і константи);
  • процесорного часу.

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

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

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

3. Алгоритми стиснення даних невідомого формату

Є два основні підходи до стиснення даних невідомого формату.

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

Література

  • Д. Ватолін, А. Ратушняк, М. Смирнов, В. Юкіно. Методи стиснення даних. Пристрій архиваторов, стиск зображень і відео. - Діалог-МИФИ, 2002. - С. 384. - ISBN 5-86404-170-X 3000 екз.
  • Д. Селомон. Стиснення даних, зображення і звуку. - М .: Техносфера, 2004. - С. 368. - ISBN 5-94836-027-X 3000 екз.