Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритмів архівації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2018
Тип роботи:
Лабораторна робота
Предмет:
Захист програмного забезпечення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
ЗІ
З В І Т
до лабораторної роботи №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.
09.03.2018 16:53
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора