ЛЗС алгоритам

Лампле-Зив-Стаков алгоритам (или Стаков алгоритам компресије) представља алгоритам за компресију без губитка података. У раду користи комбинацију ЛЗ77 алготирма компресије и фиксне Хафманове кодове. Првобитно је развијен као производ Стак електроник-а и служио је за компресију траке да би потом прерастао у софтвер прилагођен за компресију података на хард диску и као такав дуго бивао успешно продаван. Касније је постао неизоставан алгоритам компресије за бројне мрежне протоколе.

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

Стандарди

ЛЗС компресија је стандардизована по INCITS (раније по ANSI) стандарду.

Обухвата следеће интернет протоколе:

• RFC 1967 – PPP LZS-DCP протокол компресије
• RFC 1974 – PPP Stac LZS протокол компресије
• RFC 2395 – IP Payload компресија уз коришћење ЛЗС-а
• RFC 3943 – Transport Layer Security (TLS) протокол компресије

Алгоритам

ЛЗС при компресији и декомпресији користи алгоритам типа ЛЗ77. Она при компресији искористи последња 2 килобајта некомпресованих података као "sliding-window" речник. ЛЗС потом тражи подударање између података запамћених у речнику и, уколико га пронађе он кодира читаву дужину референце на речник. У супротном подаци из речника се кодирају као обичан бајт.

Уколико не дође до подударања, резервисане податке ћемо кодирати цифром '0' након чека следи 8 бита резервисаних за саме податке.

Уколико пак дође до подударања податке ћемо кодирати цифром '1', након чега следи кодирање дужине података које ћемо приказати у следећој таблици:

Дужина	Бит-но кодирање
2	00
3	01
4	10
5	1100
6	1101
7	1110
8 до 22	1111 xxxx, где xxxx представља дужину - 8
23 до 37	1111 1111 xxxx, где xxxx представља дужину - 23
дужина > 7	(1111 поновљен Н пута) xxxx, где Н представља реалан резултат (дужина + 7) / 15, а xxxx је дужина - (Н*15 - 7)