ВСТУП

Основоположником науки про стиснення інформації прийнято рахувати Клода Шеннона. Його теорема про оптимальне кодування показує, до чого потрібно прагнути при кодуванні інформації і на скільки та або інша інформація при цьому стиснеться. Крім того, ним були проведені досліди за емпіричною оцінкою надмірності англійського тексту. Він пропонував людям вгадувати наступну букву і оцінював вірогідність правильного вгадування. На основі ряду дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0.6 — 1.3 біта на символ. Не дивлячись на те, що результати досліджень Шеннона були по-справжньому затребувані лише десятиліття опісля, важко переоцінити їх значення.

Перші алгоритми стиснення були примітивними у зв'язку з тим, що була примітивною обчислювальна техніка. З розвитком потужностей комп'ютерів стали можливими все більш могутні алгоритми. Справжнім проривом був винахід Лемпелем і Зівом в 1977 р. словарних алгоритмів. До цього моменту стиснення зводилося до примітивного кодування символів. Словарні алгоритми дозволяли кодувати рядки символів, що повторювалися, що дозволило різко підвищити ступінь стиснення. Важливу роль зіграв винахід зразково в цей же час арифметичного кодування, що дозволило утілити в життя ідею Шеннона про оптимальне кодування. Наступним проривом був винахід в 1984 р. алгоритму РРМ. Слід зазначити, що цей винахід довго залишався непоміченим. Річ у тому, що алгоритм складний і вимагає великих ресурсів, в першу чергу великих об'ємів пам'яті, що було серйозною проблемою у той час. Винайдений в тому ж 1984 р. алгоритм LZW був надзвичайно популярний завдяки своїй простоті, хорошій рекламі і невимогливості до ресурсів, не дивлячись на відносно низький ступінь

стиснення. На сьогоднішній день алгоритм РРМ є найкращим алгоритмом для стиснення текстової інформації, а LZW давно вже не вбудовується в нові додатки (проте широко використовується в старих).

Майбутнє алгоритмів стиснення тісно пов'язане з майбутнім комп'ютерних технологій. Сучасні алгоритми вже впритул наблизилися до Шеннонівської оцінки 1.3 біта на символ, але учені не бачать причин, по яким комп'ютер не може передбачати краще, ніж людина. Для досягнення високих ступенів стиснення доводиться використовувати складніші алгоритми. Так, існують украй швидкі реалізації алгоритмів РРМ для текстової інформації і SPIHТ для графіки, що мають дуже високий ступінь стиснення.

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

1 АНАЛІЗ ПРОБЛЕМИ ТА ТИПИ ГРАФІЧНИХ ФОРМАТІВ

1.1 Аналіз проблеми стиснення інформації

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

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

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

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

Отже, побудова алгоритму стиснення інформації – це завжди пошук компромісу між вимогами до ступеня стиснення, швидкодією, складністю алгоритму і кількістю потрібної для роботи алгоритму пам'яті. Перед побудовою алгоритму слід відповісти на наступні питання:–

Скільки пам'яті буде доступна алгоритму?–

Чи повинен алгоритм бути максимально швидким?–

Чи повинен алгоритм бути простим?–

Чи повинен алгоритм мати максимально можливий ступінь стиснення?–

Чи повинен алгоритм бути однопрохідним (потоковим)?

Якщо головним критерієм є швидкодія, має сенс використовувати префіксне кодування. Якщо немає, то краще використовувати Range кодування. Якщо розмір вільної пам'яті менше 100 кбайт (наприклад, алгоритм використовуватиметься у вбудовуваних системах) і дані мають складну модель (наприклад, потрібно стискати текстову інформацію), то статистичні моделі не підходять і слід використовувати словарні. Якщо пам'ять досить (6-8 мбайт і більш), то слід використовувати статистичні моделі. Алгоритми на основі BWT-перетворення не можуть бути ефективно реалізовані як потокові (наприклад, для використання в модемах).

1.2 Типи графічних файлів

Рисунок 1.1 – Вигляд різних типів графічних файлів

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