Головна Головна -> Курсові роботи українською -> Інформатика, комп'ютери, програмування -> Методи стискання інформації: огляд та порівняльний аналіз

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

Назва:
Методи стискання інформації: огляд та порівняльний аналіз
Тип:
Курсова робота
Мова:
Українська
Розмiр:
30,32 KB
Завантажень:
194
Оцінка:
 
поточна оцінка 4.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5 
Зміст

ЗМІСТ 2

ВСТУП. ОГЛЯД МЕТОДІВ СТИСКАННЯ ІНФОРМАЦІЇ. 3

МЕТОДИ КОДУВАННЯ. 5

КОДУВАННЯ ХАФФМЕНА. 6

АРИФМЕТИЧНЕ КОДУВАННЯ. 8

МОДЕЛІ ВХІДНОГО ПОТОКУ. 10

СТИСКАННЯ ЗА ДОПОМОГОЮ КУПКИ КНИЖОК 11

ДВОРІВНЕВЕ КОДУВАННЯ. АЛГОРИТМ ЛЕМПЕЛЯ-ЗІВА. 12

СІМЕЙСТВО АЛГОРИТМІВ LZ78 (LZW, MW, AP, Y) 14

ВИСНОВКИ. 17

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ. 18

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

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

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

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

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

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

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

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

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

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

Методи кодування.

Кодування (encoding) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.

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

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок