Лемель - Зива әдісі

Пән: Автоматтандыру, Техника
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

Қазақстан Республикасы білім және ғылым министірлігі

Семей қаласының Шәкәрім атындағы мемлекеттік университеті

«Автоматика және элекротехника» кафедрасы»

СӨЖ

Тақырыбы: Лемель -Зива әдісі

Орындаған: Кусманов А. Қ.

Тобы: АУ-301

Тексерген: Кожахметова Д. О.

Семей 2015 ж.

Лемель-Зива анықтамасы

Израиль екі жұмыс алгоритмдерін отбасы ppinadlezhat әдістерін кодтау ғалымдар - Ziva және Lemelel, 1977 жылы жарық көрген. олардың мәні дестесін мәтінінде бұл фраза олар жерге көрсеткіш ауыстырылады Бұл мәтін қазірдің өзінде бұрын пайда болды. Отбасы алгоритм Lemelel-Ziva әдісі деп аталады және LZ-қысу деп аталады. Тез Бұл әдіс мәтін және кодтауға болады құрылымын ppisposablivaetsya үшін олар өте жиі пайда, өйткені қысқа функция сөздер. Жаңа сөздер мен сөз тіркестерін бұрын кездесетін сөздер бөлігі ретінде құрылуы мүмкін. Декодтау тікелей жүзеге асырылатын - индексінің қарапайым ауыстыру тіркесін аяқталды ол көрсетеді сөздік. Іс жүзінде, LZ-әдіс жақсы жетеді қысу, ол құрылған тез жұмыс өте маңызды ерекшелігі болып табылады. (Кезде, біз мәтін туралы әңгіме, ол кодтау кейбір ұшырайды деп болжануда векторы дискретті ақырғы алфавитін деректерді, ол мәтінде міндетті емес, сөзі сөзбе-сөз мағынасы. )

Ең сөздік кодтау әдістері идеяның авторлары мен Lemelel Ziva аталады, және жиі олардың бәрі бірдей шифрлау алгоритмі пайдалану деп ойлаймын. Қарай шын мәнінде алгоритмдер осы отбасының әр түрлі мүшелері өте оның жұмыс істеу егжей ерекшеленеді.

Лемель-Зива әдістері

Шеннон-Фано, Хаффман және арифметикалық әдістер жалпы статистикалық әдістер деп аталады. Сөздіктік алгоритмдердің математикалық дәлелі азырақ, бірақ олар өте қолайлы.

LZ77 алгоритмі

LZ77 негізгі ойы келесіде: мәліметтегі бір символдар жолдың үзіндігі екінші және келесі кірулері оның бірінші кіруінің сілтеуімен ауыстырылады. LZ77 алгоритмі мәліметтің қаралған бөлігін сөздік ретінде қолданады. Қысу үшін алгоритм мәліметтің келесі үзіндігін сөздіктің ішіндегі сілтеумен ауыстыруға тырысады.

LZ77 мәліметтің үстімен өтетін, екі бірдей емес бөлікке бөлінген, жылжымалы терезені қолданады. Бірінші бөлік, сөздік деп аталатын көп мөлшерлі болады және мәліметтің қаралған бөлігін қабылдайды. Екінші, аз мөлшерлі, буфер деп аталатын - мәліметтің әлі таңбаланбаған символдарынан тұрады. Негізі терезенің мөлшері бірнеше килобайт, ал буфердің мөлшері - жүз байттан аспайды. Алгоритм сөздіктен (терезенің үлкен бөлігінен) буфердің ішіндегісімен сай келетін жолды іздеуді тырысады.

LZ77 алгоритмі үш элементтен тұратын код шығарады :

буфердегі жол үзіндіктің басы мен сөздіктегі жолға сәйкес келетін оның ығысуы;
сәйкес келген жолдың ұзындығы;
жолдан кейінгі буфердегі бірінші символ.

LZ77 алгоритмнің кемшіліктері:

сөздіктің мөлшері өскен сайын алгоритм-кодердің жұмыс істеу жылдамдығы пропорционал азаяды;
жалғыз симводарды таңбалау өте тиімсіз.

Мысал 1

“КЕРІ КЕРНЕУ” жолды LZ77 алгоритмі бойынша таңбалау.

сөздік (8 байт): сөздік (8 байт)

буфер(5 байт):

буфер

(5 байт)

таңба: таңба

сөздік (8 байт):

буфер(5 байт):

таңба: 1

сөздік (8 байт): Е

буфер(5 байт): Р

таңба: І

КЕРІ_

ЕРІ_К

РІ_КЕ

І_КЕР

_КЕРН

КЕРНЕ

ЕУ . . .

0, 0, К

0, 0, Е

0, 0, Р

0, 0, І

0, 0, _

3, 3, Н

0, 1, У

Кодтың ұзындығы былай есептеледі:

жолдың ұзындығы буфер мөлшерінен үлкен бола алмайды, ал ығысу сөздіктің мөлшерінен-1-ден үлкен бола алмайды. Сондықтан, ығысудың екілік кодының ұзындығы log ₂ (сөздіктің мөлшері) бүтін үлкен жағына қарай дөңгеленген мәніне тең, ал жолдың екілік кодының ұзындығы log ₂ (буфердің мөлшері + 1) бүтін үлкен жағына қарай дөңгеленген мәніне тең. Ал символ 8 битпен таңбаланады (ASCII бойынша) :

(сөздіктің мөлшері) + log ₂ (буфердің мөлшері + 1) + 8.

Мысалымызда кодтың ұзындығы:

(log ₂ 8+ log ₂ (5+1) +8) *7 = 98 бит,

бастапқысы: 11*8 = 88 бит. Қарастырған мәтін жолы өте қысқа болғандықтан (қысу әдістері көп мөлшерлі файлдарға қолданады) қысу әдісті қолданғаннан кейін көлемі бастапқыдан көп болды.

Мысал 2

“КРАСНАЯ КРАСКА” жолды LZ77 алгоритмі бойынша таңбалау.

СӨЗДІК (8): СӨЗДІК (8)

БУФЕР (5): БУФЕР (5)

ТАҢБА: ТАҢБА

СӨЗДІК (8):

КР

КРА

КРАС

КРАСН

КРАСНАЯ

КРАСНАЯ_

АЯ_КРАСК

БУФЕР (5):

КРАСН

РАСНА

АСНАЯ

СНАЯ_

НАЯ_К

АЯ_КР

_КРАС

КРАСК

ТАҢБА:

0, 0, К

0, 0, Р

0, 0, А

0, 0, С

0, 0, Н

5, 1, Я

0, 0, _

0, 4, К

0, 0, А

Соңғы жолында “А” әріп соңғы болғандықтан, сөздіктен алынбайды. Мысалымызда кодтың ұзындығы: 9*(3+3+8) = 126 бит, бастапқысы: 14*8 = 112 бит.

Таңбаны шешу

Кіріс таңба басылу сөздік

LZSS алгоритмі

LZSS коды таңбаланбаған символдан өзгеше бірбитті префикстен басталады. Таңба екі символдан тұрады: ығысу мен ұзындықтан, LZ77 дегідей. LZSS-та терезе сәйкес жолдын тура ұзындығана жылжиды, немесе 1-ге, егер буферде сөздіктегідей сәйкес жол болмаса. Жолдың ұзындығы әрқашан нольден көп, сондықтан жол ұзындығы үшін екілік кодтың ұзындығы - бұл буфердің ұзындығынан көп, бүтін жаққа дөңгеленген екілік логарифмі.

Мысал 2

“КЕРІ КЕРНЕУ” жолды LZSS алгоритмі бойынша таңбалау.

сөздік (8 бит): сөздік (8 бит)

буфер(5 бит):

буфер

(5 бит)

таңба: таңба

ұзындық: ұзындық

сөздік (8 бит):

буфер(5 бит):

таңба: 1

ұзындық: 2

сөздік (8 бит):

буфер(5 бит):

таңба:

ұзындық:

КЕРІ_

ЕРІ_К

РІ_КЕ

І_КЕР

_КЕРН

КЕРНЕ

НЕУ . .

ЕУ . . .

0, К

0, Е

0, Р

0, І

0, _

3, 3

0, Н

0, 1

Алынған таңбаның ұзындығы: 6*9+7*3=75

LZ77 және LZSS алгоритмдердің айқын кемшіліктері:

сөздік ұзындығынан үлкен қашықтықта бір-бірінен тұрған жолдарды таңбалауды мүмкін емес,
таңбалауға болатын жолдың ұзындығы буфердің мөлшерімен шектелген.

Егер сөздік пен буфердің мөлшерін өсіре берсек, онда таңбалаудың тиімділігі азаяды, яғни осы шамалар өскен сайын, ығысу мен ұзындықтың кодтар ұзындығы да өсе бастайды, ал бұл кішкентай жолдардың кодтарын өте үлкен қылады. Тағы да алгоритм-кодердің жұмыс жасау уақыты көбейеді.

Таңбаны шешу

Мынадай сығылған мәліметті алдық: 0, К; 0, Р; 0, А; 0, С; 0, Н; 5, 1; 0, Я; 0, _; 0, 4; 4, 1; 0, 1