Неіснування ідеального алгоритму

Як уже було згадано в попередньому пункті, зображення I розглядається як безліч (послідовність) значень атрибутів пикселей. Надалі в цій лекції всі алгоритми й твердження ставляться як до зображень, так і до довільних послідовностей, елементи яких можуть приймати кінцеву кількість значень.

Твердження 13.2.1. Не існує алгоритму, що стискає без втрат будь-який набір даних.

Існує 2N послідовностей розміру N битов (будемо розглядати біт як мінімальний носій інформації). Нехай найдеться алгоритм A такий, що , де |I| - обсяг даних (довжина послідовності). Нехай M = max Mk, тоді M < N. Існує 21 + 22 + ... + 2M послідовностей довжини, меншої або рівної M. Але 21+22+...+2M = 2M+ 1-2 < 2N. Протиріччя.

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








Дата добавления: 2015-04-03; просмотров: 701; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2022 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.