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

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

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

· Групове кодування RLE (Run Length Encoding) – один з найдавніший та простих методів стиснення, який використовується в основному для архівації графіки.

· Кодування Хаффмана ( від англ. Huffman) – заснований на тому факті, що деякі символи в тексті можуть зустрічатись частіше середньої частоти повторення, а інші – рідше.

· Кодування Лемпеля-Зива (від англ. Lempel, Ziv) – використовує факт неодноразового повторення фрагментів тексту, тобто послідовностей байт.

Практично всі популярні програми-архіватори без втрат (ARJ, RAR, ZIP та ін) використовують обидва останніх методів стиснення – Лемпеля-Зива та Хаффмана (так званий алгоритм LZH – за початковими літерами прізвищ авторів).

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

Яка може бути описана байтами:

255 255 255 255 128 128 0 0 0 0 0

буде представлена як

255 4 128 2 0 5

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

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

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

Хаффман запропонував дуже простий графічний спосіб визначення того, якому символу який код необхідно надати.

Наприклад, кодування слова «інфінітів». Частота з’явлення літер в цьому слові наступна:

І – 4;

Н – 2;

Ф – 1;

Т – 1;

В – 1.

Користуючись методом Хаффмана, літерам можна надати коди: і – 0, н – 100, ф – 101, т – 110, в – 111. Після кодування слово «інфінітив» буде записуватись як 0100101010001100111 та мати довжину 19 бітів. Так як вихідне слово займало 72 (=9х8) біта, отримано стиснення більш, ніж в тричі.

Треба звернути увагу на те, що в методі Хаффмана код ніякого символу не є початком коду якого-небудь іншого символу. Це дозволяє одержувачу однозначно відновити код стиснутого файлу. Навіть якщо він не знає довжини коду кожного переданого символу.

Кодування Лемпеля-Зива (від англ. Lempel, Ziv) – використовує факт неоднократного повторення фрагментів тексту, тобто послідовностей байт.

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

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

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

Задачі архівації:

· Зменшення обсягу файлів. Актуально не тільки для економії дискового простору, але й для більш швидкої передачі файлів по мережах.

· Резервне копіювання. В процесі експлуатації комп’ютера не виключені ситуації, які загрожують втратою інформації (пошкодження пристрою накопичувача або дефекти на поверхні жорсткого диску, неправильні операції з файлами або випадкове видалення файлів, руйнування інформації комп’ютера вірусом). Для збереження інформації застосовується резервне копіювання на зовнішні носії (CD-диски, flesh-пам’ять, вінчестери) за допомогою спеціальних утіліт, які запеспечують створення компактних архівів (Micorsoft Backup).

· Архівація при шифруванні даних. Виконується з метою зменшення вірогідності руйнації (взлому) криптосистеми. Використовується факт того, що чим менше кореляція (взаємозв’язок) між блоками вхідної інформації, тим імовірність взлому нижча. Процедура архівації, яка усуває надлишкову інформацію, ліквідує кореляції у вхідному потоці.