Размещено на http://www.allbest.ru/

Київський національний університет будівництва і архітектури

Кафедра кібернетичної безпеки та комп'ютерної інженерії

Курсова робота

з дисципліни «Теорія інформації та кодування»

на тему «Універсальний алгоритм стиснення даних без втрат Лемпеля-Зіва-Велча LZW»

Студента ІI курсу

Дудченко

Керівник Кучанський О.Ю.

Київ-2017

ЗМІСТ

• Вступ
• Розділ 1. Загальні відомості
• 1.1 Стиснення без втрат
• 1.2 Словникові алгоритми
• 1.3 Алгоритм Лемпеля -- Зива -- Велча
• 1.4 Аналіз роботи
• Розділ 2. Спеціальна частина
• 2.1 Постановка задачі
• 2.2 Вхідні та вихідні дані
• 2.3 Опис алгоритму
• Висновки
• Список використаної літератури
• Додаток

ВСТУП

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

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

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

РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ

1.1 Стиснення без втрат

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

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

Стиснення без втрат використовується, коли важливо, щоб відновленні дані були ідентичні оригіналу. Типовий приклад -- виконуваний файл або джерельний код, текстовий файл. Деякі графічні файлові формати, наприклад, PNG та GIF використовують тільки стиснення без втрат, тоді як формати TIFF та MNG можуть використовувати стиснення як з втратами, так й без втрат. Формати стиснення звуку без втрат використовується для архівування або виробничих цілей, в той час, як менші формати стиснення аудіо з втратами використовуються в аудіопрогравачах та в ситуаціях коли простір для зберігання інформації обмежений або нема потреби в точному відтворенні інформації.

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

00 > 0

01 > 10

10 > 110

11 > 111

В такому випадку шістнадцять бітів:

00 01 00 00 11 10 00 00

будуть перетворені у 13 бітів:

0 10 0 0 111 110 0 0

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

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

Статистичні моделі алгоритмів для тексту (чи текстових бінарних даних, таких як виконувальні файли) містять:

· Перетворення Берроуза -- Вілера

· LZ77 і LZ78

· LZW[4]

1.2 Словникові алгоритми

Cловникові алгоритми призначені для усунення надмірності ланцюгів подій. арифметичний кодування шеннон алгоритм

Суть алгоритму полягає в тому, що ланцюжки подій поміщаються в словник. Якщо в подальшому у вхідному потоці зустрічається ланцюжок подій, яка присутня в словнику, то замість цього ланцюжка в вихідний потік міститься посилання на елемент словника. Ідея словникових алгоритмів була запропонована Я.Зівом і А.Лемпелем в 1977р. Ідея була втілена в алгоритмі ЛЗ77, який став основою цілого сімействі алгоритмів. Альтернативний підхід, запропонований ними ж в 1978р. , породив сімейство алгоритмів ЛЗ78.

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

Під словником в алгоритмах сімейства LZ77 сприймається деяка кількість попередніх подій. В якості посилань на елементи словника використовується відстань до раніше використовуємого ланцюга події і довжина цього ланцюга.

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

В алгоритмі LZSS посилання на елементи словника і літеральні події різняться прапорцем-бітом.

Алгоритм LZH аналогічний LZSS , але використовують для покажчиків кодування Хаффмана.

В даний час алгоритми сімейства LZ77 широко використовується в програмах універсальних архіваторів. Це як правило модифікації LZSS з використанням кодів Хаффмана , Шеннона-Фано або арифметичного кодування(HA, метод 1).

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

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

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

LZC використовується в утиліті COMPRESS операційної системи Unix в графічному форматі GIF.

Алгоритм LZFG є в деякому сенсі гібридом алгоритмів LZ77 і LZ78. Як і LZ77 , він допускає кодування ланцюжків довільної довжини (в алгоритмах LZ78 довжина ланцюжків як правило обмежена кількістю попередніх появ ланцюжка у вхідному потоці). З іншого боку , адресація елементів словника аналогічно техніки LZ78 з тією різницею , що замість двійкового дерева використовується так зване дерево Patricia. Його відмінність полягає в тому , що якщо дерево не містить розгалужень то послідовність вершин об'єднуються в одну.

Алгоритм RFGD є модифікацією LZFG з більш високим ступенем стиснення. Він поміщає в вихідний потік дані чотирьох типів: термінальні вершини дерева , нетермінальні вершини дерева , літерали , які до цього часу зустрічалися у вхідному потоці та літерали , які раніше не зустрічалися. Кожен з них кодується за власною схемою. Для визначення того , якого саме типу дані поміщаються в вихідний потік , безпосередньо перед ними в вихідний потік поміщається спеціальний префікс. Алгоритм реалізований апаратно[7].

1.3 Алгоритм Лемпеля -- Зива -- Велча

Алгоритм Лемпеля - Зива - Велч (Lempel-Ziv-Welch, LZW) - це універсальний алгоритм стиснення даних без втрат, створений Авраамом Лемпелем (англ. Abraham Lempel), Яаковом Зивом (англ. Jacob Ziv) і Террі Велчем (англ. Terry Welch ). Він був опублікований Велчем в 1984 році, в якості поліпшеної реалізації алгоритму LZ78, опублікованого Лемпелем і Зивом в 1978 році. Алгоритм розроблений так, щоб його можна було швидко реалізувати, але він не обов'язково оптимальний, оскільки він не проводить ніякого аналізу вхідних даних.

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

Наприклад, якщо стискають байтові дані (текст), то рядків в таблиці виявиться 256 (від «0» до «255»). Якщо використовується 10-бітний код, то під коди для рядків залишаються значення в діапазоні від 256 до 1023. Нові рядки формують таблицю послідовно, т. Е. Можна вважати індекс рядка її кодом.

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

Псевдокод алгоритма

1. Ініціалізація словника усіма можливими односимвольних фразами. Ініціалізація вхідний фрази щ першим символом повідомлення.

2. Вважати черговий символ K з кодованого повідомлення.

3. Якщо КОНЕЦ_СООБЩЕНІЯ, то видати код для щ, інакше:

4. Якщо фраза щ (K) вже є в словнику, привласнити вхідний фразі значення щ (K) і перейти до кроку 2, інакше видати код щ, додати щ (K) в словник, привласнити вхідний фразі значення K і перейти до кроку 2.

5. Кінець.

Приклад

Просто по псевдокоду зрозуміти роботу алгоритму не дуже легко, тому розглянемо приклад стиснення і декодування зображення.

Спочатку створимо початковий словник одиничних символів. У стандартній кодуванні ASCII є 256 різних символів, тому, для того, щоб всі вони були коректно закодовані (якщо нам невідомо, які символи будуть присутні у вихідному файлі, а які - ні), початковий розмір коду буде дорівнює 8 бітам. Якщо нам заздалегідь відомо, що в початковому файлі буде менша кількість різних символів, то цілком розумно зменшити кількість біт. Щоб форматувати таблицю, ми встановимо відповідність коду 0 відповідному символу з двійкового кодом 00000000, тоді 1 відповідає символу з кодом 00000001, і т.д., до коду 255. Насправді ми вказали, що кожен код від 0 до 255 є кореневим.

Більше в таблиці не буде інших кодів, що володіють цією властивістю.

У міру зростання словника, розмір груп повинен зростати, з тим, щоб врахувати нові елементи. 8-бітові групи дають 256 можливих комбінації біт, тому, коли в словнику з'явиться 256-е слово, алгоритм повинен перейти до 9-бітовим групам. При появі 512-ого слова станеться перехід до 10-бітовим групам, що дає можливість запам'ятовувати вже +1024 слова і т.д.

У нашому прикладі алгоритму заздалегідь відомо про те, що буде використовуватися лише 5 різних символів, отже, для їх зберігання буде використовуватися мінімальна кількість біт, що дозволяє нам їх запам'ятати, тобто 3 (8 різних комбінацій).

Кодування

Нехай ми стискаємо послідовність «abacabadabacabae».

§ Крок 1: Тоді, відповідно до викладеного вище алгоритму, ми додамо до спочатку порожній рядку "a" і перевіримо, чи є рядок "a" в таблиці. Оскільки ми при ініціалізації занесли в таблицю всі рядки з одного символу, то рядок "a" є в таблиці.

§ Крок 2: Далі ми читаємо наступний символ «b» з вхідного потоку і перевіряємо, чи є рядок "ab" в таблиці. Такий рядки в таблиці поки немає.

§ Додаємо в таблицю <5> "ab". У потік: <0>;

§ Крок 3: "ba" - немає. У таблицю: <6> "ba". У потік: <1>;

§ Крок 4: "ac" - немає. У таблицю: <7> "ac". У потік: <0>;

§ Крок 5: "ca" - немає. У таблицю: <8> "ca". У потік: <2>;

§ Крок 6: "ab" - є в таблиці; "Aba" - немає. У таблицю: <9> "aba". У потік: <5>;

§ Крок 7: "ad" - немає. У таблицю: <10> "ad". У потік: <0>;

§ Крок 8: "da" - немає. У таблицю: <11> "da". У потік: <3>;

§ Крок 9: "aba" - є в таблиці; "Abac" - немає. У таблицю: <12> "abac". У потік: <9>;

§ Крок 10: "ca" - є в таблиці; "Cab" - немає. У таблицю: <13> "cab". У потік: <8>;

§ Крок 11: "ba" - є в таблиці; "Bae" - немає. У таблицю: <14> "bae". У потік: <6>;

· Крок 12: І, нарешті останній рядок "e", за нею йде кінець повідомлення, тому ми просто виводимо в потік <4>.

Рисунок 1.1 -- Таблиця кодування

Отже, ми отримуємо закодоване повідомлення «0 1 0 2 5 0 3 9 8 6 4», що на 11 біт коротше.

Декодування

Особливість LZW полягає в тому, що для декомпресії нам не треба зберігати таблицю рядків в файл для розпакування. Алгоритм побудований таким чином, що ми в змозі відновити таблицю рядків, користуючись тільки потоком кодів.

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

Рисунок 1.2 -- Таблиця декодування

1.4 Аналіз роботи

Метою даної роботи є вивчення поведінки LZW алгоритму стиснення без втрат. В вищесказаному розділі побудови алгоритму мною були зроблені та викладені обґрунтування алгоритму та методу стиснення без втрат. Проаналізувавши їх , зараз я наведу негативні та позитивні сторони алгоритму та деяку хитрість , яку використовують у алгоритмі LZW.

Переваги

· Не вимагає обчислення ймовірностей народження символів або кодів.

· Для декомпресії не треба зберігати таблицю рядків стислому файлі. Алгоритм побудований таким чином, що ми в змозі відновити таблицю рядків, користуючись тільки стисненим кодом.

· Даний тип компресії не вносить спотворень в вихідний файл, і підходить для стиснення даних будь-якого типу.

Недоліки

· Алгоритм не проводить аналіз вхідних даних тому не оптимальний[6].

Для підвищення ступеня стиснення зображень даним методом часто використовується одна «хитрість» реалізації цього алгоритму. Деякі файли, що піддаються стисненню за допомогою LZW, мають ланцюги однакових символів, які часто зустрічаються , наприклад aaaaaa ... або 30, 30, 30 ... і т. д. Їх безпосередній стиск буде генерувати вихідний код 0, 0, 5 і т.д. Питається, чи можна в цьому окремому випадку підвищити ступінь стиснення? Виявляється, це можливо, якщо домовитися про деякі дії:

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

Рисунок 1.3 -- Список кодів та потоків

· Отже, кодировщик заносить першу «а» в рядок, шукає і знаходить «а» в словнику. Додає в рядок наступну «а», знаходить, що «аа» немає в словнику. Тоді він додає запис <5>: «аа» в словник і виводить мітку <0> ( «а») в вихідний потік.

· Далі рядок иніацілізує другий «а», тобто набуває вигляду «a?» Вводиться третя «а», рядок знову дорівнює «аа», яка тепер є в словнику.

· Якщо з'являється четверта «а», то рядок «aa?» Дорівнює «ааа», якого немає в словнику. Словник поповнюється цим рядком, а на вихід йде мітка <5> ( «aa»).

· Після цього рядок иніціалізує третю «а», і т.д. і т.п. Подальший процес цілком зрозумілий.

· В результаті на виході отримуємо послідовність 0, 5, 6 ..., яка коротше прямого кодування стандартним методом LZW.

Можна показати, що така послідовність буде коректно відновлена. Декодувальник спочатку читає перший код - це <0>, якому відповідав би символ «a». Потім читає код <5>, але цього коду в його таблиці немає. Але ми вже знаємо, що така ситуація можлива тільки в тому випадку, коли додається символ дорівнює першому символу тільки що прочитаної послідовності, тобто «a». Тому він додасть в свою таблицю рядок «aa» з кодом <5>, а у вихідний потік помістить «aa». І так може бути розкодувати весь ланцюжок кодів.

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

РОЗДІЛ 2. СПЕЦІАЛЬНА ЧАСТИНА

2.1 Постановка задачі