Білоруський державний університет інформатики і радіоелектроніки
Кафедра РЕЗ
Реферат на тему:
«Словникові методи кодування. Метод Зеева-Лемпела. Диференціальне кодування »
МІНСЬК, 2009
Словникові методи кодування. Метод Зеева-Лемпела
Практично всі словникові методи кодування пpінадлежат сім'ї алгоритмів з роботи двох ізраїльських вчених - Зіва і Лемпела, опублікованій в 1977 році. Сутність їх полягає в тому, що фрази в стисливому тексті замінюються покажчиком на те місце, де вони в цьому тексті вже pанее з'являлися.
Це сімейство алгоритмів називається методом Зеева-Лемпела і позначається як LZ-стиснення. Цей метод бистpо пpіспосаблівается до стpуктуpе тексту і може кодувати короткі функціональні слова, так як вони дуже часто в ньому з'являються. Нові слова і фрази можуть також формуватися з частин раніше зустрінутих слів.
Декодування стислого тексту здійснюється безпосередньо - відбувається проста заміна покажчика готової фразою з словника, на яку той вказує. На практиці LZ-метод домагається гарного стиснення, його важливою властивістю є дуже швидка робота декодера. (Коли ми говоримо про текст, то припускаємо, що кодуванню піддається деякий вектор даних з кінцевим дискретним алфавітом, і це не обов'язково текст в буквальному сенсі цього слова.)
Більшість словникових методів кодування носять ім'я авторів ідеї методу Зіва і Лемпела, і часто вважають, що всі вони використовують один і той же алгоритм кодування. Насправді різні представники цього сімейства алгоритмів дуже сильно розрізняються в деталях своєї роботи.
Всі словникові методи кодування можна розбити на дві групи.
Методи, що належать до першої групи, знаходячи в кодируемой послідовності ланцюжка символів, які раніше вже зустрічалися, замість того, щоб повторювати ці ланцюжки, замінюють їх покажчиками на попередні повторення.
Словник в цій групі алгоритмів у неявному вигляді міститься в оброблюваних даних, зберігаються лише покажчики на зустрічаються ланцюжка символів, що повторюються.
Всі методи цієї групи базуються на алгоритмі, розробленому і опублікованому, як уже зазначалося, порівняно недавно - в 1977 році Абрахамом Лемпела і Якобом Зівом, - LZ 77. Найбільш досконалим представником цієї групи, які ввімкнули у себе всі досягнення, отримані в даному напрямку, є алгоритм LZSS, опублікований в 1982 році Сторер і Шиманьскі.
Процедура кодування відповідно до алгоритмів цієї групи ілюструється рис. 1.
Рис. 1
Алгоритми другої групи на додаток до вихідного словника джерела створюють словник фраз, що представляють собою повторювані комбінації символів вихідного словника, що зустрічаються у вхідних даних.
При цьому розмір словника джерела зростає, і для його кодування потрібно більшу кількість біт, але значна частина цього словника буде представляти собою вже не окремі букви, а буквосполучення або цілі слова.
Коли кодер виявляє фразу, яка раніше вже зустрічалася, він замінює її індексом словника, що містить цю фразу. При цьому довжина коду індексу виходить менше або набагато менше довжини коду фрази.
Всі методи цієї групи базуються на алгоритмі, розробленому і опублікованому Лемпела і Зівом в 1978 році, - LZ 78. Найбільш досконалим на даний момент представником цієї групи словникових методів є алгоритм LZW, розроблений в 1984 році Террі Велчем.
Ідею цієї групи алгоритмів можна також пояснити за допомогою рис. 2.
Рис. 2
Алгоритми другої групи дещо простіше в поясненні їх роботи, тому почнемо розгляд принципу дії LZ-кодерів з алгоритму LZW.
Розглянемо в найзагальнішому вигляді роботу LZW-кодера і декодера.
Процедура кодування
Процес стиснення виглядає досить просто. Ми послідовно зчитуємо символи вхідного потоку (рядок) і перевіряємо, чи є у вже створеної нами таблиці такий рядок.
Якщо рядок є, то зчитуємо наступний символ, а якщо такого рядка немає, - заносимо у вихідний потік код для попередньої знайденої рядки, заносимо її в таблицю і починаємо пошук знову.
Нехай на вхід кодера надходить послідовність символів виду / WED / WE / WEE / WEB, при цьому розмір алфавіту вхідних символів dim A = 255.
Схема стиснення виглядає наступним чином:
Вхідні символи Вихідний код Нові символи словника
/ W / 256 = / W
E W 257 = WE
D E 258 = ED
/ D 259 = D /
WE 256 260 = / WE
/ E 261 = E /
WEE 260 262 = / WEE
/ W 261 263 = E / W
EB 257 264 = WEB
<END> B
У результаті отримаємо вихідний код
/ WED <256> E <260> <261> <257> B.
Як при цьому змінилася довжина вихідного коду в порівнянні з вхідним?
Якщо для двійкового кодування рядка / WED / WE / WEE / WEB довжиною в 15 літер і розміром алфавіту dim A = 255 нам знадобилося б 15 • log 2 255 = 15х8 = 120 біт, то для двійкового кодування вихідний рядка кодера / WED <256> E <260> <261> <257> B довжиною в 10 нових символів з алфавітом в 264 літери - 10 • 9 = 90 біт.
Поцедури декодування
LZW-декодер, обробляючи вхідний потік закодованих даних, відновлює з нього вихідні дані. Так само, як і алгоритм стиснення, декодер додає нові рядки в словник щоразу, коли знаходить у вхідному потоці новий код. Все, що йому залишається зробити, - це перетворити вхідний код у вихідну рядок символів і віддати її на вихід кодера.
Схема роботи LZW-декодера виглядає наступним чином:
рядок на вході кодера - / WED <256> E <260> <261> <257> B.
Вхідні символи Вихідна рядок Нові символи словника
/ /
W W 256 = / W
E E 257 = WE
D D 258 = ED
256 / W 259 = D /
E E 260 = / WE
260 / WE 261 = E /
261 E / 262 = / WEE
257 WE 263 = E / W
B B 264 = WEB
Самим чудовим якістю цього способу стиснення є те, що весь словник нових символів передається декодеру без власне передачі. В кінці процесу декодування декодер має точно такий же словник нових символів, який у процесі кодування був накопичений кодером, при цьому його створення було частиною процесу декодування.
Робота кодера / декодера сімейства LZ77 - першій опублікованій версії LZ-методу - виглядає дещо інакше.
В алгоритмі LZ77 покажчики позначають фрази у вікні постійного діаметра, пpедшествующій позиції коду. Максимальна довжина замінних покажчиками підрядків визначається параметром F (зазвичай це від 10 до 20). Ці обмеження дозволяють LZ77 використовувати "ковзне вікно" з N символів. З них перші NF були вже закодовані, а останні F складають попереджуючий буфер.
При кодуванні символу в перших NF символах вікна шукають найдовшу, збігається з цим буфером рядок. Вона може частково перекривати буфер, але не може бути самим буфером.
Знайдене найбільшу відповідність потім кодується тріадою [i, j, a] де i є його зсув від початку буфера, j - довжина відповідності, a - перший символ, що не відповідає підрядку вікна.
Потім вікно зсувається вправо на j +1 символ і готове до нового кроку алгоритму.
Прив'язка певного символу до кожного вказівником гарантує, що кодування буде виконуватися навіть в тому випадку, якщо для першого символу упpеждающего буфера не буде знайдено відповідність.
Обсяг пам'яті, необхідний кодеру і декодеру, обмежується розміром вікна. Кількість біт, необхідне для подання зсуву (i) у тріаді, становить [log (NF)]. Кількість символів (j), замінних тріадою, може бути закодовано [logF] бітами.
Декодування здійснюється дуже просто і швидко. При цьому підтримується той же порядок роботи з вікном, що і при кодуванні, але на відміну від пошуку однакових рядків він, навпаки, копіює їх з вікна відповідно до чергової тріадою.
Диференціальне кодування
Робота диференціального кодера заснована на тому факті, що для багатьох типів даних різниця між сусідніми відліками відносно невелика, навіть якщо самі дані мають великі значення. Наприклад, не можна очікувати великої різниці між сусідніми пікселями цифрового зображення.
Наступний простий приклад показує, яку перевагу може дати диференційне кодування (кодування різниці між сусідніми відліками) у порівнянні з простим кодуванням без пам'яті (кодуванням відліків незалежно один від одного).
Просканіруем 8-бітове (256-рівневе) цифрове зображення, при цьому десять послідовних пікселів мають рівні:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Якщо закодувати ці рівні піксель за пикселом яких-небудь кодом без пам'яті, що використовує 8 біт на піксел зображення, отримаємо кодове слово, що містить 80 біт.
Припустимо тепер, що перш ніж піддавати відліки зображення кодуванню, ми обчислимо різниці між сусідніми пікселями. Ця процедура дасть нам послідовність такого вигляду:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
ß ß ß ß ß ß ß ß ß ß
144, 3, 3, - 4, - 5, 1, - 4, 5, 2, -3.
Вихідна послідовність може бути легко відновлена з різницевої простим підсумовуванням (дискретним інтегруванням):
144, 144 +3, 147 +3, 150-4, 146-5, 141 +1, 142-4, 138 +5, 143 +2, 145-3
ß ß ß ß ß ß ß ß ß ß
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Для кодування першого числа з отриманої послідовності різниць відліків, як і раніше, знадобиться 8 біт, всі інші числа можна закодувати 4-бітовими словами (один знаковий біт і 3 біти на кодування модуля числа).
Таким чином, в результаті кодування отримаємо кодове слово довжиною 8 + 9 * 4 = 44 біта або майже вдвічі коротший, ніж при індивідуальному кодуванні відліків.
Метод диференціального кодування дуже широко використовується в тих випадках, коли природа даних така, що їх сусідні значення незначно відрізняються один від одного, при тому, що самі значення можуть бути як завгодно великими.
Це відноситься до звукових сигналів, особливо до мови, зображень, сусідні пікселі яких мають практично однакові яскравості і колір і т.п. У той же час цей метод абсолютно не підходить для кодування текстів, креслень або будь-яких цифрових даних з незалежними сусідніми значеннями.
ЛІТЕРАТУРА
Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В.І. Нефедов, В.І. Халкин, Є.В. Федоров та ін - М.: Вища школа, 2001 р. - 383с.
Цапенко М.П. Вимірювальні інформаційні системи. - М.: Енергоатом издат, 2005. - 440С.
Зюко А.Г., Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р. -368 с.
Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р. - 1104 с.