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

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

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

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

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

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

Київ - 1999

Зміст

Зміст...................................................................................................................................................................... 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) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.

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

Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена.

Кодування Хаффмена.

Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1 . Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ.

Нехай вхідний алфавіт складається з чотирьох символів: a , b , c , d , частоти яких відповідно дорівнюють 1/2, 1/4, 1/8, 1/8.

Кодування Хаффмена для цього алфавіта подається таблицею 1.

Таб. 1. Кодування Хаффмена.

Мал. 1. Дерево Хаффмена.

Наприклад, кодом ланцюжка abaaacb , поданого на вході як

00 01 00 00 00 10 01

буде

0 10 0 0 0 110 10

(проміжки додано для зручності читання). Отже, 14 біт на вході дали 11 біт на виході – стискання очевидне! На мал. 1 подано двійкове дерево Хаффмена для наведеного коду.

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

Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).

Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.

Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе , незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2!

Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду “ab”, “abc”, ..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам’яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання).

Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно. Великий коефіцієнт стискання, що не залежить від близькості значень імовірностей символів до степенів 1/2, може дати так зване арифметичне кодування.

Арифметичне кодування.

Арифметичне кодування – це метод, що дозволяє стискати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Концепцію методу наведено у роботах Еліаса в 60-х роках. Пізніше метод було розвинено та значно модифіковано.

Арифметичне кодування є оптимальним, досягаючи теоретичної границі стискання – ентропії вхідного потоку.

Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стискання можна подати як послідовність двійкових цифр із цього дробу.

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

Нехай алфавіт складається із двох символів: a та b з імовірностями відповідно 3/4 та 1/4. Як вже згадувалося вище, кодування Хаффмена не може стискати слова в даному алфавіті.

Розглянемо (відкритий справа) інтервал [0,1). Розіб’ємо його на частини, довжина яких пропорційна імовірностям символів. В нашому випадку це – [0, 3/4) i [3/4, 1). Принцип дії алгоритму полягає в наступному: кожному слову в початковому алфавіті відповідає певний підінтервал із [0,1). Порожньому слову відповідаю весь інтервал [0,1). Після отримання кожного наступного символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає символу, що надійшов. Кодом ланцюжка є інтервал, виділений після обробки всіх його символів, а точніше, двійковий запис координати будь-якої точки з цього інтервалу.

Таким чином, довжина отриманого інтервалу пропорційна ймовірності появи кодованого ланцюжка.

Виконаємо алгоритм для ланцюжка aaba (див. табл.2). В якості коду можна взяти будь-яке число з інтервалу, що отриманий на кроці 4, наприклад, 0.1.

Таб. 2. Арифметичне кодування.

Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0,1), він послідовно визначає символи вхідного ланцюжка.

Зокрема, в нашому випадку він спочатку поділить (пропорційно частотам символів) інтервал [0,1) на [0, 0.11) та [0.11,1). Оскільки число 0.1 (код ланцюжка аaba , переданий кодером) знаходиться в першому з них, можна отримати перший символ: а . Потім ділимо перший підінтервал [0, 0.11) на [0, 0.1001) та [0.1001, 0.1100) (пропорційно частотам символів). Знову обираємо перший, оскільки 0 < 0.1 < 0.1001. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи. Для того, щоб декодер зміг визначити кінець ланцюжка, можна або передавати його довжину окремо, або додати до алфавіту символ “кінець ланцюжка”.

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

Моделі вхідного потоку.

Як вже згадувалося вище, кодування являє собою лише частину процесу стискання. Не менш важливим є т. зв. моделювання (modelling). Ми вже говорили про те, що арифметичне кодування має мінімальну надлишковість за певного розподілу. Але звідки береться цей розподіл? І про який алфавіт йдеться?

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

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

Можливі різні підходи до цієї проблеми: найпростіший з них – збір статистики появи кожного символа незалежно від інших (моделювання лічильником Бернуллі: ймовірність появи символа не залежить від того, які символи зустрілися перед ним). Інший варіант – використання марківської моделі, коли розподіл ймовірностей символів будується з урахуванням деякої кількості попередніх символів (у марківському джерелі першого порядку ймовірність появи першого символа залежить тільки від одного останнього отриманого символа, і т.д.). Марковські моделі дають більш точну картину джерела, але кількість станів у них істотно більша, відповідно більший обсяг таблиць частот, що зберігаються. Окрім того, при використанні кодування Хаффмена вони можуть навіть зменшити ступінь стискання, оскільки ймовірності, що породжуються ними, зазвичай гірше наближуються ступенями 1/2.

Стискання за допомогою купки книжок

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

Метод було вперше відкрито та досліджено Рябко в 1980 р., а потім перевідкрито Бентлі, Слейтером, Тар’яном і Веі в 1986 р.

Ідея методу полягає в наступному: нехай алфавіт джерела складається з N символів із номерами 1,2,.....,N. Кодер зберігає список символів, що являє собою деяку перестановку алфавіту. При надходженні на вхід символа с , що має в цьому списку номер і , кодер передає номер і . Потім кодер переміщує символ с на початок списку, збільшуючи на 1 номери всіх символів, що стояли перед с . Таким чином, найбільш “популярні” символи сконцентруються на початку списку і матимуть коротші коди.

В якості коду для метода купки книжок можна використовувати так званий монотонний код – універсальний код джерела, для якого відома лише впорядкованість імовірностей символів (самі ймовірності невідомі).

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

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

В найпростішому випадку можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому відносно невеликий – близько 50% для текстових файлів.

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

Цей метод, про який піде мова, належить Лемпелю та Зіву і називається LZ77-compression (за роком публікації). Він полягає в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим словником – sliding dictionary). Назва “ковзаючий” зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує наступний ланцюжок, він дописує її в кінець словника та “відрізає” відповідну кількість символів на початку буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.

Розміри цього буфера є різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає на вихід пару (length, distance), де length – довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного потоку просто копіюється черговий символ вхідного потоку.

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

Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вхідних символів на два паралельних потоки length та distance. Очевидно, що ці потоки є потоками символів в алфавітах L та D, і до них можна застосувати один із вищенаведених методів (RLE, кодування Хаффмена, арифметичне кодування). Це підводить нас до ідеї дворівневого кодування, найефективнішій серед усіх, що використовуються сьогодні на практиці. Під час реалізації цього методу необхідно домогтися узгодженого виводу обох потоків в один файл. Ця проблема зазвичай розв’язується шляхом почергового запису кодів символів із обох потоків.

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

Не можна не відзначити широко відмий алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch compression, LZW, LZ78). Алгоритм відрізняється високою швидкістю роботи при кодуванні та декодуванні, невибагливістю до пам’яті та проста апаратна реалізація. Недолік – менший коефіцієнт компресії порівняно зі схемою двоступеневого кодування. Наведемо принципи роботи цього алгоритму.

Створимо словник, що зберігає рядки тексту і містить близько 2-3-8 тисяч пронумерованих комірок. Запишемо до перших 256 комірок рядки, що складаються з одного символа, номер якого дорівнює номеру комірки. Алгоритм проглядає вхідний потік, розбиваючи його на підрядки і додаючи нові комірки в кінець словника.

Будемо зчитувати із вхідного потоку по одному символу, кожного разу перевіряючи, чи є вже зчитаний ланцюжок у словнику. Таким чином ми отримаємо рядок S – найдовший префікс вхідного тексту (якщо його розглядати як рядок In ), який вже є у словнику. Нехай його знайдено в комірці з номером n . Виведемо число n у вихідний потік, змістимо вказівник вхідного потоку на length(S ) символів наперед та додамо до словника нову комірку, що містить рядок Sc , де с – черговий символ на вході (відразу після S ). За побудовою ланцюжка S ланцюжка Sc у словнику немає. Алгоритм перетворює потік символів на вході на потік індексів комірок словника на виході. При розмірі словника в 4096 комірок можна передавати 12 біт на індекс кожного ланцюжка, що знайдено.

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

Далі, кодер використовує дві операції зі словником: пошук рядка Sc , за умови, що рядок S є в словнику (та відома його позиція в ньому), а с – це наступний прочитаний символ, та додавання нової комірки, що містить цей рядок. Внаслідок цього можна обійтися структурою даних, що називається trie – деревом послідовного політерного пошуку.

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

Кодер LZW додає до словника одну комірку для кожного розпізнаного ланцюжка (тому його можна назвати методом із фразо-розширюваним словником). Коли словник переповнюється, кодер може або припинити його заповнення (“заморозити” словник, як класичний LZW), або очистити (повністю – compress, частково – PKZIP shrinking). Розглянемо тепер три інших методи цього сімейства.

Алгоритм MW (Miller and Wegman), на відміну від LZW, утворює нові комірки словника шляхом склеювання двох рядків (тобто використовує фразо-інкрементний словник): розпізнавши за аналогією з LZW ланцюжок S на вході, він додає до словника нову комірку PS – конкатенацію ланцюжків Р (попереднього розпізнаного ланцюжка) та S (нового). Завдяки цьому він, як правило, швидше адаптується до тексту, але може пропустити деякі ланцюжки. Тому він стискає не набагато краще за LZW, а деколи навіть і гірше.

Алгоритм MW не є префіксним. Тому реалізація словника для нього є складним завданням: звичайно, ми можемо використовувати trie для політерного пошуку (для цього ми запам’ятаємо всі префікси всіх ланцюжків із словника), однак маємо додати до кожного вузла прапорець, що вказує, чи міститься поданий рядок у словнику. До того ж пошук по словнику може вимагати повернення: якщо словник містить рядки abc та abcde , але не містить рядка abcdef (який тільки-но прочитано зі входу), то нам доведеться спочатку зчитати його весь, щоб пересвідчитися,що в словнику його немає, а потім “прокрутити” вхідний потік назад на три символи.

Властивість префіксності можна повернути, не втративши адаптивності алгоритму MW, якщо під час розпізнавання чергового ланцюжка S після ланцюжка P додавати до словника не тільки сам ланцюжок PS (як алгоритм MW), а множину АР(P,S ) – всі префікси PS , що довші за S . Маємо кодування АР (all prefixes), відкрите Сторером у 1988 р.

Алгоритм АР нарощує словник значно швидше, ніж MW. У той самий час, він зазвичай стискає краще, ніж MW.

Стосовно Y-кодування, відкритого Деніелом Бернстейном, то цей метод додає до словника один рядок на кожний прочитаний символ (подібно до АР), до того ж має властивість префіксності (подібно до LZW), тобто це – літерно-інкрементний метод з літерно-розширюваним словником.

Висновки.

По суті, всі наведені вище методи зводяться до двох основних ідей:

- “скорочуй те, що зустрічається часто” (статистичні методи);

- “повторюй старе” (словарні методи).

І нарешті, наведемо спробу класифікації методів стискання інформації:

Список використаної літератури.

1. Кохманюк Д. “Сжатие информации: как это делается”, Index PRO, 1993 К., №№ 1-2.

2. Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989.

3. Рябко Б.Я. Сжатие информации спомощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21.

4. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. – IEEE Transactions, IT-24. – No.5 (Sept.1978), pp. 530-536.