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

Київський національний університет будівництва і архітектури Курсова робота з дисципліни «Теорія інформації та кодування» на тему «Універсальний алгоритм стиснення даних без втрат Лемпеля-Зіва-Велча LZW»Основоположником науки про стиснення інформації прийнято вважати Клода Шеннона. Крім того, їм були проведені досліди за емпіричною оцінкою надмірності англійського тексту. На основі ряду дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0.6 - 1.3 біта на символ. Перші алгоритми стиснення були примітивними в звязку з тим, що була примітивною обчислювальна техніка. Справжнім проривом був винахід Лемпелем і Зивом в 1977 р словникових алгоритмів.Стиснення без втрат - метод стиснення даних, при використанні якого закодована інформація може бути повністю відновлена зі стиснутих даних. Навпроти, стиснення з втратами дозволяє лише відновлення даних, які є тільки наближенням до початкових даних. Стиснення без втрат використовується, коли важливо, щоб відновленні дані були ідентичні оригіналу. Деякі графічні файлові формати, наприклад, PNG та GIF використовують тільки стиснення без втрат, тоді як формати TIFF та MNG можуть використовувати стиснення як з втратами, так й без втрат. Формати стиснення звуку без втрат використовується для архівування або виробничих цілей, в той час, як менші формати стиснення аудіо з втратами використовуються в аудіопрогравачах та в ситуаціях коли простір для зберігання інформації обмежений або нема потреби в точному відтворенні інформації.Суть алгоритму полягає в тому, що ланцюжки подій поміщаються в словник. Якщо в подальшому у вхідному потоці зустрічається ланцюжок подій, яка присутня в словнику, то замість цього ланцюжка в вихідний потік міститься посилання на елемент словника. Ідея була втілена в алгоритмі ЛЗ77, який став основою цілого сімействі алгоритмів. Щоб забезпечити відмінність між ланцюжками подій і літеральние подіями(подіями не ввійшли ланцюжка зі словника) алгоритм LZ77 просто чергує посилання на елементи словника з литеральними подіями. Щоразу коли ланцюжок зі словника зустрічається у вхідному потоці в алгоритмі LZ78 також як і в LZ77 літеральні події та елементи словника чергувалися.Якщо такий рядок існує, зчитується наступний символ, а якщо рядок не існує, в потік заноситься код для попередньої знайденої рядки, рядок заноситься в таблицю, а пошук починається знову. Якщо фраза ? (K) вже є в словнику, привласнити вхідний фразі значення ? (K) і перейти до кроку 2, інакше видати код ?, додати ? (K) в словник, привласнити вхідний фразі значення K і перейти до кроку 2. Щоб форматувати таблицю, ми встановимо відповідність коду 0 відповідному символу з двійкового кодом 00000000, тоді 1 відповідає символу з кодом 00000001, і т.д., до коду 255. § Крок 1: Тоді, відповідно до викладеного вище алгоритму, ми додамо до спочатку порожній рядку "a" і перевіримо, чи є рядок "a" в таблиці. Оскільки ми при ініціалізації занесли в таблицю всі рядки з одного символу, то рядок "a" є в таблиці.В вищесказаному розділі побудови алгоритму мною були зроблені та викладені обґрунтування алгоритму та методу стиснення без втрат. · Не вимагає обчислення ймовірностей народження символів або кодів. Для підвищення ступеня стиснення зображень даним методом часто використовується одна «хитрість» реалізації цього алгоритму. Виявляється, це можливо, якщо домовитися про деякі дії: Ми знаємо, що для кожного коду треба додавати в таблицю рядок, що складається з уже наявного там рядку і символу, з якого починається наступний рядок в потоці. · Далі рядок иніацілізує другий «а», тобто набуває вигляду «a?» Вводиться третя «а», рядок знову дорівнює «аа», яка тепер є в словнику.Користувач запучкає програму , у головному вікні потрібно ввести текст повідомлення , яке буде використано для кодування.Результат роботи виводить стиснене повідомлення та розмір в бітах.Дана програма використовує алгоритм LZW. Зараз я опишу свою програму та для прикладу зроблю стиснення з декількома повідомленнями. Для початку зробимо запуск програми і побачимо головне вікно (Рисунок 2.1). Рисунок 2.1 Головне вікно програми Далі ми вводиму повідомлення для стиснення , натискаємо кнопку компрессія , та бачимо результат.З обґрунтування теми моєї курсової роботи можна сказати , що алгоритм LZW стиснення без втрат був в певній мірі обгрунтований , було наведено приклади роботи даного алгоритму , наведено переваги та недоліки алгоритму та виконано аналіз всієї роботи.using System; using System.Collections.Generic; using System.Text; using System.Windows.Forms; {string text = TEXTBOX1.

ЗМІСТ

Вступ

Розділ 1. Загальні відомості

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

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

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

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

Розділ 2. Спеціальна частина

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

2.2 Вхідні та вихідні дані

2.3 Опис алгоритму

Висновки

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

Додаток