МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА ЗІ
З В І Т до лабораторної роботи №1 з дисципліни: «Захист програмного забезпечення» на тему: «Дослідження алгоритмів архівації» Львів 2017 Мета роботи: Розглянути основні методи стиску інформації. Навчитися на практиці реалізовувати дані алгоритми. Короткі теоретичні відомості Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є : • степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і вихідного потоків; • швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку; • якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом. Алгоритм Хоффмана (Гаффмана) Цей метод кодування складається з двох основних етапів: Побудова оптимального кодового дерева. Побудова відображення код-символ на основі побудованого дерева. Ідея алгоритму така: знаючи ймовірності появи символів у повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілої кількості бітів. Символам з більшою ймовірністю ставляться у відповідність коротші коди. Коди Гаффмана володіють властивістю префіксності (тобто жодне кодове слово не є префіксом іншого), що дозволяє однозначно їх декодувати. Класичний алгоритм Гаффмана на вході отримує таблицю частот з якими зустрічаються символи у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Гаффмана (Н-дерево). Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, яка може бути рівною або ймовірності, або кількості входжень символу у стиснене повідомлення. Вибираються два вільних вузли дерева з найменшими вагами. Створюється їхній батьківський вузол з вагою, рівною їх сумарній вазі. Вузол-батько додається в список вільних вузлів, а два його нащадки видаляються з цього списку. Одній дузі, котра виходить з вузла батька, ставиться у відповідність біт 1, інший — біт 0. Кроки, починаючи з другого, повторюються доти, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева. Хід виконання роботи 1. Кодуємо послідовність слів «Національний університет «Львівська політехніка»» за допомогою відповідного програмного забезпечення.
2. Представляємо даний текст у вигляді бітової послідовності.
3. Кодове представлення символів.
Основна частина становить: 207 біт. Дерево бітових кодів становить: 219 біт. Середня довжина коду становить: 4.31 біт. Теоретичний максимум: 4.26 біт. Коефіцієнт стиснення: 1.86 (з урахуванням дерева бітових кодів 0,90). Середній коефіцієнт стиснення: 1.88. Висновок: Стиснення даних Гаффмана застосовується під час стиснення фото- і відеозображень (JPEG, стандарти стиснення MPEG), в архіваторах (PKZIP, LZH та ін), в протоколах передачі даних MNP5 і MNP7.