1.2.5. Алгоритми стиснення без втрат

1.2.5.1. Алгоритм rle

Даний алгоритм э надзвичайно простим в реалізації. Групове кодування — від англійського Run| Length| Encoding| (RLE|) [4]— один з найстаріших і найпростіших алгоритмів стиснення графіки. Зображення в нім витягується в ланцюжок байт по рядках растру. Сам процес стиснення в RLE| відбувається|походить| за рахунок того, що в початковому|вихідному| зображенні зустрічаються ланцюжки однакових байт. Заміна їх на пари <лічильник повторень, значення> зменшує надмірність даних.

Кодування довжин ділянок (або повторень) може бути достатньо ефективним при стисненні двійкових даних, наприклад, чорно-білих зображень що містять безліч прямих ліній і однорідних ділянок, схем і т.п.

Ідея стиснення даних на основі кодування довжин повторень полягає в тому, що замість кодування власне дані піддають кодуванню числа, що відповідають довжинам ділянок, на яких дані зберігають незмінне значення.

Припустимо, що потрібно закодувати двійкове зображення розміром 8 х 8 елементів.

Проскануємо це зображення по рядках (двом об’єктам на зображенні відповідатимуть 0 і 1), в результаті отримаємо двійковий вектор даних, наприклад:

довжиною 64 біта (швидкість початкового коду складає 1 біт на елемент зображення).

Виділимо у векторі X ділянки, на яких дані зберігають незмінне значення, і визначимо їх довжини. Результуюча послідовність довжин ділянок - позитивних цілих чисел, що відповідають початковому вектору даних , - матиме вид .

Таблиця 1.1. Кодові слова RLE

Довжина ділянки	Кодове слово
4	0
1	10
7	110
3	111

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

Для того, щоб вказати, що кодована послідовність починається з нуля, додамо на початок кодового слова префіксний символ 0. В результаті отримаємо кодове слово довжиною в 34 біта, тобто результуюча швидкість коду складе 34/64, або трохи більше 0,5 біт на елемент зображення. При стисненні зображень більшого розміру і повторюванні елементів, що містять множину, ефективність стиснення може виявитися істотно вищою.

Нижче наведений інший приклад використання кодування довжин повторень, коли в цифрових даних зустрічаються ділянки з великою кількістю нульових значень. Кожного разу, коли в потоці даних зустрічається “нуль”, він кодується двома числами. Перше - 0, такий, що є прапором початку кодування довжини потоку нулів, і друге – кількість нулів в черговій групі (Рис. 1.5). Якщо середнє число нулів в групі більше двох, матимемо стиснення. З іншого боку, велике число окремих нулів може привести навіть до збільшення розміру кодованого файлу.

Рис. 1.5 . Графічне зображення алгоритму кодування по довжині повторів нулів

1.2.5.2. Метод lzw

Метод LZW (Лємпеля-Зіва-Уелча) був розроблений у 1984 році Тері Уелчем на основі метода LZ (Лємпеля-Зіва) [4].

LZW являється словниковим методом компресії, у якому використовується словник послідовностей символів, які зустрічалися раніше в вихідному тексті. На виході компресора ці послідовності представляються у вигляді міток. Мітка LZW складається з вказівника на місце послідовності в словнику.

Процес стиснення виглядає досить просто. Считуються послідовно символи вхідного потоку і перевіряється, чи є в створеній таблиці рядків такий рядок. Якщо рядок є, то ми считуємо наступний|такий| символ, а якщо рядка немає, то заносимо в потік код для попереднього знайденого рядка, заносимо рядок в таблицю і починаємо|розпочинаємо| пошук знову.

Хай|нехай| ми стискаємо послідовність 45, 55, 55, 151, 55, 55, 55. Тоді, згідно викладеному вище алгоритму, ми помістимо у вихідний потік спочатку код очищення|очистки| <256>, потім додамо|добавлятимемо| до спочатку порожнього|пустого| рядка “45” і перевіримо, чи є рядок “45” в таблиці. Оскільки ми при ініціалізації занесли в таблицю всі рядки з|із| одного символу, то рядок “45” є в таблиці. Далі ми читаємо наступний|такий| символ 55 з|із| вхідного потоку і перевіряємо, чи є рядок “45, 55” в таблиці. Такого рядка в таблиці поки немає. Ми заносимо в таблицю рядок “45, 55” (з|із| першим вільним кодом 258) і записуємо|занотовуємо| в потік код <45>. Можна коротко представити|уявляти| архівацію так:

“45” — є в таблиці;

“45, 55” — ні. Додаємо|добавляємо| в таблицю <258>“45, 55”. У потік: <45>;

“55, 55” — ні. У таблицю: <259>“55, 55”. У потік: <55>;

“55, 151” — ні. У таблицю: <260>“55, 151”. У потік: <55>;

“151, 55” — ні. У таблицю: <261>“151, 55”. У потік: <151>;

“55, 55” — є в таблиці;

“55, 55, 55” — ні. У таблицю: “55, 55, 55” <262>. У потік: <259>;

Послідовність код для даного прикладу|зразка|, що потрапляють|попадають| у вихідний потік: <256>, <45>, <55>, <55>, <151>, <259>.

Особливість LZW| полягає в тому, що для декомпресії не треба зберігати таблицю рядків у файл для розпаковування. Алгоритм побудований|спорудити| таким чином, що можливо відновити таблицю рядків, користуючись тільки|лише| потоком кодів. LZW-декодер, обробляючи вхідний потік закодованих даних, відновлює з нього початкові дані. Так само, як і алгоритм стиснення, декодер додає нові рядки в словник кожного разу, коли знаходить у вхідному потоці новий код. Все, що йому залишається зробити, – це перетворити вхідний код у вихідний рядок символів і віддати її на вихід кодера.

Відомо, що для кожної коди треба додавати|добавляти| в таблицю рядок, що складається з вже присутнього там рядка і символу, з якого починається наступний|такий| рядок в потоці.

Принцип роботи алгоритму проілюстровано на рис. 1.6 [1].

Рис. 1.16. Процедура кодування відповідно до алгоритму LZW