БІЛОРУСЬКИЙДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАТИКИ І РАДІОЕЛЕКТРОНІКИ
Кафедра РЕЗ
Реферат натему:
В«Словниковіметоди кодування. Метод Зіва-Лемпела. Диференціальне кодування В»
МІНСЬК, 2009
Словникові методикодування. Метод Зіва-Лемпела
Практично всі словниковіметоди кодування пpінадлежат родині алгоритмів з роботи двох ізраїльськихвчених - Зіва і Лемпела, опублікованій в 1977 році. Сутність їх полягає вте, що фрази в стисливому тексті замінюються покажчиком на те місце, де вони вцьому тексті вже pанее з'являлися .
Це сімействоалгоритмів називається методом Зіва-Лемпела і позначається як LZ-стиснення .Цей метод Швидка пpіспосаблівается до стpуктуpе тексту і може кодуватикороткі функціональні слова, так як вони дуже часто в ньому з'являються. Новіслова і фрази можуть також формуватися з частин раніше зустрінутих слів.
Декодування стисненого текстуздійснюється безпосередньо - відбувається проста заміна покажчика готової фразою зсловника, на яку той вказує. На практиці LZ-метод домагається гарногостиснення, його важливою властивістю є дуже швидка робота декодера. (Коли миговоримо про текст, то припускаємо, що кодуванню піддається деякийвектор даних з кінцевим дискретним алфавітом, і це не обов'язково текст вбуквальному сенсі цього слова.)
Більшістьсловникових методів кодування носять ім'я авторів ідеї методу Зеева і Лемпела, ічасто вважають, що всі вони використовують один і той же алгоритм кодування. НаНасправді різні представники цього сімейства алгоритмів дуже сильнорозрізняються в деталях своєї роботи.
Всісловникові методи кодування можна розбити на дві групи.
Методи,належать до першої групи, знаходячи в кодованого послідовностіланцюжки символів, які раніше вже зустрічалися, замість того, щоб повторюватиці ланцюжки, замінюють їх покажчиками на попередні повторення.
Словник вцій групі алгоритмів в неявному вигляді міститься в оброблюваних даних,зберігаються лише покажчики на зустрічаються ланцюжка повторюваних символів.
Всі методицієї групи базуються на алгоритмі, розробленому і опублікованому, як ужезазначалося, порівняно недавно - в 1977 році Абрахамом Лемпела і ЯкобомЗівом, - LZ77. Найбільш досконалимпредставником цієї групи, що включив в себе всі досягнення, отримані вданому напрямку, є алгоритм LZSS, опублікований в 1982 році Сторер і Шиманські.
Процедуракодування відповідно до алгоритмами цієї групи ілюструється рис. 1.
Рис. 1
Алгоритми другугрупи на додаток до вихідного словника джерела створюють словник фраз,представляють собою повторювані комбінації символів вихідного словника,зустрічаються у вхідних даних.
При цьомурозмір словника джерела зростає, і для його кодування потрібно більшучисло біт, але значна частина цього словника буде являти собою вже неокремі букви, а буквосполучення або цілі слова.
Коли кодервиявляє фразу, яка раніше вже зустрічалася, він замінює її індексомсловника, що містить цю фразу. При цьому довжина коду індексу виходить меншеабо набагато менше довжини коду фрази.
Всі методицієї групи базуються на алгоритмі, розробленому і опублікованому Лемпеля іЗівом в 1978 році, - LZ78.Найбільш досконалим на даний момент представником цієї групи словниковихметодів є алгоритм 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
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азмеpа,пpедшествующіе позиції коду. Максимальна довжина замінних покажчиками підрядківвизначається параметром F (зазвичай це від 10 до 20). Ці обмеженнядозволяють LZ77 використовувати "ковзне вікно" з N символів.З них перші NF були вже закодовані, а останні F складають попереджуючий буфер.
Прикодуванні с...
