Дослідження алгоритмів архівації. Лабораторна робота з Захист інформації. Робота № 524842

Перехід до торгівельного партнера Binance

Дослідження алгоритмів архівації

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

УІ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2012

Тип роботи:

Лабораторна робота

Предмет:

Захист інформації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Лабораторна роботи №1 на тему “ Дослідження алгоритмів архівації” з курсу “Захист програмного забезпечення та програмні методи захисту інформації” Львів-2012 Теоретичні відомості: Архівація даних Архіватори — це програми, що призначені для стиснення даних. Під стисненням розуміють кодування даних, у результаті якого закодований варіант займає менше дискової пам’яті, ніж вихідний. Процес стиснення даних називають архівуванням, а результат архівними даними. За основу роботи програм-архіваторів покладено процедуру пошуку та перекодування однакових фрагментів вмісту файлу. Наприклад, розглянемо файл, який містить багато однотипних слів: комп’ютер, комп’ютера, комп’ютерна, комп’ютеризація тощо. Якщо набір символів “комп’ютер” замінити на “чц”, тоді розглянута послідовність слів перетвориться в послідовність: “чц”, “чца”, “чцна”, “чцизація” тощо. При такій заміні вихідний текст дійсно зменшується. Однак в реальних програмах-архіваторах процедура пошуку та перекодування даних відбувається значно складніше. Найбільш поширені програми-архіватори: ARJ, RAR, PKZIP (з розархіватором PKUNZIP), LHARC, ICE, WinRAR. Алгоритми стиснення (архівації) даних Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів. Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є : • степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і результуючого потоків; • швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку; • якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом. Всі способи стиснення можна поділити на дві категорії: зворотнє і незворотнє. Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних). Такі підходи і алгоритми використовуються для стиснення, наприклад, даних растрових графічних файлів з низькою повторюваністю байтів у потоці. При такому підході використовується властивість структури формату графічного файлу і можливість подати графічний рисунок приблизно схожу за якістю відображення (для сприйняття людським оком) декількома способами. Тому, крім рівня або величини стиснення, в таких алгоритмах виникає поняття якості, оскільки вихідне зображення в процесі стиснення змінюється, то під якістю можна розуміти рівень відповідності вхідного і результуючого зображення, що оцінюється суб’єктивно, враховуючи формат даних. Для графічних файлів така відповідність визначається візуально, хоча є і відповідні інтелектуальні алгоритми і програми. Незворотнє стиснення неможливо застосовувати тоді, коли потрібно мати точну відповідність структури вхідного і вихідного потоків. Даний підхід реалізовано в популярних форматах подання відео і фото інформації, відомих як JPEG і JFIF алгоритми і JPG і JIF формати файлів. Зворотнє стиснення завжди призводить до зменшення вихідного потоку даних без зміни його інформативності, тобто – без втрати інформаційної структури. Більше того, з вихідного потоку, за допомогою поновлювального або декомпресійного алгоритму, можна отримати вхідний, а процес поновлення називається декомпресією або розпакуванням і тільки після процесу розпакування дані можна використовувати для опрацювання у відповідності до їх внутрішнього формату. Перейдемо тепер безпосередньо до алгоритмічних особливостей зворотних алгоритмів і розглянемо найважливіші теоретичні викладки до стиснення даних, які пов’язані з реалізацією систем , що кодуються та способами стиснення даних. 1. Стиснення способом кодування серій (RLE) Найбільш відомий простий підхід та алгоритм стиснення даних зворотнім шляхом – це кодування серій послідовностей (Run Length Encoding - RLE). Суть методів даного підходу складається у заміні ланцюжків або серій байтів, що повторюються або їх послідовностей на один кодуючий байт та лічильник числа їх повторень. Наприклад: 44 44 44 11 11 11 11 11 01 33 FF 22 22 – вхідна послідовність 03 44 04 11 00 03 01 FF 02 22 – стиснена послідовність Перший байт вказує скільки раз потрібно повторити наступний байт. Якщо перший байт дорівнює 00, тоді за ним слідує лічильник, який вказує кількість даних, що не повторюються. Ці методи, як правило , достатньо ефективні для стиснення растрових зображень (BMP, PCX, TIF, GIF), тому що останні містять достатньо багато довгих серій послідовностей байтів, що повторюються. Недоліком методу RLE є достатньо низький ступінь стиснення. Наведемо приклади програм – архіваторів, які працюють за цим алгоритмом: PKPAK 3.61 2. Алгоритм Хаффмана Стискаючи файл за алгоритмом Хаффмана перше, що потрібно зробити – це прочитати файл повністю та підрахувати скільки раз зустрічається кожний символ з розширеного набору ASCII. Якщо враховувати усі 256 символів, то не буде ніякої різниці в стисненні текстового та ЕХЕ файлу. Після підрахунку частоти входжень кожного символу, потрібно переглянути таблицю кодів ASCII і сформувати бінарне дерево. Наприклад: Розглянемо файл довжиною в 100 байт, що містить 6 різних символів. Підрахуємо входження кожного з символів у файл та отримаємо наступне: Візьмемо ці числа і назвемо їх частотою входжень для кожного символа. Візьмемо з останньої таблиці 2 символи з найменшою частотою, у нашому випадку це D (5) та якийсь символ з F або А (10), можемо вибрати довільних серед них, наприклад А. Сформуємо з "вузлів " D і A новий "вузол", частота входжень для якого буде дорівнювати сумі частот D і A : Тепер коли наше дерево створене, ми можемо кодувати файл . Ми повинні завжди починати з кореня ( Root ). Кодуючи перший символ (аркуш дерева З) Ми прослідковуємо вгору по дереву всі повороти гілок і якщо ми робимо лівий поворот, то запам'ятовуємо 0-й біт, і аналогічно 1-й біт для правого повороту. Так для C, ми йтимемо вліво до 55 ( і запам'ятаємо 0 ), потім знову вліво (0) до самого символу . Код Хаффмана для нашого символу C - 00. Для наступного символу ( А ) у нас виходить - ліво, право, ліво, ліво, що виливається в послідовність 0100. Виконавши вище сказане для всіх символів отримаємо: C = 00 ( 2 біта )A = 0100 ( 4 біта )D = 0101 ( 4 біта )F = 011 ( 3 біта )B = 10 ( 2 біта )E = 11 ( 2 біта ) При кодуванні замінюємо символи на дані послідовності. Наведемо приклади програм – архіваторів, які працюють за цим алгоритмом: PKPAK 3.61, PKZIP 1.10, LHArc, LHA,QUARK, ARJ. 3. Арифметичне кодування Абсолютно інше рішення пропонує т.з. арифметичне кодування. Арифметичне кодування є методом, що дозволяє упаковувати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів і є найбільш оптимальним, оскільки досягається теоретичний кордон міри стискування. Приклад: Нехай алфавіт складається з двох символів: а і b з вірогідністю відповідно 0,75 і 0,25. Розглянемо наш інтервал вірогідності [0, 1). Розіб'ємо його на частини, довжина яких пропорційна вірогідності символів. У нашому випадку це [0; 0,75) і [0,75; 1). Суть алгоритму в наступному: кожному слову у вхідному алфавіті відповідає деякий підінтервал з інтервалу [0, 1) а порожному слову відповідає весь інтервал [0, 1). Після здобуття кожного наступного символу інтервал зменшується з вибором частини, яка відповідає новому символу. Кодом ланцюжка є інтервал, виділений після обробки всіх її символів, точніше, двійковий запис будь-якої крапки з цього інтервалу, а довжина отриманого інтервалу пропорційна вірогідності появи кодованого ланцюжка. Застосуємо даний алгоритм для ланцюжка “aaba”: Кордони інтервалу обчислюються так: береться відстань всередині інтервалу (0,5625-0,421875 = 0,140625), ділиться на частоти [0; 0,10546875) і [0,10546875; 1) і знаходяться нові кордони [0,421875; 0,52734375) і [0,52734375; 0,5625). Як код можна узяти будь-яке число з інтервалу, отриманого на кроці 4, наприклад, 0,43. Алгоритм декодування працює аналогічно тому, що кодує. На вході 0,43 і йде розбиття інтервалу. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи. Для того, щоб декодуючий алгоритм міг визначити кінець ланцюжка, ми можемо або передавати її довжину окремо, або додати до алфавіту додатковий унікальний символ – “кінець ланцюжка”. 4. Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW) Даний алгоритм відрізняють висока швидкість роботи як при упаковці, так і при розпаковуванні, досить скромні вимоги до пам'яті і проста апаратна реалізація. Недолік - низька міра стиснення в порівнянні з схемою двоступінчатого кодування. Передбачимо, що у нас є словник, що зберігає рядки тексту і що містить порядку від 2-х до 8-ми тисяч пронумерованих гнізд. Запишемо в перших 256 гнізд рядки, що складаються з одного символу, номер якого дорівнює номеру гнізда. Алгоритм переглядає вхідний потік, розбиваючи його на підрядки і додаючи нові гнізда в кінець словника. Прочитаємо декілька символів в рядок s і знайдемо в словнику рядок t - щонайдовший префікс s. Хай він знайдений в гнізді з номером n. Виведемо число n у вихідний потік, перемістимо покажчик вхідного потоку на length(t) символів вперед і додамо в словник нове гніздо, що містить рядок t+c, де с - черговий символ на вході (відразу після t). Алгоритм перетворить потік символів на вході в потік індексів комірок словника на виході. При практичній реалізації цього алгоритму слід врахувати, що будь-яке гніздо словника, окрім найперших, таких, що містять одно-символьні ланцюжки, зберігає копію деякого іншого гнізда, до якої в кінець приписаний один символ. Внаслідок цього можна обійтися простою обліковою структурою з одним зв'язком. Приклад: ABCABCABCABCABCABC - 1 2 3 4 6 5 7 7 7 1 A 2 B 3 C 4 AB 5 BC 6 CA 7 ABC 8 CAB 9 BCA Наведемо приклади програм – архіваторів, які працюють за цим алгоритмом: PKPAK 3.61, PKZIP 1.10. 5. Двоступінчате кодування. Алгоритм Лемпеля-Зіва Великої степені стиснення можна добитися при виділенні з вхідного потоку ланцюжків, що повторюються, блоків, і кодуванням посилань на ці ланцюжки з побудовою хеш-таблиць від першого до n-го рівня. Метод, про який і піде мова, належить Лемпелю і Зіву і зазвичай називається LZ-compression. Суть його полягає в наступному: пакувальник постійно зберігає деяку кількість останніх оброблених символів в буфері. У міру обробки вхідного потоку символи, що знов поступили, потрапляють в кінець буфера, зрушуючи попередні символи і витісняючи найстаріші. Розміри цього буфера, названого також ковзаючим словником (slidingdictionary), варіюються в різних реалізаціях кодуючих систем. Експериментальною шляхом встановлено, що програма LHarc використовує 4-кілобайтний буфер, LHA і PKZIP - 8-ми, а ARJ - 16-кілобайтний. В разі, якщо така стрічка не знайдена, у вихідний потік просто копіюється черговий символ вхідного потоку. У первинній версії алгоритму пропонувалося використовувати простий пошук по всьому словнику. Проте, надалі, було запропоновано використовувати двійкове дерево і хешування для швидкого пошуку в словнику, що дозволило на порядок підняти швидкість роботи алгоритму. Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вихідних символів в два паралельні потоки довжин і індексів в таблиці (length + distance). Вочевидь, що ці потоки є потоками символів з двома новими алфавітами, і до них можна застосувати один із згадуваних вище методів (RLE, кодування Хаффмана або арифметичне кодування). Так ми приходимо до схеми двоступінчатого кодування - найбільш ефективної з практично використовуваних в даний час. При реалізації цього методу необхідно добитися погодженого виведення обох потоків в один файл. Ця проблема зазвичай вирішується шляхом почергового запису коду символів з обох потоків. Приклад: Перший рівень abcabcabcabcabc - 1 а 1 b 1 з 3 3 6 3 9 3 12 3 Другий рівень - виключення великої групи послідовностей, що повторюються 1 а 1 b 1 з 12 3і стиснення RLE, кодування Хаффмана, арифметичне кодування. Наведемо приклади програм – архіваторів, які працюють за цим алгоритмом: LHArc, LHA, ARJ, GZIP,QUARK,Zip, PKZIP. Виконання роботи Txt файл – 20kb Архіватор швидкодія стиснення степінь стиснення якість стиснення файлів WinRar <1c 2.5 5 Quark <1c 2.8 5 На виході з WinRar Txt файл – 8kb На виході з Quark Txt файл – 6kb Jpg файл – 292kb Архіватор швидкодія стиснення степінь стиснення якість стиснення файлів WinRar 1c 92 5 Quark 1c 92 5 На виході з WinRar Jpg файл – 268kb На виході з Quark Jpg файл – 268kb AVI файл – 195mb Архіватор швидкодія стиснення степінь стиснення якість стиснення файлів WinRar 2:03 98 5 Quark 19c 98 5 На виході з WinRar AVI файл – 193mb На виході з Quark AVI файл – 97,4mb Dll файл – 1.1mb Архіватор швидкодія стиснення степінь стиснення якість стиснення файлів WinRar 2c 24 5 Quark 1c 31 5 На виході з WinRar AVI файл – 328kb На виході з Quark AVI файл – 256kb Висновок: При порівнянні двох архіваторів WinRar і з Quark виявилося що для різного типу файлів вони мають різну степінь стиснення, що в свою чергу залежить від структури файлу. Різну степінь стиснення можна пояснити різними алгоритмами кодування і своєрідністю кожного файлу. Quark домагається кращих результатів у компактності даних, тому що: Quark працює з плаваючим розміром вікна від 32Kb до 64Kb (проти фіксованих 16Kb у LHA, та 32Kb у PkZIP та ARJ). Quark виконує оптимізацію Першого роду (оптимальність адрес посилань LZ77) та оптимізацію Другого роду (оптимальність посилального покриття потоку). Quark використовує текстову редукцію для текстових файлів. Quark заносить в архів мінімум службової інформації, не претендуючи на інші апаратні платформи та операційні системи.

Лабораторна робота Захист інформації

Tatti

18.09.2013 12:09-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись