Аналіз методів стискання коду без втрат інформації
Методичні вказівки до виконання лабораторної роботи №3
з курсу «Теорія інформації та кодування»


Шаблон оформлення звіту можна одержати тут в форматах doc або odt.

Мета роботи:
- закріпити теоретичні знання про сучасні методи стискання без втрат;
- освоїти практичні рішення зі стискання повідомлень основних типів;
- оцінити ефективність стискання з використанням різних алгоритмів.


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

У сучасних архіваторах реалізуються три принципово різних підходи: словниковий (ряд алгоритмів LZ Лемпеля–Зіва); прогнозний (реалізований, зокрема, в алгоритмі PPM «прогнозування за частковим збігом») та сортувальний (який використовує перетворення BWT Барроуза–Уїллера). Лідером популярності є словниковий метод. До його переваг належить висока швидкість обробки. Компресія тут досягається за рахунок заміни ланцюжків знаків, що повторюються, короткими посиланнями на такі ланцюжки. Для цього оброблена частина повідомлення відображується в так званому словнику. Зокрема, поширений спосіб використання словника, що «ковзає» текстом повідомлення. Саме такий спосіб реалізований у популярному алгоритмі LZMA, який додатково використовує низку удосконалень (лекція 5).

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

У певних графічних форматах застосовуються вбудовані алгоритми компактного кодування без втрат. Ці підходи особливо ефективні при компресії файлів ділової графіки, оскільки тут наявні великі одноколірні області зображень, що містять довгі ланцюжки однакових пікселів. Різні вбудовані алгоритми стискання використовуються, зокрема, у форматах PCX (кодування RLE однотипних серій знаків), GIF (словникове стискання LZ) і PNG (комбінація словникової і статистичної компресії).

Сучасним методам стискання без втрат присвячені лекції 5 та частково 7 з курсу ТІК.

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

У розділі 1 для дослідження використовується один із сучасних архіваторів 7-zip, у якому реалізовані три описані вище підходи до стискання. Для детального аналізу механізму словникової компресії застосовується демопрограма LZ-Demo.

У розділі 2 використовується програма FormatFactory, яка дозволяє, зокрема, оцінити ефективність стискання без втрат у форматах FLAC і Monkey. Для аналізу базових складових компресії звуку застосовується демонстраційна програма SoundCompressDemo.

У розділі 3 для порівняння можливостей стискання в різних графічних форматах застосовується переглядач FastStoneImageViewer.

Порядок виконання

Підготовки до виконання роботи:
1. Ознайомитися з теоретичним матеріалом, використовуючи електронний конспект лекцій 5, 7 на сайті tik-diit.dp.ua.
2. Закріпити розуміння матеріалу, використовуючи пробне тестування.
3. Завантажити архів із матеріалами для виконання лабораторної роботи. В архіві містяться згадані вище програми, а також файли з даними для оцінки ефективності стискання.

Виконання розділу 1:
1. Виконати експерименти з компресії файлів різних типів за допомогою архіватора 7-zip за алгоритмом LZMA (одна із сучасних версій словникового методу). Використовувати згідно з варіантом файли з текстовими й числовими даними форматів txt, doc і xls, а також растровий файл формату bmp і звуковий файл формату wav. Розмістити результати в табл. 3.1 звіту (додаток В). Порівняти ступінь стискання алгоритмом LZMA та кодом Хаффмена (за даними лабораторної роботи 2), а також оцінити універсальність словникового стискання.
2*. За допомогою демопрограми LZ-Demo детально розглянути механізм компресії із словником, що «ковзає». Коротко охарактеризувати у звіті основні ресурси стискання повідомлень цим методом.
3*. Виконати експерименти із компресії файлів форматів txt і doc із використанням методів LZMA (словниковий), PPMd (прогнозний) і Bzip2 (сортувальний). Розмістити результати в табл. 3.2 звіту (додаток В). Зіставити ефективність методів стискання для різних типів файлів з урахуванням обсягу пам'яті, що резервується. Розібратись із принципами стискання повідомлень у разі використання прогнозного та сортувального методів.

Виконання розділу 2:
1. Виконати експерименти зі стискання звуку із допомогою програми Format Factory:
- завантажити з Інтернет музичний файл у форматі mp3 і конвертувати його у формат wav вихідного кодування звуку. Проаналізувати параметри кодування звуку;
- виконати стискання за методами FLAC і Monkey. Оцінити одержаний ступінь компресії. Внести результати до табл. 3.3 (додаток В).
2*. За допомогою демопрограми SoundCompressDemo детально розглянути механізм компресії звуку без втрат. Коротко охарактеризувати у звіті основні етапи та переваги такого стискання. Підготуватися до розгорнутої відповіді з цих питань.

Виконання розділу 3:
1. За допомогою програми FastStoneImageViewer виконати експерименти зі збереження файлів растрового формату з фотографією (при 24-бітній глибині кольору), використовуючи формати PCX, GIF і PNG. Внести результати до табл. 3.4 звіту (додаток В). Сформулювати висновок про порівняльну ефективність стискання зображень різних типів у різних форматах.
2*. Виконати аналогічні експерименти із стискання без втрат із діаграмою Excel (при 8-бітній глибині кольору). Внести результати до табл. 3.4 звіту (додаток В). Сформулювати висновок про ефективність стискання без втрат для такого типу зображень.

Запитання та завдання для самоконтролю

До розділу 1
1. Назвіть основні типи універсальних методів стискання без втрат, які застосовуються в сучасних архіваторах.
2. Поясніть принцип стискання за допомогою словникових методів.
3. Прокоментуйте результати аналізу механізму словникового стискання за допомогою програми LZ-Demo.
4*. Дайте розгорнуту характеристику алгоритму компресії LZMA.
5*. Поясніть принцип прогнозного стискання, його переваги й недоліки.
6*. Прокоментуйте результати порівняльного аналізу методів універсальних компресії.

До розділу 2
1. Чому при стисканні звуку не набули поширення універсальні методи?
2. Назвіть базові складові спеціалізованих методів компресії звуку.
3. Прокоментуйте результати порівняльного аналізу ефективності стискання звуку без втрат (табл. 3.3).
4*. Детально поясніть спосіб кодування Райса.

До розділу 3
1. Чому стискання зображень без втрат ефективно використовувати насамперед для файлів ділової графіки, а не для фото?
2. Назвіть найпоширеніші способи компресії зображень із втратами і відповідні графічні формати.
3. Прокоментуйте результати порівняльного аналізу ефективності стискання зображень без втрат (табл. 3.4).
4*. Поясніть принцип стискання зображень з використанням палітр.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP