Курсова робота
Алгоритми стиснення даних
Зміст
Введення
Загальні відомості
Ентропія і кількість інформації
Комбінаторна, імовірнісна і алгоритмічна оцінка кількості інформації
Моделювання і кодування
Деякі алгоритми стиснення даних
Алгоритм LZ77
Алгоритм LZ78-LZW84
Алгоритм PPM
BWT - перетворення і компресор
Кодування Хаффмана
Арифметичне кодування
Алгоритм арифметичного кодування
Реалізація алгоритму арифметичного кодування
Реалізація моделі
Доказ правильності декодування
Пріращаемая передача і отримання
Негативне переповнення
Переповнення і завершення
Адаптивна модель для арифметичного кодування
Ефективність стиснення
Висновок
Список літератури
Додаток 1. Програмний код
Додаток 2. Інтерфейс програми
Введення
Основоположником науки про стиснення інформації прийнято вважати Клода Шеннона. Його теорема про оптимальний кодуванні показує, до чого потрібно прагнути при кодуванні інформації та на скільки та чи інша інформація при цьому стиснеться. Крім того, їм були проведені досліди за емпіричною оцінкою надмірності англійського тексту. Він пропонував людям вгадувати наступну букву і оцінював вірогідність правильного вгадування. На основі ряду дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0.6 - 1.3 біта на символ. Незважаючи на те, що результати досліджень Шеннона були по-справжньому затребувані лише десятиліття потому, важко переоцінити їх значення.
Перші алгоритми стиснення були примітивними у зв'язку з тим, що була примітивною обчислювальна техніка. З розвитком потужностей комп'ютерів стали можливими все більш потужні алгоритми. Справжнім проривом був винахід Лемпеля і Зівом в 1977 р. словникових алгоритмів. До цього моменту стиснення зводилося до примітивного кодуванню символів. Словникові алгоритми дозволяли кодувати повторювані рядки символів, що дозволило різко підвищити ступінь стиснення. Важливу роль зіграло винахід приблизно в цей же час арифметичного кодування, що дозволив втілити в життя ідею Шеннона про оптимальне кодування. Наступним проривом було винахід в 1984 р. алгоритму РРМ. Слід зазначити, що цей винахід довго залишалося непоміченим. Справа в тому, що алгоритм складний і вимагає великих ресурсів, в першу чергу великих об'ємів пам'яті, що було серйозною проблемою в той час. Винайдений в тому ж 1984 р. алгоритм LZW був надзвичайно популярний завдяки своїй простоті, хорошій рекламі і невимогливість до ресурсів, незважаючи на відносно низьку ступінь стиснення. На сьогоднішній день алгоритм РРМ є найкращим алгоритмом для стиснення текстової інформації, a LZW давно вже не вбудовується в нові додатки (проте широко використовується в старих).
Майбутнє алгоритмів стиснення тісно пов'язане з майбутнім комп'ютерних технологій. Сучасні алгоритми вже впритул наблизилися до Шенноновская оцінці 1.3 біта на символ, але вчені не бачать причин, по яких комп'ютер не може передбачати краще, ніж людина. Для досягнення високих ступенів стиснення доводиться використовувати більш складні алгоритми. Однак існувала один час упередження, що складні алгоритми з більш високим ступенем стиснення завжди більш повільні, неспроможне. Так, існують вкрай швидкі реалізації алгоритмів РРМ для текстової інформації і SPIHT для графіки, що мають дуже високу ступінь стиснення.
Таким чином, майбутнє за новими алгоритмами з високими вимогами до ресурсів і все більш і більш високою ступенем стиснення.
застаріває не тільки алгоритми, але й типи інформації, на які вони орієнтовані. Так, на зміну графіку з малим числом кольорів і неформатований текст прийшли високоякісні зображення та електронні документи в різних форматах. Відомі алгоритми не завжди ефективні на нових типах даних. Це робить вкрай актуальною проблему синтезу нових алгоритмів.
Кількість потрібної людині інформації неухильно зростає. Обсяги пристроїв для зберігання даних і пропускна здатність ліній зв'язку також ростуть. Однак кількість інформації зростає швидше. У цій проблеми є три рішення. Перше - обмеження кількості інформації. До жаль, воно не завжди прийнятно. Наприклад, для зображень це означає зменшення дозволу, що призведе до втрати дрібних деталей і може зробити зображення взагалі даремними (наприклад, для медичних або космічних зображень). Друге - збільшення обсягу носіїв інформації та пропускної спроможності каналів зв'язку. Це рішення пов'язане з матеріальними витратами, причому іноді досить значними. Третє рішення - використання стиснення інформації. Це рішення дозволяє в кілька разів скоротити вимоги до обсягу пристроїв зберігання даних і пропускної спроможності каналів зв'язку без додаткових витрат (за винятком витрат на реалізацію алгоритмів стиснення). Умовами його застосовності є надмірність інформації та можливість установки спеціального програмного забезпечення або апаратури як поблизу джерела, так і поблизу приймача інформації. Як правило, обидва ці умови задовольняються.
Саме завдяки необхідності використання стиснення інформації методи стиснення досить широко поширені. Однак існують дві серйозні проблеми. По-перше, широко використовувані методи стиснення, як правило, застаріли і не забезпечують достатнього ступеня стиснення. В Водночас вони вбудовані в велику кількість програмних продуктів і бібліотек і тому будуть використовуватися ще досить довгий час. Другою проблемою є часте застосування методів стиснення, не відповідають характеру даних. Наприклад, для стиснення графіки широко використовується алгоритм LZW, орієнтований на стиск одновимірної інформації, наприклад тексту. Вирішення цих проблем дозволяє різко підвищити ефективність застосування алгоритмів стиснення.
Таким чином, розробка і впровадження нових алгоритмів стиску, а також правильне використання існуючих дозволить значно скоротити витрати на апаратне забезпечення обчислювальних систем.
При реалізації алгоритму арифметичного кодування використовувався мову C # і візуальна середа програмування Microsoft Visual Studio 2005. Мова C # має наступні переваги: ​​простота, об'єктна орієнтованість, типова захищеність, "збірка сміття", підтримка сумісності версій, спрощення налагодження програм.
Загальні відомості
Ентропія і кількість інформації
Під ентропією в теорії інформації розуміють міру невизначеності (наприклад, міру невизначеності стану деякого об'єкта). Для того щоб зняти цю невизначеність, необхідно повідомити деяку кількість інформації. При цьому ентропія чисельно дорівнює мінімальній кількості інформації, яку необхідно повідомити для повного зняття невизначеності. Ентропія також може бути використана в якості оцінки найкращою можливою мірою стиснення для деякого потоку подій.
Тут і далі поняття події використовується як найбільш загальне поняття сутності, яку необхідно стиснути. Так, при стисненні потоку символів під подією може розумітися поява у вхідному потоці того чи іншого символу, при стисненні графіки - пікселя того чи іншого кольору і т.д.
Комбінаторна, імовірнісна і алгоритмічна оцінка кількості інформації
Найбільш Найпростішим способом оцінки кількості інформації є комбінаторний підхід. Відповідно до цього підходу, якщо змінна х може належати до безлічі з N елементів, то ентропія змінного
H (x) = log 2 N.
Таким чином, для передачі стану об'єкта достатньо I = log 2 N біт інформації. Зауважимо, що кількість інформації може бути дробовим. Зрозуміло, дробову кількість інформації неможливо зберегти на носії або передати по каналах зв'язку. У той же час, якщо необхідно передати або зберегти велику кількіс...
