Методи стискання інформації: огляд та порівняльний аналіз, Детальна інформація

Національний Університет “Києво-Могилянська академія”

Департамент Комп’ютерних Технологій

Методи стискання інформації: огляд та порівняльний аналіз

Курсова робота студента IV р.н.

Чаговця Олексія

Керівник: доц. Ставровський А.Б.

Київ - 1999

Зміст

TOC \o "1-3" Зміст PAGEREF _Toc452326836 \h 2

Вступ. Огляд методів стискання інформації. PAGEREF _Toc452326837 \h 3

Методи кодування. PAGEREF _Toc452326838 \h 5

Кодування Хаффмена. PAGEREF _Toc452326839 \h 6

Арифметичне кодування. PAGEREF _Toc452326840 \h 8

Моделі вхідного потоку. PAGEREF _Toc452326841 \h 10

Стискання за допомогою купки книжок PAGEREF _Toc452326842 \h 11

Дворівневе кодування. Алгоритм Лемпеля-Зіва. PAGEREF _Toc452326843 \h 12

Сімейство алгоритмів LZ78 (LZW, MW, AP, Y) PAGEREF _Toc452326844 \h 14

Висновки. PAGEREF _Toc452326845 \h 17

Список використаної літератури. PAGEREF _Toc452326846 \h 18



Вступ. Огляд методів стискання інформації.

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

Існує низка “наївних” підходів до цієї проблеми. Найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).

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

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

Тут зробимо невеличкий відступ для уточнення термінології. Надалі будемо розглядати компресор (compressor) як програму, що перетворює масив символів деякого алфавіту в інший, бажано меншого за розміром. Часто роль цього масиву виконує безструктурний двійковий файл (подібний до файла MS-DOS або UNIX), а роль масиву символів вхідного алфавіту – 256 можливих значень байта (але не завжди). Відповідно, декомпресор (decompressor) – програма, що виконує зворотнє перетворення, до того ж виконує його однозначно. Таким чином, ми виключаємо з розгляду методи стискання, що втрачають інформацію (наприклад, метод стискання зображень JPEG, що базується на перетворенні кольорів, які практично неможливо розрізнити людським оком).

При цьому найбільш цікавими є однопрохідні алгоритми, що стискають не просто файл прямого доступу, а потік – файл, що не дозволяє позиціонування та скролінгу (подібно до програмного каналу (pipe) в UNIX). Такі алгоритми мають більш широку сферу застосувань, зокрема вони зручніші для апаратної реалізації в складі інтелектуальних контролерів пристроїв. Наприклад, протокол v42bis, що застосовується в модемах – це реалізація модифікації алгоритму LZW.

Фундаментальне поняття теорії інформації – ентропія, яку можна розглядати як міру кількості інформації в повідомленні. Під вартістю мається на увазі середня довжина кодового слова (в бітах) на один символ вихідного тексту. Надлишковість кодування дорівнює різниці між вартістю кодування та ентропією вихідного повідомлення з розрахунку на один символ. Надлишковість також можна розглядати як відношення кількості надлишкових символів до кількості корисних: за таких визначень очевидно, що надлишковість завжди є невід’ємною. Ефективний алгоритм стискання має мінімізувати надлишковість (в ідеальному випадку – звести до нуля). Фундаментальна теорема Шеннона про кодування джерел стверджує, що вартість кодування завжди не менша, ніж ентропія джерела, хоча й може бути як завгодно близька до неї. Це твердження встановлює теоретичні границі стискання даних.

Далі, процес стискання даних можна поділити на два – т. зв. моделювання і кодування. Ці процеси (а також і алгоритми, що їх реалізують), можна розглядати незалежно одне від одного.

Спочатку поговоримо про технології кодування.