Рожко М.Ю.

Херсонський Національний Технічний Університет, Україна

Дослідження методів і алгоритмів стиснення без втрат

 

Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в кілька разів більше ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більше ніж ступінь надлишковості текстових даних.

Коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надмірність відіграє негативну роль, оскільки вона призводить до зростання вартості зберігання та передачі інформації. Особливо актуальною ця проблема стає в разі обробки величезних обсягів інформації при передачі цієї інформації, для чого може не вистачити ширини каналу зв'язку. Звичайно в даному випадку слід розглядати алгоритми стиснення без втрати даних.

Коефіцієнт стиснення [1] - основна характеристика алгоритму стиснення. Вона визначається як відношення обсягу вихідних не зтиснутих даних до обсягу стислих тобто:

 

(1)

де k - коефіцієнт стиснення,

So - обсяг вихідних даних,

Sc - обсяг стислих даних.

Таким чином, чим вищий коефіцієнт стиснення, тим алгоритм ефективніший.

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

Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів. Однак, в основі цих методів лежать три теоретичних алгоритми [2]:

Алгоритм RLE - простий алгоритм стиснення даних, який оперує серіями даних, тобто послідовностями, в яких один і той же символ зустрічається кілька разів поспіль. При кодуванні рядок однакових символів, що становлять серію, замінюється рядком, який містить сам повторюваний символ і кількість його повторів [3].

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

Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз [4].

Алгоритм Хаффмана - адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений в 1952 році аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні ним курсової роботи. В даний час використовується в багатьох програмах стиснення даних [5].

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

До таких алгоритмів можна віднести алгоритми сімейства LZ, які в 1.3-1.7 рази поступаються методам статистичного моделювання по якості стиснення, проте мають дуже високу швидкістю кодування при порівняно невеликому обсязі необхідної пам'яті, що важливе наприклад при передачі стиснутих даних, із-за меншого навантаження на систему кодування.

Величезна перевага алгоритмів сімейства LZ- надзвичайно висока швидкість декодування. Це дозволяє застосовувати їх в тих випадках, коли декодування здійснюється набагато частіше кодування або швидкість декодування дуже важлива [6].

Велика частина сучасних промислових систем стиснення даних побудовано на основі різних варіантів алгоритму LZ77, які протягом багатьох років заслужено вважалися найкращими за співвідношенням швидкості і якості стиснення. Тому їх можна по праву вважати одними з найважливіших алгоритмів стиснення без в трат в даній категорії швидкодії кодування і декодування, що потрібно в великій кількості різноманітних систем.

 

Перелік посилань

1.     https://ru.wikipedia.org/wiki/Сжатие_данных

2.     http://www.victoria.lviv.ua/html/informatika/lecture9.htm

3.     https://uk.wikipedia.org/wiki/RLE

4.     http://edufuture.biz/index.php?title=Архівування_інформації._Повні_уроки

5.     https://uk.wikipedia.org/wiki/Код_Хаффмана

6.     http://mf.grsu.by/UchProc/livak/po/comprsite/theory_classification_02.html