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

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

Стандарди

уреди

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

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

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

Референце

уреди
  1. ^ [1], ЛЗ77 и ЛЗ78 алгоритми
  2. ^ X3.241-1994 - Data Compression Method – Adaptive Coding with Sliding Window for Information Interchange