Як відбувається стискання інформації?

Ще одна проблема, тісно пов'язана з моделями представлення інформації, – стискання інформації. При зберіганні та передачі даних каналами зв'язку обсяг інформації є основним параметром.

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

Розроблені та застосовуються два типи алгоритмів стискання: стискання інформації зі зміною структури даних (воно відбувається без втрати даних) та стискання інформації з частковою втратою даних. Алгоритми першого типу передбачають дві операції: стиснення інформації для зберігання, передачі та відновлення даних точно у вихідному вигляді, коли їх потрібно використовувати. Такий тип стискання застосовується, наприклад, для зберігання текстів (найбільш відомі алгоритми Хаффмена та Лемпеля-Зіва). Алгоритми другого типу не дозволяють повністю відновити оригінал і застосовуються для зберігання графіки або звуку; для текстів, чисел або програм вони не застосовуються.

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

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