Цей термін має також інші значення див. Стиснення.
Стиснення даних (англ. Data compression) - алгоритмічне перетворення даних. вироблене з метою зменшення займаного ними об'єму. Застосовується для більш раціонального використання пристроїв зберігання і передачі даних. Синоніми - упаковка даних. компресія. стискуюче кодування. кодування джерела. Зворотна процедура називається відновленням даних (розпакуванням, декомпресією).
Стиснення засноване на усуненні надмірності. міститься у вихідних даних. Найпростішим прикладом надмірності є повторення в тексті фрагментів (наприклад, слів природної або машинного мови). Подібна надмірність зазвичай усувається заміною повторюваної послідовності посиланням на вже закодований фрагмент із зазначенням його довжини. Інший вид надмірності пов'язаний з тим, що деякі значення в стисливих даних зустрічаються частіше інших. Скорочення обсягу даних досягається за рахунок заміни часто зустрічаються даних короткими кодовими словами, а рідкісних - довгими (ентропійне кодування). Стиснення даних, що не володіють властивістю надмірності (наприклад, випадковий сигнал або білий шум. Зашифровані повідомлення), принципово неможливо без втрат.
Стиснення без втрат дозволяє повністю відновити вихідне повідомлення, тому що не зменшує в ньому кількість інформації, не дивлячись на зменшення довжини. Така можливість виникає тільки якщо розподіл ймовірностей на множині повідомлень не рівномірний, наприклад частина теоретично можливих в колишньої кодуванні повідомлень на практиці не зустрічається.
Принципи стиснення даних
В основі будь-якого способу стиснення лежить модель джерела даних, або, точніше, модель надмірності. Іншими словами, для стиснення даних використовуються деякі апріорні відомості про те, якого роду дані стискаються. Не володіючи такими відомостями про джерело, неможливо зробити ніяких припущень про перетворення, яке дозволило б зменшити обсяг повідомлення. Модель надмірності може бути статичною, незмінною для всього, що стискається повідомлення, або будуватися або параметризрвані на етапі стиснення (і відновлення). Методи, що дозволяють на основі вхідних даних змінювати модель надмірності інформації, називаються адаптивними. Неадаптивними є зазвичай вузькоспеціалізовані алгоритми, що застосовуються для роботи з даними, що володіють добре певними і незмінними характеристиками. Переважна частина досить універсальних алгоритмів є в тій чи іншій мірі адаптивними.
Всі методи стиснення даних діляться на два основні класи:
Характеристики алгоритмів стиснення і їх застосовність
коефіцієнт стиснення
Коефіцієнт стиснення - основна характеристика алгоритму стиснення. Вона визначається як відношення обсягу стислих даних до обсягу вихідних незжатих даних, тобто: k = S c S o >>>>. де k - коефіцієнт стиснення, So - обсяг вихідних даних, а Sc - обсяг стиснутих. Таким чином, чим вище коефіцієнт стиснення, тим алгоритм ефективніше. Слід зазначити:
- якщо k = 1, то алгоритм не виробляє стиснення, тобто вихідна повідомлення виявляється за обсягом рівним вхідному;
- якщо k> 1, то алгоритм породжує повідомлення більшого розміру, ніж нестиснене, тобто, здійснює «шкідливу» роботу.
Ситуація з k <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
k ⩾ S o S o + 1> +1 >>>
Робиться це в такий спосіб: якщо обсяг стиснутих даних менше обсягу вихідних, повертаємо стислі дані, додавши до них «1», інакше повертаємо вихідні дані, додавши до них «0»).
Коефіцієнт стиснення може бути як постійним (деякі алгоритми стиснення звуку, зображення і т. П. Наприклад А-закон. Μ-закон. ADPCM. Усічений блочне кодування), так і змінним. У другому випадку він може бути визначений або для кожного конкретного повідомлення, або оцінений за деякими критеріями:
- середній (зазвичай по деякому тестовому набору даних);
- максимальний (випадок найкращого стиснення);
- мінімальний (випадок найгіршого стиснення);
або будь-яким іншим. Коефіцієнт стиснення з втратами при цьому сильно залежить від допустимої похибки стиснення або якості. яке зазвичай виступає як параметр алгоритму. У загальному випадку постійний коефіцієнт стиснення здатні забезпечити тільки методи стиснення даних з втратами.
допустимість втрат
Основним критерієм відмінності між алгоритмами стиснення є описане вище наявність або відсутність втрат. У загальному випадку алгоритми стиснення без втрат універсальні в тому сенсі, що їх застосування безумовно можливо для даних будь-якого типу, в той час як можливість застосування стиснення з втратами повинна бути обгрунтована. Для деяких типів даних спотворення не припустимі в принципі. В тому числі
Системні вимоги алгоритмів
Різні алгоритми можуть вимагати різної кількості ресурсів обчислювальної системи, на яких вони реалізовані:
- оперативної пам'яті (під проміжні дані);
- постійної пам'яті (під код програми і константи);
- процесорного часу.
В цілому, ці вимоги залежать від складності і «інтелектуальності» алгоритму. Загальна тенденція така: чим ефективніше і універсальніше алгоритм, тим більші вимоги до обчислювальних ресурсів він пред'являє. Проте, в специфічних випадках прості і компактні алгоритми можуть працювати не гірше складних і універсальних. Системні вимоги визначають їх споживчі якості: чим менш вимогливий алгоритм, тим на більш простий, а отже, компактною, надійної і дешевої системі він може бути реалізований.
Так як алгоритми стиснення і відновлення працюють в парі, має значення співвідношення системних вимог до них. Нерідко можна ускладнивши один алгоритм значно спростити інший. Таким чином, можливі три варіанти:
Алгоритми стиснення даних невідомого формату
Є два основні підходи до стиснення даних невідомого формату:
- На кожному кроці алгоритму стиснення черговий стискається символ або міститься в вихідний буфер стискає кодера як є (зі спеціальним прапором, позначати, що він не був стиснутий), або група з декількох стискаються символів замінюється посиланням на збігається з нею групу з уже закодованих символів. Оскільки відновлення стислих таким чином даних виконується дуже швидко, такий підхід часто використовується для створення саморозпаковуються програм.
- Для кожної сжимаемой послідовності символів одноразово або в кожен момент часу збирається статистика її народження в кодованих даних. На основі цієї статистики обчислюється ймовірність значення чергового кодованого символу (або послідовності символів). Після цього застосовується той або інший різновид ентропійного кодування. наприклад, арифметичне кодування або кодування Хаффмана. для подання часто зустрічаються послідовностей короткими кодовими словами, а рідко зустрічаються - довшими.