Метод Зеева-Лемпела

Практично всі словникові методи кодування пpінадлежат сім'ї алгоритмів з роботи двох ізраїльських вчених - Зіва і Лемпела, опублікованій в 1977 році.Сутністьїх полягає в тому, що фрази в стисливому тексті замінюються покажчиком на те місце, де вони в цьому тексті вже раніше з'являлися.
Це сімейство алгоритмів називається методом Зеева-Лемпела і позначається як LZ-стиснення. Цей метод швидко приспособлюється до стpуктуpе тексту і може кодувати короткі функціональні слова, так як вони дуже часто в ньому з'являються. Нові слова і фрази можуть також формуватися з частин раніше зустрінутих слів.
Декодування стислого тексту безпосередньо - відбувається проста заміна покажчика готової фразою з словника, на яку той вказує. На практиці LZ-метод домагається гарного стиснення, його важливою властивістю є дуже швидка робота декодера. (Коли ми говоримо про текст, то припускаємо, що кодуванню піддається деякий вектор даних з кінцевим дискретним алфавітом, і це не обов'язково текст в буквальному сенсі цього слова.)
Більшість словникових методів кодування носять ім'я авторів ідеї методу Зіва і Лемпела, і часто вважають, що всі вони використовують один і той же алгоритм кодування. Насправді різні представники цього сімейства алгоритмів дуже сильно розрізняються в деталях своєї роботи.
Всі словникові методи кодування можна розбити на дві групи.
Методи, що належать до першої групи, знаходячи в кодуючій послідовності ланцюжка символів, які раніше вже зустрічалися, замість того, щоб повторювати ці ланцюжки, замінюють їх покажчиками на попередні повторення.
Словник в цій групі алгоритмів у неявному вигляді міститься в оброблюваних даних, зберігаються лише покажчики та зустрічаються ланцюжки символів, що повторюються.
Всі методи цієї групи базуються на алгоритмі, розробленому і опублікованому, як уже зазначалося, в 1977 році Абрахамом Лемпела і Якобом Зівом, - LZ77. Найбільш досконалим представником цієї групи, які ввімкнули у себе всі досягнення, отримані в даному напрямку, є алгоритм LZSS, опублікований в 1982 році Сторер і Шиманьскі.
Процедура кодування відповідно до алгоритмів цієї групи ілюструється рис. 2.3.6.

Рисунок 2.3.6 – Вхідні – Вихідні данні

Алгоритми другої групи на додаток до вихідного словника джерела створюють словник фраз, що представляють собою повторювані комбінації символів вихідного словника, що зустрічаються у вхідних даних.
При цьому розмір словника джерела зростає, і для його кодування потрібно більшу кількість біт, але значна частина цього словника буде представляти собою вже не окремі букви, а буквосполучення або цілі слова.
Коли кодер виявляє фразу, яка раніше вже зустрічалася, він замінює її індексом словника, що містить цю фразу. При цьому довжина коду індексу виходить менше або набагато менше довжини коду фрази.
Всі методи цієї групи базуються на алгоритмі, розробленому і опублікованому Лемпела і Зівом в 1978 році, - LZ78. Найбільш досконалим на даний момент представником цієї групи словникових методів є алгоритм LZW, розроблений в 1984 році Террі Велчем.
Ідею цієї групи алгоритмів можна також пояснити за допомогою рис. 2.3.7.

Рисунок 2.3.7 – Вхідні – Вихідні данні словника

Алгоритми другої групи дещо простіше в поясненні їх роботи, тому почнемо розгляд принципу дії LZ-кодерів з алгоритму LZW.
Розглянемо в найзагальнішому вигляді роботу LZW-кодера і декодера.

Дата добавления: 2015-07-11