LZS algoritam

Lample-Ziv-Stakov algoritam (ili Stakov algoritam kompresije) predstavlja algoritam za kompresiju bez gubitka podataka. U radu koristi kombinaciju LZ77 algotirma kompresije i fiksne Hafmanove kodove. Prvobitno je razvijen kao proizvod Stak elektronik-a i služio je za kompresiju trake da bi potom prerastao u softver prilagođen za kompresiju podataka na hard disku i kao takav dugo bivao uspešno prodavan. Kasnije je postao neizostavan algoritam kompresije za brojne mrežne protokole.

Kao proizvod rada ovog algoritma dobijamo datoteku koja će u potpunosti odgovarati originalu, bez i jedne razlike a samim postupkom dekomprimacije smanjićemo količinu prostora koju zauzima u memoriji.

Standardi

LZS kompresija je standardizovana po INCITS (ranije po ANSI) standardu.

Obuhvata sledeće internet protokole:

• RFC 1967 – PPP LZS-DCP protokol kompresije
• RFC 1974 – PPP Stac LZS protokol kompresije
• RFC 2395 – IP Payload kompresija uz korišćenje LZS-a
• RFC 3943 – Transport Layer Security (TLS) protokol kompresije

Algoritam

LZS pri kompresiji i dekompresiji koristi algoritam tipa LZ77. Ona pri kompresiji iskoristi poslednja 2 kilobajta nekompresovanih podataka kao "sliding-window" rečnik. LZS potom traži podudaranje između podataka zapamćenih u rečniku i, ukoliko ga pronađe on kodira čitavu dužinu reference na rečnik. U suprotnom podaci iz rečnika se kodiraju kao običan bajt.

Ukoliko ne dođe do podudaranja, rezervisane podatke ćemo kodirati cifrom '0' nakon čeka sledi 8 bita rezervisanih za same podatke.

Ukoliko pak dođe do podudaranja podatke ćemo kodirati cifrom '1', nakon čega sledi kodiranje dužine podataka koje ćemo prikazati u sledećoj tablici:

Dužina	Bit-no kodiranje
2	00
3	01
4	10
5	1100
6	1101
7	1110
8 do 22	1111 xxxx, gde xxxx predstavlja dužinu - 8
23 do 37	1111 1111 xxxx, gde xxxx predstavlja dužinu - 23
dužina > 7	(1111 ponovljen N puta) xxxx, gde N predstavlja realan rezultat (dužina + 7) / 15, a xxxx je dužina - (N*15 - 7)