Презентация. Алгоритм Лемпеля-Зива

Скачать презентацию




Алгоритм Лемпеля-Зива Виконав: Студент групи СН-41 Стодола В.Р.
 


Суть алгоритму Якщо в тексті зустрінеться повторення рядків символів, то повторні рядки замінюються посиланнями (покажчиками) на вихідний рядок. Посилання має формат <префікс, відстань, довжина>. Префікс в цьому випадку дорівнює 1. Поле відстань ідентифікує слово в словнику рядків. Якщо рядка в словнику немає, генерується код символ виду <префікс, символ ", де поле префікс = 0, а поле символ відповідає Вашому символу вихідного тексту. Звідси видно, що префікс служить для розділення кодів покажчика від кодів символ. Введення кодів символ, дозволяє оптимізувати словник і підняти ефективність стиснення. Головна алгоритмічна проблема тут полягати в оптимальному виборі рядків, так як це передбачає значний обсяг переборів.
 


Принцип скользящого вікна Метод кодування згідно з принципом скользящого вікна враховує вже раніше зустрівши інформацію, тобто інформацію, яка вже відома для кодувальника і декодувальник (другий і наступні входження деякого рядка символів в повідомленні замінюються посиланнями на його перше входження). Завдяки цьому принципу алгоритми LZ * іноді називаються методами стиснення з використанням скользящого вікна. Скользяще вікно можна представити у вигляді буфера (або більш складної динамічної структури даних), який організований так, щоб запам'ятовувати «сказану» раніше інформацію та надавати до неї доступ. Таким чином, сам процес стискаючого кодування згідно LZ77 нагадує написання програми, команди якої дозволяють звертатися до елементів «скользящого вікна», і замість значень стисливою послідовності вставляти посилання на ці значення в «скользящого вікні». Розмір скользящого вікна може динамічно змінюватися і складати 2, 4 або 32 кілобайт. Слід також зазначити, що розмір вікна кодувальника може бути менше або дорівнює розміру вікна декодувальник, але не навпаки.
 


Механізм кодування збігів Якщо всі елементи послідовності унікальні, то така послідовність не буде містити жодного повторюваного елементу, або, інакше кажучи, в послідовності не знайдеться хоча б двох рівних один одному або співпадаючих елементів. У стандартному алгоритмі LZ77 збіги кодуються парою:      1. Довжина збігу (match length)      2. Зміщення (offset) або дистанція (distance) Яким чином можна скопіювати 7 символів з буфера, коли зараз в буфері знаходиться тільки 1 символ? Однак наступна інтерпретація кодує пари може прояснити ситуацію: кожні 7 наступних символів збігаються (еквівалентні) з 1 символом перед ними. Це означає, що кожен символ можна однозначно визначити, перемістившись тому в буфері - навіть якщо цей символ ще не міститься в буфері на момент декодування поточної пари довжина-зміщення. Така кодується пара буде являти собою багаторазове (визначається значенням зсуву) повторення послідовності (визначається значенням довжини) символів, що являє собою більш загальну форму RLE.
 


LZ78 LZ78 не використовує "скользяще" вікно, він зберігає словник з вже переглянутих фраз. При старті алгоритму цей словник містить тільки один порожній рядок (рядок довжини нуль). Алгоритм зчитує символи повідомлення до тих пір, поки накопичувальний підрядок входить цілком в одну з фраз словника. Як тільки цей рядок перестане відповідати хоча б одній фразі словника, алгоритм генерує код, що складається з індексу рядка в словнику, яка до останнього введеного символу містила вхідний рядок, або символ, який порушив збіг. Потім до словника додається введений підрядок. Якщо словник вже заповнений, то з нього попередньо видаляють менша за всіх використовуюму в порівняннях фразу.
 


Приклади кодування Закодувати по алгоритму LZ78 рядок " КРАСНАЯ КРАСКА", використовуючи словник довжиною 16 фраз. довжина отриманого коду дорівнює 10 * (4 +8) = 120 бітам.
 


Приклади кодування Закодувати по алгоритму LZW рядок " КРАСНАЯ КРАСКА ". Розмір словника - 500 фраз. У цьому прикладі довжина отриманого коду дорівнює 12 * 9 = 108 бітам.
 

< <       > >