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

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

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

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

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

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

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

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

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

ü Групове кодування 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. Розмір стис­нутого файла в такому разі може перевищувати розмір вихідного файла.