МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна роботи №1 на тему “ Дослідження алгоритмів архівації” з курсу “Захист програмного забезпечення та програмні методи захисту інформації” Львів-2012 Теоретичні відомості: Архівація даних Архіватори — це програми, що призначені для стиснення даних. Під стисненням розуміють кодування даних, у результаті якого закодований варіант займає менше дискової пам’яті, ніж вихідний. Процес стиснення даних називають архівуванням, а результат архівними даними. За основу роботи програм-архіваторів покладено процедуру пошуку та перекодування однакових фрагментів вмісту файлу. Наприклад, розглянемо файл, який містить багато однотипних слів: комп’ютер, комп’ютера, комп’ютерна, комп’ютеризація тощо. Якщо набір символів “комп’ютер” замінити на “чц”, тоді розглянута послідовність слів перетвориться в послідовність: “чц”, “чца”, “чцна”, “чцизація” тощо. При такій заміні вихідний текст дійсно зменшується. Однак в реальних програмах-архіваторах процедура пошуку та перекодування даних відбувається значно складніше. Найбільш поширені програми-архіватори: ARJ, RAR, PKZIP (з розархіватором PKUNZIP), LHARC, ICE, WinRAR. Алгоритми стиснення (архівації) даних Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів. Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є : • степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і результуючого потоків; • швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку; • якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом. Всі способи стиснення можна поділити на дві категорії: зворотнє і незворотнє. Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних). Такі підходи і алгоритми використовуються для стиснення, наприклад, даних растрових графічних файлів з низькою повторюваністю байтів у потоці. При такому підході використовується властивість структури формату графічного файлу і можливість подати графічний рисунок приблизно схожу за якістю відображення (для сприйняття людським оком) декількома способами. Тому, крім рівня або величини стиснення, в таких алгоритмах виникає поняття якості, оскільки вихідне зображення в процесі стиснення змінюється, то під якістю можна розуміти рівень відповідності вхідного і результуючого зображення, що оцінюється суб’єктивно, враховуючи формат даних. Для графічних файлів така відповідність визначається візуально, хоча є і відповідні інтелектуальні алгоритми і програми. Незворотнє стиснення неможливо застосовувати тоді, коли потрібно мати точну відповідність структури вхідного і вихідного потоків. Даний підхід реалізовано в популярних форматах подання відео і фото інформації, відомих як JPEG і JFIF алгоритми і JPG і JIF формати файлів. Зворотнє стиснення завжди призводить до зменшення вихідного потоку даних без зміни його інформативності, тобто – без втрати інформаційної структури. Більше того, з вихідного потоку, за допомогою поновлювального або декомпресійного алгоритму, можна отримати вхідний, а процес поновлення називається декомпресією або розпакуванням і тільки після процесу роз...