ЛЗ77 и ЛЗ78

Из Википедије, слободне енциклопедије

ЛЗ77 и ЛЗ88 су два алгоритма компресије без губитака. Створили су их Абрахам Лампел и Јаков Зив 1977. и 1978. године. Алгоритми су још познати и под називима ЛЗ1 те ЛЗ2 а уједно предсављају и основу за многобројне варијације разних алгоритама компресије и декомпресије као например ЛЗС алгоритам.

Обадва алгоритма су тзв. речник кодери. Тј, чувају одређену колицину података из задате датотеке коју компресују. ЛЗ77 током компресије подржава [[Клизни-прозор протокол|клизни-прозор] (Sliding window protocol) а једна од основних разлика између два алгоритма је та што ЛЗ77 свој посао почиње од самог почетка речника док ЛЗ78 има могућност случајног приступа било ком делу речника.

ЛЗ77[уреди]

Алгоритам ЛЗ77 тежи постичи компресију заменом низа података који се понављају референцом на један од њих који ће се налазити у некомпресованом делу датотеке. Да би цео поступак могао да се изведе алгориам мора памтити неку количину података за време извршавања поступка. Структуру у којој се ови подаци одржавају називамо клизни-прозор (Sliding window protocol) те кроз њу можемо провући последња 2, 4 или 32 килобајта података. Кодер мора задржати ове податке све док не постави референцу на сваки дупликат.[1]

У следећој таблици показаћемо принцип рада овог алгоритма коришћењем речника бафера величине 12, те величине 9. Положај уз десну ивичу речника се приликом компримације мора узети у обзир а као производ рада алгоритма имамо колону излаз (последњу колону наше табеле).

Бафери раде по принципу клизних-прозора. Податак који уђе у бафер мораће проћи дужину речника и поставити референце на све дупликате. Овакав начин рада неће бити временски најефикаснији, али ће резултат бити ефикасан јер у бафер ни једног тренутка неће доспети неки дупликат.[2]

Example of a LZ77 compression sliding window
Линија 12 11 10  9  8  7  6  5  4  3  2  1  0  1  2  3  4  5  6  7  8  9 Излаз
1 (Празно) a a c a a c a b c a (0,0,"a")
2 (Празно) a a c a a c a b c a b (1,1,"c")
3 (Празно) a a c a a c a b c a b a a (3,4,"b")
4 (Празно) a a c a a c a b c a b a a a c (Празно) (3,3,"a")
5 a a c a a c a b c a b a a a c (Празно) (12,3,"$")
завршетак

ЛЗ78[уреди]

ЛЗ78 алгоритам пак компресију врши тако што у речник карактере смешта на следећи начин: речник[индекс] = {индексПретходног, карактер}. Дакле податке буквално "везује" једне за друге одговарајућим индексом тако што ће му доделити индекс претходног с тим да ће карактере смештати "од назад" да би испис могао да функционише.[3]

Пример: ако желимо да сместимо карактере АБЦ урадићемо на следећи начин речник[1] = {0, 'А'}, речник[2] = {1, 'Б'}, речник[3] = {2, 'Ц'}.

Уколико се при додавању новог карактера у речник дати карактер већ пронађе унутар њега, неће се додавати поново исти карактер већ ће се индекс променити да би могао да приступи више позиција. Уколико карактер није пронађен у речнику поступак је класичан и очекиван, на ново место са новим индексом га додајемо и памтимо му индекс претходног.

Референце[уреди]

  1. [1], ПефПак компресија
  2. [2], Алгоритам компресије ЛЗ77
  3. [3] Лампел-Зивов нотес

Спољашње везе[уреди]