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

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

Нагадаємо, що при кодуванні текстової інформації кожному символу відво­диться 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.

Дата добавления: 2014-01-14