Стиснення та архівування даних. Види стиснення даних

 Загальні поняття про архівацію та стиснення файлів

Архівація і стиснення

З розвитком інформаційних технологій гостро постало питання щодо спо­собів зберігання даних. Починаючи з сорокових років XX ст., вчені розробляють методи представлення даних, за яких простір на носіях інформації використо­вувався б економніше. Результатом цього стала технологія стиснення й архівації даних (англійською мовою backup).

Архівація даних - це злиття кількох файлів чи каталогів до єдиного файла - архіву. Стиснення даних є скороченням обсягу вихідних файлів шляхом усунення надлишкової інформації.

Для виконання цих завдань є програми-apxiватоpu, які забезпечують як архівацію, так і стиснення даних. За допомогою спеціальних алгоритмів архі­ватори видаляють з файлів усю надмірну інформацію, а при зворотних операціях розпаковування вони відновлюють інформацію у первісному вигляді. При цьому стиснення та відновлення інформації відбувається без втрат. Стиснення без втрат актуальне при роботі з текстовими і програмними файлами, у задачах криптографії.

Існують також методи стиснення із втратами. Вони видаляють з потоку інформацію, яка незначно впливає на дані або взагалі не сприймається людиною. Такі методи стиснення застосовуються для аудіо- та відеофайлів, деяких фор­матів графічних файлів.

 

Методи стискання даних без втрат

            На сьогодні розроблено багато способів стискання без втрат, в основі їх лежать такі методи кодування:

• Групове кодування RLE (Run Length Encoding) - один з найстаріших мето­дів стиснення, який використовується в основному для архівації графіки.
• Кодування Хаффмана (англ. Huffman) - в основі лежить той факт, що деякі символи в тексті можуть траплятися частіше середньої частоти повторень, а інші - рідше.
• Кодування Лемпеля-Зіва (англ. Lempel, Ziv) - використовує факт неод­норазового повторення фрагментів тексту, тобто послідовностей байтів. Практично всі популярні програми-архіватори без втрат (ARJ, RAR, ZIP тощо) застосовують методи Лемпеля-Зіва і Хаффмана (так званий алгоритм LZH - за початковими літерами прізвищ авторів).

 

Групове кодування RLE

Подамо зображення у числовому вигляді як ланцюжок байтів, записаних по рядках растру. Послідовності байтів, що повторюються, замінимо парою чисел: перше число буде представляти колір, а друге - кількість пікселів. Тоді, наприк­лад, такий рядок зображення

що описаний байтами:

255   255   255   255   128   128   0   0   0   0   0

буде подано як

255   4   128   2   0   5

Замість 11 байтів для запису цього рядка потрібно буде 6 байтів. Зрозуміло, що ступінь ущільнення залежатиме від характеру зображення та наявності дов­гих ланцюжків з байтами, що повторюються. Це виконується для зображень з великими одноколірними ділянками. Зображення, в яких мало сусідніх пікселів однакового кольору, не придатні для стиснення по методу RLE. Розмір стис­нутого файла в такому разі може перевищувати розмір вихідного файла.

Кодування Хаффмана

Нагадаємо, що при кодуванні текстової інформації кожному символу відво­диться 1 байт. Однак на прак­тиці одні символи у конкретному тексті трапляються частіше, інші - рідше. Основою методу Хаффмана є те, що для запису поширених символів використо­вуються короткі послідовності біт (довжиною менше 8 біт), а для запису рідкісних символів - довгі. При цьому сумарний обсяг файла зменшується,

Хаффман запропонував дуже простий графічний спосіб визначення того, якому символу потрібно присвоїти певний код. Уникаючи подробиць покажемо дію методу на прикладі кодування слова «інфінітив». Частота появи літер у цьому слові така:

і-3;                           т-1;

н-2;                          и-1;

ф-1;                          в-1.

Користуючись методом Хаффмана, літерам можна присвоїти коди: і - 11; н -01; ф - 101; т-001;          и - 000; в - 100. Після кодування слово «інфінітив» буде записуватися як 1101101110111001000100 та матиме довжину 22 біти. Оскільки вихідне слово займало 72 (=9x8) біти, отримаємо стиснення більш ніж утричі.

Зверніть увагу, що в методі Хаффмана код жодного символу не є початком коду будь-якого іншого символу. Це дозволяє отримувачеві однозначно відно­вити код стиснутого файла, навіть якщо він не знає довжини коду кожного пере­даного символу. Під час прийому коду отримувач спершу відділить перший символ, у нашому прикладі: 11-01101110111001000100. Потім буде відділений другий символ: 11 -01 -101110111001000100 і так до повного розшифрування коду: 11-01-101-11-01-11-001-000-100.

Недоліком методу Хаффмана є лише те, що до закодованого файла слід додавати таблицю кодування символів (у кожного файла вона буде своя). Однак, якщо файл великий, наявність таблиці несуттєво вплине на підсумковий розмір архівного файла.

 

Кодування Лемпеля-Зіва

Згідно з методом Лемпеля-Зіва у потоці даних відшукують послідовності символів, що повторюються. До стиснутого файлу записують не самі послідов­ності, а посилання на них у вигляді параметрів (зміщення, довжина).

Пояснимо це на прикладі вислову «давним-давно», яка кодується як «давним-(-7,4)о». Тобто замість повторюваної послідовності «давн», що скла­дається з 4 символів та починається з 8-ої позиції, виконується така підстановка. Відраховується зміщення від поточної позиції на 7 знаків вліво (зміщення вліво позначається знаком мінус) та використовується фрагмент з 4 знаків.

Представимо за допомогою метода Лемпеля-Зіва ще такий вірш:

-   Грицю, Грицю, до роботи!
В Гриця порвані чоботи...

-   Грицю, Грицю, до телят!
В Гриця ніженьки болять...

Після кодування одержимо «-_Грицю,_(-7,6)_до_роботи!/В(-20,5)я_порвані _ч(-24,5).../(- 1,19)телят (-50,10)ніженьки_бо(-24,3)ь...».Знак абзацу тут позначено косою рискою «/».

Метод Лемпеля-Зіва найчастіше застосовується для стиснення текстів та файлів, які взагалі не стискаються методом RLE.

 

Завдання архівації

Досі йшлося про одне призначення архівації даних - економніше вико­ристання носіїв інформації. Однак за допомогою архівації можна виконувати цілий комплекс завдань:

• Зменшення обсягу файлів. Це завдання виконується за допомогою методів стискання, що були розглянуті вище. Зменшення файлів актуальне не лише для економії вільного місця на дисках, а й для швидшого передавання файлів по мережі. Якщо дисковий простір можна «нарощувати» шляхом придбання сучасніших дисків більшої ємності, то швидкість передавання ще довго стримуватиме збільшення розміру файлів, що передаються.
• Резервне копіювання. У процесі експлуатації комп'ютера не виключені си­туації, що загрожують невідновною втратою інформації (несправність при­строю накопичувача або дефекти на поверхні жорсткого диска, неправильні операції з файлами або випадкове знищення файлів, чи руйнування інфор­мації комп'ютерним вірусом). Для збереження важливої інформації засто­совується резервне копіювання на зовнішні носії (магнітооптичні диски, дис­ки CD-R і CD-RW, вінчестери). Резервне копіювання виконується за допомо­гою спеціальних утиліт, що забезпечують створення компактних архівів. Одна з таких утиліт, Microsoft Backup, входить до комплекту Windows.
• Архівація при шифруванні даних. Ця операція виконується з метою змен­шення імовірності злому криптосистеми. Доведено, що чим менша кореляція (взаємозв'язок) між блоками вхідної інформації, тим нижча імовірність злому. Процедура архівації, знищуючи надмірну інформацію, ліквідує кореляції у вхідному потоці.

 

Архівні формати й архіватори

Для роботи з архівами існують програми, що називаються архіваторами. Ці програми, окрім створення архівів, здійснюють стиснення даних.

Перші програми-архіватори з'явилися в середині 80-х років. Вони були зо­рієнтовані, насамперед, на роботу в MS-DOS і підтримували популярні архівні формати: ARC, ZIP, LZH, ARJ, ARC, ICE тощо. Тогочасні архіватори дозволяли створювати архівні файли та розкривати архіви, переглядати архіви, сортувати файли в архіві, виводити вміст архіву на екран, знищувати файли в архіві. Існувала також група архіваторів (PKLITE, LZE,..), які запаковували дані у саморозпаковувані архіви - файли з розширеннями exe, com. Для стиснення всього диска були розроблені резидентні архіватори (STACKER, SSTOR,..). Вони дозволяли підвищити ефективність використання дискового простору шляхом створення дуже великих архівних файлів - «стиснутих» дисків. Архівація і розархівація даних на такому диску виконується автоматично під час будь-яких операцій читання-запису.

В MS-DOS програми-архіватори викликаються командним рядком з числен­ними параметрами. Параметри забезпечують великі можливості, хоча й ство­рюють труднощі пересічному користувачеві у роботі з архіваторами.

Значно зручнішою стала робота з архівами з появою ОС Windows 9.x і Windows-версій архиваторів. З попередніх архівних форматів серед користувачів Windows найпопулярнішими є ZIP, ARJ і менш пощирений LZH. Популярним є також формат CAB, розроблений фірмою Microsoft, що ввійшов до складу Windows 9.x. Багато архіваторів, орієнтованих на формати ZIP і ARJ, дозволяють розпаковувати і САВ-архіви.

Слід окремо розглянути формат RAR і відповідні архіватори, створені про­грамістом з Челябінська Євгеном Рошалем. Windows-версія цього архіватора (WinRAR) дуже зручна для роботи (її інтерфейс нагадує вікно Мой компьютер), забезпечує високий ступінь стиснення, дозволяє створювати багатотомні (на кількох дискетах) та саморозпаковувальні архіви (exe-файли).

На жаль, серед стандартних програм Windows немає архіватора (є лише утиліта резервного копіювання Microsoft Backup). Ці архіватори інтегруються до системи Windows 9.x: дозволяють пакувати і розпаковувати файли за допомогою операцій Drag and Drop, подавати архіви у вигляді звичайних папок, викликати для архівних файлів контекстні меню.

 

Терміни, пов'язані з архівацією

У програмах архіваторів застосовуються спеціальні терміни та вислови:

• Add file - додавання файла до архіву. Якщо архів не існує, то він ство­рюється.
• Extract files - вилучення файлів з архіву.
• Fresh fіles - додавання до архіву нових версій файлів, які вже є там.
• Move files - переміщення файлів до архіву.
• Multiple volumes - багатотомні архіви, які складаються з кількох файлів (томів). Вони звичайно створюються для запису архівних файлів на окремі дискети.
• Ratio - ступінь стиснення файла, який може визначатися як відношення вихідного обсягу файла до стиснутого або навпаки (залежно від програми архіватора).
• Self-extract (SFX) archive - саморозпаковувальний архів, що є архівним фай­лом з розширенням ехе або com. Після запуску цього файла відбувається автоматичне вилучення вмісту з архіву. Термін SFX означає буквально «самовилучення».
• Solid archive - неперервний архів, який звичайно створюється з багатьох схожих файлів. Вміст цих файлів розглядається як один суцільний потік даних. Завдяки можливим повторенням досягають більшого стискання, ніж при роздільній упаковці файлів. Неперервні архіви можуть займати на третину менше місця, ніж звичайні архіви. Недоліком неперервних архівів є, насамперед, більша уразливість архіву (при ушкодженні архіву не відкри­ється жоден файл). Крім того, такі архіви розпаковуються дуже повільно.
• Update files - додавання до архіву нових файлів.