Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема :
АЛГОРИТМ ЛЕМПЕЛЯ-ЗИВА
Виконав:
Студент групи СН-41
Стодола В.Р.
Тернопіль, 2010
План доповіді
1.1 Винекнення
1.2 LZ77
1.2.1 Принцип скользящого вікна
1.2.2 Механізм кодування збігів
1.2.3 Недоліки LZ77
1.3 LZ78
1.3.1 Приклади кодування
Список використаних джерел
Контрольні питання до теми
1. АЛГОРИТМ ЛЕМПЕЛЯ-ЗИВА
1.1 Винекнення
У 1977 році Абрахам Лемпель і Якоб Зив запропонували алгоритм стиснення даних, названий пізніше LZ77. Цей алгоритм використовується в програмах архівування текстів compress, lha, pkzip і arj. Модифікація алгоритму LZ78 застосовується для стиснення двійкових даних. Ці модифікації алгоритму захищені патентами США. Алгоритм передбачає кодування послідовності біт шляхом розбиття її на фрази з подальшим кодуванням цих фраз.
Суть алгоритму полягає в наступному:
Якщо в тексті зустрінеться повторення рядків символів, то повторні рядки замінюються посиланнями (покажчиками) на вихідний рядок. Посилання має формат <префікс, відстань, довжина>. Префікс в цьому випадку дорівнює 1. Поле відстань ідентифікує слово в словнику рядків. Якщо рядка в словнику немає, генерується код символ виду <префікс, символ ", де поле префікс = 0, а поле символ відповідає Вашому символу вихідного тексту. Звідси видно, що префікс служить для розділення кодів покажчика від кодів символ. Введення кодів символ, дозволяє оптимізувати словник і підняти ефективність стиснення. Головна алгоритмічна проблема тут полягати в оптимальному виборі рядків, так як це передбачає значний обсяг переборів.
1.2 LZ77
Можна сказати, що алгоритми сімейства LZ * являють собою більш складне узагальнення простого і інтуїтивного способу стиснення даних, що використовується в RLE. Для розуміння даного алгоритму необхідно розібратися з двома його складовими: принципом скользящого вікна і механізмом кодування збігів.
1.2.1 Принцип скользящого вікна
Метод кодування згідно з принципом скользящого вікна враховує вже раніше зустрівши інформацію, тобто інформацію, яка вже відома для кодувальника і декодувальника (другий і наступні входження деякого рядка символів в повідомленні замінюються посиланнями на його перше входження).
Завдяки цьому принципу алгоритми LZ * іноді називаються методами стиснення з використанням скользящого вікна. Скользяще вікно можна представити у вигляді буфера (або більш складної динамічної структури даних), який організований так, щоб запам'ятовувати «сказану» раніше інформацію та надавати до неї доступ. Таким чином, сам процес стискаючого кодування згідно LZ77 нагадує написання програми, команди якої дозволяють звертатися до елементів «скользящого вікна», і замість значень стисливою послідовності вставляти посилання на ці значення в «скользящі вікні». Розмір скользящого вікна може динамічно змінюватися і складати 2, 4 або 32 кілобайт. Слід також зазначити, що розмір вікна кодувальника може бути менше або дорівнює розміру вікна декодувальника, але не навпаки.
Наведене вище порівняння процесу кодування з «програмуванням» може наштовхнути на передчасний висновок про те, що алгоритм LZ77 відноситься до методів контекстного моделювання. Тому слід зазначити, що алгоритм LZ77 прийнято класифікувати як метод словникового стиснення даних, коли замість поняття «скользящого вікна» використовується термін «динамічного словника».
1.2.2 Механізм кодування збігів
Перед тим, як перейти до розгляду механізму кодування, уточнимо поняття збігу (від англ. Match). Розглянемо послідовність з N елементів. Якщо всі елементи послідовності унікальні, то така послідовність не буде містити жодного повторюваного елементу, або, інакше кажучи, в послідовності не знайдеться хоча б двох рівних один одному або співпадаючих елементів.
У стандартному алгоритмі LZ77 збіги кодуються парою:
* Довжина збігу (match length)
* Зміщення (offset) або дистанція (distance)
В продовження вже наведеної аналогії з програмуванням відзначимо, що в більшості статей, присвячених алгоритму LZ77, які кодуються пара трактується саме як команда копіювання символів з скользящого вікна з певної позиції, або дослівно як: «Назад в буфері символів на значення зміщення і скопіювати значення довжини символів , починаючи з поточної позиції ».
Хоча для прихильників імперативного програмування така інтерпретація може здатися інтуїтивно зрозумілою, вона, на жаль, мало говорить про сутність алгоритму LZ77 як методу стиснення. Особливість даного алгоритму стиснення полягає в тому, що використання кодованої пари довжина-зміщення є не тільки прийнятним, але й ефективним у тих випадках, коли значення довжини перевищує значення зміщення.
Приклад з командою копіювання не зовсім очевидний: «Назад на 1 символ тому в буфері і скопіювати 7 символів, починаючи з поточної позиції». Яким чином можна скопіювати 7 символів з буфера, коли зараз в буфері знаходиться тільки 1 символ? Однак наступна інтерпретація кодує пари може прояснити ситуацію: кожні 7 наступних символів збігаються (еквівалентні) з 1 символом перед ними.
Це означає, що кожен символ можна однозначно визначити, перемістившись тому в буфері - навіть якщо цей символ ще не міститься в буфері на момент декодування поточної пари довжина-зміщення. Така кодується пара буде являти собою багаторазове (визначається значенням зсуву) повторення послідовності (визначається значенням довжини) символів, що являє собою більш загальну форму RLE.
1.2.3 Недоліки LZ77:
1.3 LZ78
У 1978 р. авторами LZ77 був розроблений алгоритм LZ78, позбавлений названих недоліків.
LZ78 не використовує "скользяще" вікно, він зберігає словник з вже переглянутих фраз. При старті алгоритму цей словник містить тільки один порожній рядок (рядок довжини нуль). Алгоритм зчитує символи повідомлення до тих пір, поки накопичувальний підрядок входить цілком в одну з фраз словника. Як тільки цей рядок перестане відповідати хоча б одній фразі словника, алгоритм генерує код, що складається з індексу рядка в словнику, яка до останнього введеного символу містила вхідний рядок, або символ, який порушив збіг. Потім до словника додається введений підрядок. Якщо словник вже заповнений, то з нього попередньо видаляють менша за всіх використовуюму в порівняннях фразу.
Ключовим для розміру отримуваних кодів є розмір словника у фразах, тому що кожен код при кодуванні за методом LZ78 містить номер фрази в словнику. З останнього випливає, що ці коди мають постійну довжину, рівну округленням у більшу сторону бінарного логарифму розміру словника 8 (це кількість біт в байт-коді розширеного ASCII).
1.3.1 Приклади кодування
Закодувати по алгоритму LZ78 рядок " КРАСНАЯ КРАСКА", використовуючи словник довжиною 16 фраз.
|
Вхідна фраза (в словник) |
Код |
Позиція словника |
|
0 |
||
|
«К» |
<0,’K’> |
1 |
|
«Р» |
<0,’Р’> |
2 |
|
«А» |
<0,’А’> |
3 |
|
«С» |
<0,’С’> |
4 |
|
«Н» |
<0,’Н’> |
5 |
|
«АЯ» |
<3,’Я’> |
6 |
|
<0’ ’> |
7 |
|
|
«КР» |
<1,’Р’> |
8 |
|
«АС» |
<3,’С’> |
9 |
|
«КА» |
<1,’А’> |
10 |
Покажчик на будь-яку фразу такого словника - це число від 0 до 15, для його кодування достатньо чотирьох біт.
В останньому прикладі довжина отриманого коду дорівнює 10 * (4 +8) = 120 бітам.
Алгоритми LZ77, LZ78 і LZSS розроблені математиками і можуть використовуватися свободно. В 1984 Уелчем (Welch) був шляхом модифікації LZ78 створено алгоритм LZW.
Приклад
Закодувати по алгоритму LZW рядок " КРАСНАЯ КРАСКА ". Розмір словника - 500 фраз.
|
Вхідна фраза, wK (в словник) |
Код для w |
Позиція словника |
|
ASCII+ |
0-255 |
|
|
«КР» |
<0,’K’> |
256 |
|
«РА» |
<0,’Р’> |
257 |
|
«АС» |
<0,’А’> |
258 |
|
«СН» |
<0,’С’> |
259 |
|
«НА» |
<0,’Н’> |
260 |
|
«АЯ» |
<0,’А’> |
261 |
|
«Я » |
<0’ Я’> |
262 |
|
«К» |
<0,’ ’> |
263 |
|
«КРА» |
<256> |
264 |
|
«АСК» |
<258> |
265 |
|
«КА» |
<0’ К’> |
266 |
|
«А» |
<0’ А’> |
У цьому прикладі довжина отриманого коду дорівнює 12 * 9 = 108 бітам.
При переповненні словника, тобто коли необхідно внести нову фразу в повністю заповнений словник, з нього видаляють або найбільш рідко використовувану фразу, або всі фрази, що відрізняються від одиночного символу. Алгоритм LZW є запатентованим і, таким чином, являє собою інтелектуальну власність. Його безліцензійного використання особливо на апаратному рівні може спричинити за собою неприємності. Цікава історія патентування LZW. Заявку на LZW подали майже одночасно дві фірми - спочатку IBM і потім Unisys, але першою була розглянута заявка Unisys, яка й отримала патент. Проте, ще до патентування LZW був використаний в широко відомої у світі Unix програмі стиснення даних compress.
Список використаних джерел
Перевіте граматику – Виникнення. Я б назвав Інсторія виникнення
Ковзного, русизм
Виправити Ковзного – ВСЮДИ ПО ТЕКСТУ. Подайте спочатку англ..термін для внесення ясності в термінологію.
Добавте наглядність – СХЕМУ, АЛГОРИТМ, ПРИКЛАД
Дайте описй що то за метод, які ще бувать методи.
Аналогічно до попереднього. Подайте які бувають методи вцілому, і на слайд відповідно.
Можна наглядність ? Схему чи приклад.
Що то за таке програмування ? А як краще, щоб сутність алгоритму розкрити ?
Де той приклад ?!
Неузгоджене речення
Буду знімати бали за неякісно перекладений, вичитаний і т.д. і т.п. матеріал !
Слабо український приклад ? Невже немає чи самі не можете придумати ?!
ЦЕ взагалі ППЦ переклад ! Таке враження, що ви мені підсутури машинний переклад і навіть не вичитали.
Там чудові приклади – виколистайте їх в доповіді