Презентація на тему:
Стиснення і архівація даних

Стиснення і архівація даних Підгірненська загальноосвітня школа І-ІІІ ступенів Автор: вчитель інформатики Миланко Володимир

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

Об’єкти стиснення Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації

Алгоритми стиснення даних Алгори тм Ле мпеля — Зіва — Ве лча (LZW) Алгоритм Хаффмана Алгоритм- RLE (Run Length Encoding)

Алгоритм LZW Опис : Даний алгоритм при кодуванні динамічно створює таблицю перетворення строчок в якій певним послідовностям символів (слів) ставиться у відповідність групи біт фіксованої довжини. В ході кодування алгоритм переглядає текст символ за символом, і зберігає кожну нову унікальну 2-символьну строчку в таблицю у вигляді пари код/символ . Після зберігання нової 2-символьної строчки в таблиці, на вихід передається код першого символа. Коли на виході читається черговий символ для нього по таблиці знаходиться строчка максимальної довжини яка уже повторювалася , після чого в таблиці збережеться код цієї строчки зі наступним символом на вході; на вихід подається код цієї строчки, а наступний символ використовується в якості початку наступної строчки. Повідомлення яке необхідно стиснути має такий вигляд TOBEORNOTTOBEORTOBEORNOT# Маркер # показує про закінчення повідомлення. Таким чином в нашому алфавіті 27 символів (26 букв від A до Z і #). Комп’ютер представляє їх у вигляді груп біт, для позначення одного символа достатньо групи з 5 біт. 5-бітні групи утворюють 25 = 32 можливих комбінацій біт, тому коли в словнику з’явиться 33-е слово (символ), алгоритм має перейти на 6-бітні групи кодування. Приклад

Початковий словник має вигляд: Перекодування (стиснення) Алгоритм LZW Символ: Бітовий код: Новий запис словника: (на виході) T 20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: OR початок кодування 6-бітнимигрупами N 14 = 001110 32: RN O 15 = 001111 33: NO T 20 = 010100 34: OT TO 27 = 011100 35: TT BE 29 = 011110 36: TOB OR 31 = 100000 37: BEO TOB 36 = 100101 38: ORT EO 30 = 011111 39: TOBE RN 32 = 100001 40: EOR OT 34 = 100011 41: RNO # 0 = 000000 42: OT# Без використання алгоритму LZW, при передачі повідомлення в 25 символів по 5 біт на кожен символ повідомлення займе обсяг 125 біт. В И С Н О В О К: Загальна довжина коду = 6*5 + 11*6 = 96 бит. # 00000 A 00001 B 00010 C 00011 . . . . . . Z 11010 При перекодуванні заLZW довжина коду зменшується на 29 біт (125-96=29) Ступінь стиснення становить 22%

CBBDACDEEFA…………FE (всього 100 символів) Файл утворений з 6 різних символів частота повторення яких вказана в таблиці: Закодуємо більш вживані символи у файлі меншою кількістю біт 1-3, і навпаки. Отримали архівний файл обсягом 30 байт (240 біт) коефіціент стисненя становить 30% C = 00 ( 2 біта ) A = 0100 ( 4 біта ) D = 0101 ( 4 біта ) F = 011 ( 3 біта ) B = 10 ( 2 біта ) E = 11 ( 2 біта ) Алгоритм Хафмана Визначивши ймовірність входження символів в повідомлення можна описувати процедуру побудови коду змінної довжини Ідея: Приклад: Мали файл обсягом 100 байт (800 біт) Частота До стиснення Після стиснення Зменшилось на C30 30*8=240 30*2=60 180 A10 10*8=80 10*3=30 50 D5 5*8=40 5*4=20 20 F10 10*8=80 10*4=40 40 B20 20*8=160 20*2=40 120 E25 25*8=200 25*2=50 150 символ A B C D E F число повторень 10 20 30 5 25 10

Приклад: Алгоритм- RLE (Run Length Encoding) Опис: В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Нехай задана така послідовність даних, що підлягає стисненню: 1 1 1 1 2 2 3 4 4 4 В алгоритмі RLE пропонується замінити її наступною структурою: 1 4 2 2 3 1 4 3, де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті.

ПРОГРАМИ - АРХІВАТОРИ WinZIP . WinRAR. 7-Zip. Winace. PowerArhiver. ArjFolder. Резервне копіювання даних з метою їх довготривалого збереження Стиснення даних з метою економії обсягу пам’яті на носії Основні функції програм: створення архіві файлів і папок додавання файлів і папок до вже існуючих архівів перегляд вмісту архівів зміна і оновлення файлів і папок в архіві видобування з архіву всіх або тільки вибраних файлів і папок створення багатотомних архівів створення архівів з фунцією самовидобування файлів і папок перевірка цілісності даних в архівах шифрування даних та імен файлів в архівах перевірка на віруси в архіві до розпакування; захист архівів паролями від несанкціонованого доступу; Призначення:

Архіватор 7-Zip Відкриття архіву Додавання файла до архіву

Архіватор 7-Zip Параметри стиснення Процес стиснення

Об’экт , що підлягав архівації Архів

Обсяг об’єкта до архівації 109 Мб Обсяг архівного файла 90,3 Мб

Методи стиснення: Стиснення з регульованими втратами інформації Стиснення без втрати інформації Цей метод можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. графічні дані відеодані аудіодані MPG MP3 JPEG GIF TIFF AVI ZIP ARJ RAR CAB Графічні дані Відеодані Довільні типи даних При стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадку з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення

Значки архівних файлів CAB SFX SFX RAR ZIP ZIP

Контрольні запитання: Завдяки чому можливе стиснення даних? Які бувають методи стиснення ? Для чого створюють архіви? Які основні функції архіватора 7-ZIP ? Що таке багатотомний і саморозпакувальний архів? Як додати файл до архіву? Як видобути файл з архіву?

Автор презентації Миланко В. М. Підгірненська ЗОШ І-ІІІ ступенів Новомиколаївського району Запорізької області vlad_milen@ukr.net Використані джерела: Навчальна програма для учнів 9 класу загальноосвітніх навчальних закладів. Інформатика. http://ru.wikipedia.org/wiki http://uk.wikipedia.org/wik