Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритмів архівації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2009
Тип роботи:
Методичні вказівки
Предмет:
Захист інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
“ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КАФЕДРА ЗІ
/
Дослідження алгоритмів архівації
Методичні вказівки
до виконання лабораторної роботи №1
з курсу “Захист програмного забезпечення та програмні методи захисту інформації”
Львів-2009
Дослідження алгоритмів архівації: Інструкція до лабораторної роботи № 1 з курсу “Захист програмного забезпечення та програмні методи захисту інформації” для магістрів базового напряму 8.160102 “Захист інформації з обмеженим доступом та автоматизація її обробки” // Укл. кан. техн. наук, доц.. В.І. Отенко, О.В.Пашук - Львiв: Національний університет “Львівська політехніка”, 2009 – 20 с.
Укладачі кан. техн. наук, доц.. В.І. Отенко, О.В.Пашук
При участі Н.Ю. Пилипчук, Т.Ю. Тимощук,
студенти НУЛП базового напрямку Магістр
Відповідальний за
випуск В.Б. Дудикевич, д-р техн. наук, проф.
Рецензент
В інструкції викладено теоретичні дані, які стосуються досліджень алгоритмів архівації, а також дані про найбільш поширені алгоритми архівації.
Може бути використана студентами базових напрямків “Інформаційна безпека”, “Комп’ютеризовані системи автоматики і управління”, “Захист інформації з обмеженим доступом та автоматизація її обробки”, “Системи технічного захисту інформації” та інших спеціальностей.
Мета роботи:
Засвоїти поняття:
• архівація даних; • архів даних;
• програма-архіватор: • неперервне архівування;
• багатотомні архіви; • архіви, які містять засіб для розархівування (SFX);
• відновлення даних; • відновлювальні томи;
• коментар до архіву; • протокол помилок.
Вміти:
• створювати архіви даних;
• переглядати вміст архіву, видобувати файли, відображати коментарі та інформацію про архів;
• відновлювати фізично пошкоджений архів;
• видобувати файли за допомогою середовища WinRAR;
• створювати архіви, які містять засіб для розархівування (SFX);
• додавати до архіву данні;
• користуватися майстром створення архіву.
Теоречні відомості:
Архівація даних
Архіватори — це програми, що призначені для стиснення даних. Під стисненням розуміють кодування даних, у результаті якого закодований варіант займає менше дискової пам’яті, ніж вихідний. Процес стиснення даних називають архівуванням, а результат архівними даними.
Основне призначення програм резервного копіювання (програм-архіваторів) – створення копій вихідних даних на резервних носіях (стримерах, жорсткихтагнучких дисках, CD/DVD) та економія місця на диску за рахунок стиснення даних до архівного файлу. Програми-архіватори використовуються у випадках: наявності на дисках великих обсягів даних, які потрібні для майбутнього використання; перенесення даних між комп’ютерами за допомогою дискет; створення резервних копій в стислому вигляді. В результаті роботи програм–архіваторів створюються архівні файли (архіви даних).
За основу роботи програм-архіваторів покладено процедуру пошуку та перекодування однакових фрагментів вмісту файлу. Наприклад, розглянемо файл, який містить багато однотипних слів: комп’ютер, комп’ютера, комп’ютерна, комп’ютеризація тощо. Якщо набір символів “комп’ютер” замінити на “чц”, тоді розглянута послідовність слів перетвориться в послідовність: “чц”, “чца”, “чцна”, “чцизація” тощо. При такій заміні вихідний текст дійсно зменшується. Однак в реальних програмах-архіваторах процедура пошуку та перекодування даних відбувається значно складніше.
Найбільш поширені програми-архіватори: 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 :
Номер в рамці – це сума частот символів D і A. Тепер ми знову шукаємо два символи з найнижчими частотами входжень. Виключаючи з перегляду D і A та розглядаючи замість них новий “вузол” з сумарною частотою входжень. Найнижча частота тепер у F і нового вузла. Знову зробимо операцію злиття вузлів :
Розглядаємо таблицю знову для наступних двох символів ( B і E ).
Ми продовжуємо в цей режим доки все "дерево" не сформовано, тобто доки все не зведеться до одного вузла.
Тепер коли наше дерево створене, ми можемо кодувати файл . Ми повинні завжди починати з кореня ( 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. Арифметичне кодування
Абсолютно інше рішення пропонує т.з. арифметичне кодування. Арифметичне кодування є методом, що дозволяє упаковувати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів і є найбільш оптимальним, оскільки досягається теоретичний кордон міри стискування.
Передбачувана необхідна послідовність символів, при стисненні методом арифметичного кодування розглядається як деякий двійковий дріб з інтервалу [0, 1). Результат стиснення представляється як послідовність двійкових цифр із запису цього дробу.
Ідея методу полягає в наступному: вихідний текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, пропорційною вірогідності його появи. Цим пояснюється інтервал, відповідний мінімальній і максимальній вірогідності появи символу в потоці.
Приклад:
Нехай алфавіт складається з двох символів: а і 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), де length - довжина знайденої в словнику стрічки, а distance - відстань від неї до вхідної стрічки (тобто фактично індекс стрічки в буфері, вирахуваний з його розміру).
В разі, якщо така стрічка не знайдена, у вихідний потік просто копіюється черговий символ вхідного потоку.
У первинній версії алгоритму пропонувалося використовувати простий пошук по всьому словнику. Проте, надалі, було запропоновано використовувати двійкове дерево і хешування для швидкого пошуку в словнику, що дозволило на порядок підняти швидкість роботи алгоритму.
Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вихідних символів в два паралельні потоки довжин і індексів в таблиці (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.
Зміст звіту:
1. Назва і мета роботи.
2. Короткі теоретичні відомості.
3. Результати виконання роботи.
4. Висновок.
ЛАБОРАТОРНЕ ЗАВДАННЯ
Варіант
Опис дій
1
1.Ознайомитись з роботою архіваторів RARі ZIP.
2.За допомогою архіваторів RARі ZIPстиснути файли типів Txt., JPG,AVI, DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стиснення файлів.
4.Встановити найкращий метод стиснення.
2
1.Ознайомитись з роботою архіваторів QUARKі ZIP.
2.За допомогою архіваторів QUARKі ZIPстиснути файли типів Txt., JPG,AVI, DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стиснення файлів.
4.Встановити найкращий метод стиснення.
3
1.Ознайомитись з роботою архіваторів RARі QUARK.
2.За допомогою архіваторів RARі QUARKстиснути файли типів Txt., JPG,AVI, DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стиснення файлів.
4.Встановити найкращий метод стиснення.
4
1.Ознайомитись з роботою архіваторів ARJі ZIP.
2.За допомогою архіваторів ARJі ZIPстиснути файли типів Txt.,JPG,AVI, DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стиснення файлів.
4.Встановити найкращий метод стиснення.
5
1.Ознайомитись з роботою архіваторів RARі ARJ.
2.За допомогою архіваторів RARі ARJстиснути файли типів Txt., JPG,AVI,DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стиснення файлів.
4.Встановити найкращий метод стиснення.
6
1.Ознайомитись з роботою архіваторів ARJі QUARK.
2.За допомогою архіваторів ARJі QUARKстиснути файли типів Txt., JPG,AVI, DLL.
3.На основі отриманих результатів визначити: швидкодію стиснення, степінь стиснення і якість стисненняфайлів.
4.Встановити найкращий метод стиснення.
Контрольні запитання
Список використаної літератури
НАВЧАЛЬНЕ ВИДАННЯ
"Дослідження алгоритмів архівації"
Інструкція до лабораторної роботи №1
з курсу: “Захист програмного забезпечення та програмні методи захисту інформації”
для магістрів базового напряму 8.160102 “Захист інформації з обмеженим доступом та автоматизація її обробки”
Укладачі кан. техн. наук, доц.. В.І. Отенко, О.В.Пашук
22.05.2013 19:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора