Стиснення даних

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Види стиснення:

  • Стиснення без втрат — можливо відновлення вихідних даних без спотворень.
  • Стиснення з втратами — відновлення можливе з незначними спотвореннями.

Стиснення без втрат[ред.ред. код]

Основна стаття Стиснення без втрат

Стиснення без втрат використовується при обробці та збереженні комп'ютерних програм і даних.

Для деяких типів даних спотворення не припустимі в принципі. У їх числі:

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

Стиснення з втратами[ред.ред. код]

Основна стаття Стиснення з втратами

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

Допустимість втрат[ред.ред. код]

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

Системні вимоги алгоритмів[ред.ред. код]

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

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

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

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

  • Алгоритм стиснення вимагає більших обчислювальних ресурсів, ніж алгоритм відновлення.

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

  • Алгоритми стиснення і відновлення вимагають приблизно рівних обчислювальних ресурсів.

Найбільш прийнятний варіант для ліній зв'язку, коли стиснення і відновлення відбувається одноразово на двох її кінцях (наприклад, в цифровій телефонії).

  • Алгоритм стиснення істотно менш вимогливий, ніж алгоритм відновлення.

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

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

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

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

Примітки[ред.ред. код]

Див. також[ред.ред. код]