Цей термін має також інші значення див. Стиснення.
Стиснення даних (англ. Data compression) - алгоритмічне перетворення даних. вироблене з метою зменшення їх обсягу. Застосовується для більш раціонального використання пристроїв зберігання і передачі даних. Синоніми - упаковка даних, компресія, стискає кодування, кодування джерела. Зворотна процедура називається відновленням даних (розпакуванням, декомпресією).
Стиснення засноване на усуненні надмірності. міститься у вихідних даних. Найпростішим прикладом надмірності є повторення в тексті фрагментів (наприклад, слів природної або машинного мови). Подібна надмірність зазвичай усувається заміною повторюваної послідовності посиланням на вже закодований фрагмент із зазначенням його довжини. Інший вид надмірності пов'язаний з тим, що деякі значення в стисливих даних зустрічаються частіше інших. Скорочення обсягу даних досягається за рахунок заміни часто зустрічаються даних короткими кодовими словами, а рідкісних - довгими (ентропійне кодування). Стиснення даних, що не володіють властивістю надмірності (наприклад, випадковий сигнал або білий шум. Зашифровані повідомлення), принципово неможливо без втрат.
Принципи стиснення даних
В основі будь-якого способу стиснення лежить модель джерела даних, або, точніше, модель надмірності. Іншими словами, для стиснення даних використовуються деякі апріорні відомості про те, якого роду дані стискаються. Не володіючи такими відомостями про джерело, неможливо зробити ніяких припущень про перетворення, яке дозволило б зменшити обсяг повідомлення. Модель надмірності може бути статичною, незмінною для всього, що стискається повідомлення, або будуватися або параметризрвані на етапі стиснення (і відновлення). Методи, що дозволяють на основі вхідних даних змінювати модель надмірності інформації, називаються адаптивними. Неадаптивними є зазвичай вузькоспеціалізовані алгоритми, що застосовуються для роботи з даними, що володіють добре певними і незмінними характеристиками. Переважна частина досить універсальних алгоритмів є в тій чи іншій мірі адаптивними.
Всі методи стиснення даних діляться на два основні класи:
Характеристики алгоритмів стиснення і їх застосовність
коефіцієнт стиснення
Коефіцієнт стиснення - основна характеристика алгоритму стиснення. Вона визначається як відношення обсягу вихідних незжатих даних до обсягу стислих, тобто:, де k - коефіцієнт стиснення, So - обсяг вихідних даних, а Sc - обсяг стиснутих. Таким чином, чим вище коефіцієнт стиснення, тим алгоритм ефективніше. Слід зазначити:
- якщо k = 1, то алгоритм не виробляє стиснення, тобто вихідна повідомлення виявляється за обсягом рівним вхідному;
- якщо k <1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.
Ситуація з k <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
Робиться це в такий спосіб: якщо обсяг стиснутих даних менше обсягу вихідних, повертаємо стислі дані, додавши до них «1», інакше повертаємо вихідні дані, додавши до них «0»). Приклад того, як це реалізується на псевдо-C ++. показаний нижче:
Коефіцієнт стиснення може бути як постійним (деякі алгоритми стиснення звуку, зображення і т. П. Наприклад А-закон. Μ-закон. ADPCM. Усічений блочне кодування), так і змінним. У другому випадку він може бути визначений або для кожного конкретного повідомлення, або оцінений за деякими критеріями:
- середній (зазвичай по деякому тестовому набору даних);
- максимальний (випадок найкращого стиснення);
- мінімальний (випадок найгіршого стиснення);
або будь-яким іншим. Коефіцієнт стиснення з втратами при цьому сильно залежить від допустимої похибки стиснення або якості. яке зазвичай виступає як параметр алгоритму. У загальному випадку постійний коефіцієнт стиснення здатні забезпечити тільки методи стиснення даних з втратами.
допустимість втрат
Основним критерієм відмінності між алгоритмами стиснення є описане вище наявність або відсутність втрат. У загальному випадку алгоритми стиснення без втрат універсальні в тому сенсі, що їх застосування безумовно можливо для даних будь-якого типу, в той час як можливість застосування стиснення з втратами повинна бути обгрунтована. Для деяких типів даних спотворення не припустимі в принципі. В тому числі
Системні вимоги алгоритмів
Різні алгоритми можуть вимагати різної кількості ресурсів обчислювальної системи, на яких вони реалізовані:
- оперативної пам'яті (під проміжні дані);
- постійної пам'яті (під код програми і константи);
- процесорного часу.
В цілому, ці вимоги залежать від складності і «інтелектуальності» алгоритму. Загальна тенденція така: чим ефективніше і універсальніше алгоритм, тим більші вимоги до обчислювальних ресурсів він пред'являє. Проте, в специфічних випадках прості і компактні алгоритми можуть працювати не гірше складних і універсальних. Системні вимоги визначають їх споживчі якості: чим менш вимогливий алгоритм, тим на більш простий, а отже, компактною, надійної і дешевої системі він може бути реалізований.
Так як алгоритми стиснення і відновлення працюють в парі, має значення співвідношення системних вимог до них. Нерідко можна ускладнивши один алгоритм значно спростити інший. Таким чином, можливі три варіанти:
Алгоритми стиснення даних невідомого формату
Є два основні підходи до стиснення даних невідомого формату.
- На кожному кроці алгоритму стиснення черговий стискається символ або міститься в вихідний буфер стискає кодера як є (зі спеціальним прапором, позначати, що він не був стиснутий), або група з декількох стискаються символів замінюється посиланням на збігається з нею групу з уже закодованих символів. Оскільки відновлення стислих таким чином даних виконується дуже швидко, такий підхід часто використовується для створення саморозпаковуються програм.
- Для кожної сжимаемой послідовності символів одноразово або в кожен момент часу збирається статистика її народження в кодованих даних. На основі цієї статистики обчислюється ймовірність значення чергового кодованого символу (або послідовності символів). Після цього застосовується той або інший різновид ентропійного кодування. наприклад, арифметичне кодування або кодування Хаффмана. для подання часто зустрічаються послідовностей короткими кодовими словами, а рідко зустрічаються - довшими.
література
Дивитися що таке "Стиснення даних" в інших словниках:
Стиснення даних - процес, що забезпечує зменшення обсягу даних шляхом скорочення їх надмірності. Стиснення даних пов'язано з компактним розташуванням порцій даних стандартного розміру. Розрізняють стиснення з втратою і без втрати інформації. За англійськи: Data ... ... Фінансовий словник
СТИСК ДАНИХ - СТИСК ДАНИХ, в обчислювальній техніці методика, що дозволяє домогтися скорочення обсягу пам'яті, займаної даними. Для цього великі літери представляють меншим числом біт, ніж зазвичай, а часто вживані слова відтворюють скороченими ... ... Науково-технічний енциклопедичний словник
стиснення даних - 05.02.34 стиснення даних [data compaction]: Методика або алгоритм обробки вихідних даних з метою їх ефективного представлення, результатом якого є зменшення необхідного числа октетів на носії даних в порівнянні з числом, ... ... Словник-довідник термінів нормативно-технічної документації
стиснення даних - duomenų spūda statusas T sritis radioelektronika atitikmenys: angl. data compression vok. Datenkompression, f rus. стиснення даних, n pranc. compression de données, f ... Radioelektronikos terminų žodynas
Стиснення даних з втратами - Цей термін має також інші значення див. Стиснення. Стиснення даних з втратами метод стиснення (компресії) даних, при використанні якого розпаковані дані відрізняються від вихідних, але ступінь відмінності не є істотною з точки ... Вікіпедія
- Стиснення даних в умовах обмеженості ресурсів. Михайло Медведєв. В даний час великого поширення набули мобільні обчислювальні пристрої і різна вбудована техніка, яка часто характеризується мінімальними продуктивними ... Детальніше Купити за 4889 грн (тільки Україна)
- Стиснення даних. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Стиснення даних (англ. Data compression) - алгоритмічне ... Детальніше Купити за 998 руб
- Стиснення даних, зображень і звуку. Д. Селомон. У навчальному посібнику викладено як загальні ідеї й основи теорії стиснення інформації, так і практичні методи з докладним описом конкретних алгоритмів компресії різних типів цифрових даних. ... Детальніше Купити за 293 руб