ані меншою або рівної довжини. Обгрунтування цього факту полягає в тому, що оскільки число різних повідомлень довжиною n біт складає рівно 2n, число різних повідомлень з довжиною меншою або рівною n (при наявності хоча б одного повідомлення меншої довжини) буде менше 2n. Це означає, що неможливо однозначно зіставити всі вихідні повідомлення стисненим: або деякі вихідні повідомлення не будуть мати стиснутого представлення, або декільком вихідним повідомленнями буде відповідати одне і те ж стислий, а отже їх не можна відрізнити. Але навіть коли алгоритм стиснення збільшує розмір вихідних даних, легко домогтися того, щоб їх обсяг гарантовано не міг збільшитися більш, ніж на 1 біт. Тобто зробити так, щоб навіть у самому гіршому випадку мало місце нерівність:
= So/(So +1)
Робиться це в такий спосіб: якщо обсяг стиснутих даних менше обсягу вихідних, повертаються стислі дані шляхом додавання до них В«1В», інакше повертаємо вихідні дані, додавши до них В«0В». Коефіцієнт стиснення може бути як постійним (деякі алгоритми стиснення звуку, зображення тощо, наприклад А-закон, ? - закон, ADPCM, усічене блочне кодування), так і змінним. У другому випадку він може бути визначений або для кожного конкретного повідомлення, або оцінено за деякими критеріями:
В· середній (зазвичай по деякому тестовому набору даних);
В· максимальний (випадок найкращого стиснення);
В· мінімальний (випадок найгіршого стиснення);
або яким-небудь іншим. Коефіцієнт стиснення з втратами при цьому сильно залежить від допустимої похибки стиснення або якості, яке зазвичай виступає як параметр алгоритму. У загальному випадку постійний коефіцієнт стиснення здатні забезпечити тільки методи стиснення даних з втратами. p align="justify"> Основним критерієм відмінності між алгоритмами стиснення є описане вище наявність або відсутність втрат. У загальному випадку алгоритми стиснення без втрат універсальні в тому сенсі, що їх застосування безумовно можливо для даних будь-якого типу, в той час як можливість застосування стиснення з втратами повинна бути обгрунтована. Для деяких типів даних спотворення не припустимі в принципі. У їх числі символічні дані, зміна яких неминуче призводить до зміни їх семантики: програми та їх вихідні тексти, виконавчі масиви тощо; життєво важливі дані, зміни в яких можуть призвести до критичних помилок: наприклад, одержувані з медичної вимірювальної апаратури або контрольних приладів літальних, космічних апаратів і т. п.; багаторазово піддаються стисненню і відновленню проміжні дані при багатоетапної обробці графічних, звукових і відеоданих.
Різні алгоритми можуть вимагати різної кількості ресурсів обчислювальної системи, на яких ...
