Lempel – Ziv – Stac - Lempel–Ziv–Stac

Lempel – Ziv – Stac (LZSnebo Stac komprese) je bezztrátová komprese dat algoritmus , který používá kombinaci LZ77 algoritmus komprese posuvného okna a opraven Huffmanovo kódování. To bylo původně vyvinuto Stac Electronics pro kompresi pásky a následně upraven pro komprese pevného disku a prodávány jako Stohovač software pro kompresi disku. Později byl specifikován jako kompresní algoritmus pro různé síťové protokoly. LZS je uvedena v Cisco IOS zásobník.

Standardy

Komprese LZS je standardizována jako standard INCITS (dříve ANSI).[1]

Komprese LZS je specifikována pro různé internetové protokoly:

  • RFC 1967 – Kompresní protokol PPP LZS-DCP (LZS-DCP)
  • RFC 1974 – Kompresní protokol PPP Stac LZS
  • RFC 2395 – Komprese užitečného zatížení IP pomocí LZS
  • RFC 3943 – Komprese protokolu Transport Layer Security (TLS) pomocí Lempel-Ziv-Stac (LZS)

Algoritmus

LZS komprese a dekomprese používá LZ77 algoritmus typu. Používá poslední 2 kB nekomprimovaných dat jako slovník posuvného okna.

Kompresor LZS hledá shody mezi daty, která mají být komprimována, a posledními 2 kB dat. Pokud najde shodu, zakóduje offset / délku odkazu do slovníku. Pokud není nalezena shoda, je další datový bajt zakódován jako „doslovný“ bajt. Proud komprimovaných dat končí koncovou značkou.

Formát komprimovaných dat

Data jsou kódována do proudu tokenů s proměnnou bitovou šířkou.

Doslovný bajt

Doslovný bajt je kódován jako bit „0“ následovaný 8 bity bajtu.

Odsazení / reference délky

Odkaz na offset / délku je zakódován jako bit '1', za kterým následuje kódovaný offset, následovaný kódovanou délkou. Jedním výjimečným kódováním je koncový marker, popsaný níže.

Posun může mít minimální hodnotu 1 a maximální hodnotu 2047. Hodnota 1 odkazuje na nejnovější bajt ve vyrovnávací paměti historie, bezprostředně předcházející dalšímu datovému bajtu, který má být zpracován. Posun je kódován jako:

  • Pokud je offset menší než 128: bit „1“ následovaný 7bitovou hodnotou offsetu.
  • Pokud je posun větší nebo roven 128: bit „0“ následovaný 11bitovou hodnotou posunu.

Délka je zakódována jako:

DélkaBitové kódování
200
301
410
51100
61101
71110
8 až 221111 xxxx, kde xxxx je délka - 8
23 až 371111 1111 xxxx, kde xxxx je délka - 23
délka> 37(1111 opakování N krát) xxxx, kde

N je celočíselný výsledek (délka + 7) / 15 a
xxxx je délka - (N * 15 - 7)

Koncová značka

Koncová značka je zakódována jako 9bitový token 110000000. Za koncovou značkou je podle potřeby připojeno 0 až 7 dalších '0' bitů, aby se proud vyložil na další hranici bajtu.

Patenty

Spin-off společnosti Stac Electronics Hifn je držitelem několika patentů na kompresi LZS.[2][3] Tyto patenty zanikly z důvodu nezaplacení poplatků a pokusy o jejich obnovení v roce 2007 selhaly.

V letech 1993–94 společnost Stac Electronics úspěšně žaloval Microsoft za porušení patentů LZS v EU DoubleSpace program komprese disku součástí MS-DOS 6.0.[4]

Viz také

Reference

  1. ^ INCITS / ANSI X3.241-1994 - Metoda komprese dat - adaptivní kódování s posuvným oknem pro výměnu informací
  2. ^ Přítel, Robert C. „Prohlášení společnosti Hifn o právech duševního vlastnictví nárokovaných v komprese draft-friend-tls-lzs, RFC1967, RFC1974, RFC2118, RFC2395 a RFC3078“. Citováno 21. července 2010.
  3. ^ Příteli, Roberte. „Prohlášení Hifna o právech duševního vlastnictví nárokovaných v kompresních algoritmech LZS a MPPC“. Citováno 21. července 2010.
  4. ^ Stížnost na porušení patentu a Poptávka po soudu před porotou Archivováno 09.05.2007 na Wayback Machine by Stac Electronics v. Microsoft Corporation