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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Застосування

Відео

Див. також: Відеокодек

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

Більшість алгоритмів стиснення використовують стиснення з втратами. Нестиснене відео^[en] потребує високої частоти даних. Хоча кодеки виконують стиснення відео без втрат із коефіцієнтом стиснення 5-12, типове стиснення MPEG-4 із втратами має коефіцієнт стиснення в межах від 20 до 200. Як і при будь-якому стисненні з втратами, завжди відбувається пошук компромісу між бажаною якістю відео, затратами ресурсів на здійснення стиснення і декодування, і системними вимогами. Сильно стисненне відео може мати візуально помітні артефакти.

Деякі схеми стиснення відео зазвичай оперують квадратні групи сусідніх пікселів, що називаються макроблоками. Ці групи пікселів або блоки порівнюються від одного кадру до наступного, і відео кодек посилає лише різницю в рамках цих блоків. Ті зони відео де є більше рухів, при стиснені треба закодувати більше даних, аби зберегти більшу кількість змінних пікселів. Зазвичай коли в кадрах відео є вибухи, полум’я, стада тварин, панорамні зйомки, велика частота зміни деталй призводить до зменшення якості або збільшення змінної бітової швидкості.

Хронологія

Наступна таблиця є частковою історією міжнародних стандартів стиснення відео.

Історія стандартів стиснення відео

Рік	Стандарт	Видавець	Популярні реалізації
1984	H.120	ITU-T
1988	H.261	ITU-T	Відеоконференції, відеотелефонія
1993	MPEG-1 Part 2	ISO, IEC	Video CD
1995	H.262/MPEG-2 Part 2	ISO, IEC, ITU-T	DVD Video, Blu-ray, Digital Video Broadcasting, SVCD
1996	H.263	ITU-T	Відеоконференції, відеотелефонія, відео для мобільних телефонів (3GP)
1999	MPEG-4 Part 2	ISO, IEC	Відео в інтернет (DivX, Xvid ...)
2003	H.264/MPEG-4 AVC	Sony, Panasonic, Samsung, ISO, IEC, ITU-T	Blu-ray, HD DVD, Digital Video Broadcasting, iPod Video, Apple TV, відеоконференції
2009	VC-2 (Dirac)	SMPTE	Відео в інтернет, HDTV трансляція, UHDTV
2013	H.265	ISO, IEC, ITU-T

Примітки

1. . Center for Signal and Information Processing Research. Georgia Institute of Technology. Архів оригіналу за 23 травня 2013. Процитовано 6 березня 2013. 
2. Graphics & Media Lab Video Group (2007). Lossless Video Codecs Comparison. Moscow State University. 

Література

• Вейвлет-перетворення у компресії та попередній обробці зображень / О. В. Капшій, О. І. Коваль, Б. П. Русин ; НАН України, Фіз.-мех. ін-т ім. Г. В. Карпенка. — Львів : Сполом, 2008. — 206 с. : іл., табл., портр. ; 22 см. — Бібліогр.: с. 187—203 (238 назв). — 300 пр. — ISBN 978-966-665-554-0
• Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2002. — С. 384. — ISBN 5-86404-170-X. 3000 экз.
• Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техносфера, 2004. — С. 368. — ISBN 5-94836-027-X. 3000 экз.

Див. також

• Портал «Математика»

• Стиснення зображень
• Стиснення відео
• Стиснення аудіо