LZ77 i LZ78

LZ77 i LZ88 su dva algoritma kompresije bez gubitaka. Stvorili su ih Abraham Lampel i Jakov Ziv 1977. i 1978. godine. Algoritmi su još poznati i pod nazivima LZ1 te LZ2 a ujedno predsavljaju i osnovu za mnogobrojne varijacije raznih algoritama kompresije i dekompresije kao na primer LZS algoritam.

Obadva algoritma su tzv. rečnik koderi. Tj, čuvaju određenu kolicinu podataka iz zadate datoteke koju kompresuju. LZ77 tokom kompresije podržava [[Klizni-prozor protokol|klizni-prozor] (Sliding window protocol) a jedna od osnovnih razlika između dva algoritma je ta što LZ77 svoj posao počinje od samog početka rečnika dok LZ78 ima mogućnost slučajnog pristupa bilo kom delu rečnika.

LZ77

Algoritam LZ77 teži postiči kompresiju zamenom niza podataka koji se ponavljaju referencom na jedan od njih koji će se nalaziti u nekompresovanom delu datoteke. Da bi ceo postupak mogao da se izvede algoriam mora pamtiti neku količinu podataka za vreme izvršavanja postupka. Strukturu u kojoj se ovi podaci održavaju nazivamo klizni-prozor (Sliding window protocol) te kroz nju možemo provući poslednja 2, 4 ili 32 kilobajta podataka. Koder mora zadržati ove podatke sve dok ne postavi referencu na svaki duplikat.

U sledećoj tablici pokazaćemo princip rada ovog algoritma korišćenjem rečnika bafera veličine 12, te veličine 9. Položaj uz desnu iviču rečnika se prilikom komprimacije mora uzeti u obzir a kao proizvod rada algoritma imamo kolonu izlaz (poslednju kolonu naše tabele).

Baferi rade po principu kliznih-prozora. Podatak koji uđe u bafer moraće proći dužinu rečnika i postaviti reference na sve duplikate. Ovakav način rada neće biti vremenski najefikasniji, ali će rezultat biti efikasan jer u bafer ni jednog trenutka neće dospeti neki duplikat.

Example of a LZ77 compression sliding window

Linija

12

11

10

9

8

7

6

5

4

3

2

1

0

1

2

3

4

5

6

7

8

9

Izlaz

1

(Prazno)

a

a

c

a

a

c

a

b

c

a

$\Longrightarrow$

(0,0,"a")

2

(Prazno)

a

a

c

a

a

c

a

b

c

a

b

$\Longrightarrow$

(1,1,"c")

3

(Prazno)

a

a

c

a

a

c

a

b

c

a

b

a

a

$\Longrightarrow$

(3,4,"b")

4

(Prazno)

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

(Prazno)

$\Longrightarrow$

(3,3,"a")

5

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

(Prazno)

$\Longrightarrow$

(12,3,"$")

završetak

LZ78

LZ78 algoritam pak kompresiju vrši tako što u rečnik karaktere smešta na sledeći način: rečnik[indeks] = {indeksPrethodnog, karakter}. Dakle podatke bukvalno "vezuje" jedne za druge odgovarajućim indeksom tako što će mu dodeliti indeks prethodnog s tim da će karaktere smeštati "od nazad" da bi ispis mogao da funkcioniše.

Primer: ako želimo da smestimo karaktere ABC uradićemo na sledeći način rečnik[1] = {0, 'A'}, rečnik[2] = {1, 'B'}, rečnik[3] = {2, 'C'}.

Ukoliko se pri dodavanju novog karaktera u rečnik dati karakter već pronađe unutar njega, neće se dodavati ponovo isti karakter već će se indeks promeniti da bi mogao da pristupi više pozicija. Ukoliko karakter nije pronađen u rečniku postupak je klasičan i očekivan, na novo mesto sa novim indeksom ga dodajemo i pamtimo mu indeks prethodnog.

Spoljašnje veze

• LZ Algoritam kompresije
• LZ kodovanje FILM