ЛЗ77 и ЛЗ78

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

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

ЛЗ77

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

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

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

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

$\Longrightarrow$

(0,0,"a")

2

(Празно)

a

a

c

a

a

c

a

b

c

a

b

$\Longrightarrow$

(1,1,"c")

3

(Празно)

a

a

c

a

a

c

a

b

c

a

b

a

a

$\Longrightarrow$

(3,4,"b")

4

(Празно)

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

(Празно)

$\Longrightarrow$

(3,3,"a")

5

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

(Празно)

$\Longrightarrow$

(12,3,"$")

завршетак

ЛЗ78

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

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

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

Спољашње везе

• ЛЗ Алгоритам компресије
• ЛЗ кодовање ФИЛМ