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

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

Стандарди

ЛЗС компресија је стандардизована по INCITS (раније по ANSI) стандарду.[http://www.incits.org/news-events/press-releases/incits-announces-the-approval-of-five-biometric-data-interchange-format-standardsINCITS/ANSI X3.241-1994 - Data Compression Method] – Adaptive Coding with Sliding Window for Information Interchange

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

– PPP LZS-DCP протокол компресије – PPP Stac LZS протокол компресије – IP Payload компресија уз коришћење ЛЗС-а – 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)

Референце

Категорија:Алгоритми Категорија:Структуре података