Lempel–Ziv–Stac

Lempel–Ziv–Stac (LZS, or Stac compression or Stacker compression[1]) is a lossless data compression algorithm that uses a combination of the LZ77 sliding-window compression algorithm and fixed Huffman coding. It was originally developed by Stac Electronics for tape compression, and subsequently adapted for hard disk compression and sold as the Stacker disk compression software. It was later specified as a compression algorithm for various network protocols. LZS is specified in the Cisco IOS stack.

Standards

LZS compression is standardized as an INCITS (previously ANSI) standard.[2]

LZS compression is specified for various Internet protocols:

  • RFC 1967 – PPP LZS-DCP Compression Protocol (LZS-DCP)
  • RFC 1974 – PPP Stac LZS Compression Protocol
  • RFC 2395 – IP Payload Compression Using LZS
  • RFC 3943 – Transport Layer Security (TLS) Protocol Compression Using Lempel-Ziv-Stac (LZS)

Algorithm

LZS compression and decompression uses an LZ77 type algorithm. It uses the last 2 KB of uncompressed data as a sliding-window dictionary.

An LZS compressor looks for matches between the data to be compressed and the last 2 KB of data. If it finds a match, it encodes an offset/length reference to the dictionary. If no match is found, the next data byte is encoded as a "literal" byte. The compressed data stream ends with an end-marker.

Compressed data format

Data is encoded into a stream of variable-bit-width tokens.

Literal byte

A literal byte is encoded as a '0' bit followed by the 8 bits of the byte.

Offset/length reference

An offset/length reference is encoded as a '1' bit followed by the encoded offset, followed by the encoded length. One exceptional encoding is an end marker, described below.

An offset can have a minimum value of 1 and a maximum value of 2047. A value of 1 refers to the most recent byte in the history buffer, immediately preceding the next data byte to be processed. An offset is encoded as:

  • If the offset is less than 128: a '1' bit followed by a 7-bit offset value.
  • If the offset is greater than or equal to 128: a '0' bit followed by an 11-bit offset value.

A length is encoded as:

Length Bit encoding
2 00
3 01
4 10
5 1100
6 1101
7 1110
8 to 22 1111 xxxx, where xxxx is length − 8
23 to 37 1111 1111 xxxx, where xxxx is length − 23
length > 37 (1111 repeated N times) xxxx, where

N is integer result of (length + 7) / 15, and
xxxx is length - (N*15 − 7)

End marker

An end marker is encoded as the 9-bit token 110000000. Following the end marker, 0 to 7 extra '0' bits are appended as needed, to pad the stream to the next byte boundary.

Patents

Stac Electronics' spin-off Hifn has held several patents for LZS compression.[3][4] These patents lapsed due to non-payment of fees and attempts to reinstate them in 2007 failed.

In 1993–94, Stac Electronics successfully sued Microsoft for infringement of LZS patents in the DoubleSpace disk compression program included with MS-DOS 6.0.[5]

See also

References

  1. ^ "Understanding Data Compression". Cisco. Retrieved 2021-05-07.
  2. ^ INCITS/ANSI X3.241-1994 - Data Compression Method – Adaptive Coding with Sliding Window for Information Interchange
  3. ^ Friend, Robert C. "Hifn's Statement about IPR claimed in draft-friend-tls-lzs-compression, RFC1967, RFC1974, RFC2118, RFC2395, and RFC3078". Retrieved 21 July 2010.
  4. ^ Friend, Robert. "Hifn's Statement on IPR Claimed in LZS and MPPC compression algorithms". Retrieved 21 July 2010.
  5. ^ Complaint for patent infringement and Demand for jury trial Archived 2007-05-09 at the Wayback Machine by Stac Electronics v Microsoft Corporation

Read other articles:

Edgar Morin

Edgar Morin (2011). Edgar Morin adalah seorang filsuf dan sosiolog dari Prancis.[1] Dia dikenal karena keahliannya dalam bidang ilmu transdisiplin. Biografi Pada awal abad ke 20, keluarganya pindah dari Yunani ke Marseille[2] lalu ke Prancis di mana Edgar dilahirkan pada tanggal 8 Juli 1921 dengan nama Edgar Nahoum. Perkenalannya pertama kali pada sosialisme terjadi saat Perang Saudara di Spanyol. Ketika Jerman menginvansi Prancis pada tahun 1940, Edgar mengungsi ke Toulouse d...

 

 

Kebun Binatang Taronga

Jerapah di Kebun Binatang Taronga Sydney dengan pencakar langit Sydney di latar belakang Kebun Binatang Taronga (Taronga Zoo) adalah kebun binatang kota Sydney, Australia yang pertama kali dibuka pada tanggal 7 Oktober 1916. Kebun binatang ini terdapat di daerah pesisir pantai dari pelabuhan Sydney (Sydney Harbour) di Mosman. Luas kebun binatang ini adalah 287 hektare dan memiliki lebih dari 26.000 binatang. Kebun binatang ini dibagi menjadi delapan area dengan bermacam anjungan dalam gedung ...

 

 

Henry Lohmann

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Untuk politikus Selandia Baru, lihat Henry Lahmann. Henry LohmannLahir(1924-02-14)14 Februari 1924Blommenslyst, DenmarkMeninggal4 Oktober 1967(1967-10-04) (umur 43)DenmarkPekerjaanPemeranTahun aktif1954-1967 Henry Lohmann (14 Februari 1924&#...

St. Francois County, Missouri

County in Missouri, United States County in MissouriSaint Francois CountyCountySt. Francois County Courthouse in Farmington SealLocation within the U.S. state of MissouriMissouri's location within the U.S.Coordinates: 37°46′55″N 90°25′20″W / 37.781944444444°N 90.422222222222°W / 37.781944444444; -90.422222222222Country United StatesState MissouriFoundedDecember 19, 1821Named forSt. Francis RiverSeatFarmingtonLargest cityFarmingtonArea •...

 

 

Franco Donatoni

Franco DonatoniUn primo piano di Franco Donatoni Nazionalità Italia GenereMusica contemporanea Periodo di attività musicale1950 – 2000 EtichettaRicordi, Stradivarius Album pubblicati10 Modifica dati su Wikidata · Manuale Franco Donatoni (Verona, 9 giugno 1927 – Milano, 17 agosto 2000) è stato un compositore italiano. Indice 1 Biografia 1.1 Gli studi 1.2 L'insegnamento 1.3 Premi e riconoscimenti 1.4 L'attività di scrittore 1.5 Gli ultimi anni 2 La musica 2...

 

 

Who Fears Death

2010 science fantasy novel by Nnedi Okorafor Who Fears Death AuthorNnedi OkoraforCover artistGreg RuthCountryNigeriaLanguageEnglishGenreScience fantasy, AfricanfuturismPublisherDAW/PenguinPublication date1 June 2010Media typePrint, e-book, audio bookPages304AwardsWorld Fantasy Award (2011)ISBN9780756406691OCLC1269240111Preceded byThe Book of Phoenix  Who Fears Death is a science fantasy novel by Nigerian-American writer Nnedi Okorafor, published in 2010 by DAW, an imprint ...

Umma Islamic Party

Political party in Saudi Arabia Umma Islamic Party حزب الأمة الإسلاميLeaderDr. Abdullah al-SalimFounded10 February 2011HeadquartersRiyadhIdeologyIslamismReformismShuraWebsiteislamicommaparty.orgPolitics of Saudi ArabiaPolitical partiesElections The Umma Islamic Party (Arabic: حزب الأمة الإسلامي) is a political party in Saudi Arabia that was formed on 10 February 2011 in response to the Arab Spring. Formed by a collective of opposition members including Isl...

 

 

Tirant le Blanc

Pour les articles homonymes, voir Tirant. Pour le film, voir Tirant le Blanc (film). Tirant le Blanc Page de garde de la traduction espagnole (1511) de Tirante el Blanco. Auteur Joanot Martorell Pays  Royaume de Valence Genre roman chevaleresque Version originale Langue catalan-valencien Titre Tirant lo Blanc Lieu de parution Valence Date de parution 1490 Version française Traducteur Anne Claude de Caylus Date de parution 1737 modifier  Tirant le Blanc (titre original en catalan-v...

 

 

Lutheranism by region

Aspect of religion Lutherans By number of adherents By percent of total populationTotal populationc. 77 million+ (worldwide, 2020)[1][2]Regions with significant populations Germany10,814,631 Ethiopia10,404,128 Tanzania7,916,253 Sweden5,900,000 Indonesia5,705,589 India4,386,957 Denmark4,339,511 Madagascar4,000,000 Finland3,800,000 Norway3,746,308 United States2,900,000ScripturesBible (Old and New Testament) Part of a series...

Ta Mok

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (mars 2013). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ? Comm...

 

 

King Cotton

Slogan of the pre-Civil War American South For other uses, see King Cotton (disambiguation). King Cotton, a panoramic photograph of a cotton plantation in 1907, now housed in the Library of Congress King Cotton is a slogan that summarized the strategy used before the American Civil War (of 1861–1865) by secessionists in the southern states (the future Confederate States of America) to claim the feasibility of secession and to prove there was no need to fear a war with the northern states. T...

 

 

سارة الخولي

سارة الخولي معلومات شخصية الميلاد 15 فبراير 1988 (36 سنة)  القاهرة  مواطنة مصر  الطول 175 سنتيمتر  الحياة العملية المدرسة الأم الجامعة الأمريكية في الشارقة  المهنة عارضة،  ومتسابقة ملكة الجمال  اللغة الأم العربية  اللغات العربية  تعديل مصدري - تعديل   سا�...

Madam Satan

Madam SatanKartu lobi rilis teatrikalSutradaraCecil B. DeMilleProduserCecil B. DeMilleDitulis olehDialogue:[1]Gladys UngerElsie JanisSkenarioJeanie MacphersonPemeranKay JohnsonReginald DennyLillian RothRoland YoungSinematograferHarold RossonPenyuntingAnne BauchensPerusahaanproduksiMetro-Goldwyn-MayerDistributorLoew's Inc.Tanggal rilis 20 September 1930 (1930-09-20) (AS) Durasi116 menitNegaraAmerika SerikatBahasaInggris Madam Satan atau Madame Satan adalah sebuah film komedi m...

 

 

Post Office Limited

British retail post office company owned by the government of the United Kingdom Post Office LimitedNative nameWelsh: Swyddfa'r Post Cyf.Scottish Gaelic: Oifis a' PhuistIrish: Oifig an PhoistFormerlyPost Office Counters Ltd (1987–2001)[1]Company typeState-owned private company limited by sharesIndustryPostal servicePredecessorGeneral Post OfficeFounded13 August 1987[1]HeadquartersLondon, EnglandArea servedUnited KingdomKey peopleNick Read (CEO) [2]Revenue£9...

 

 

Stein 2051

Star in the constellation Camelopardalis Stein 2051 Image of Stein 2051 B and a background star taken by the Hubble Space Telescope.[1]Credit: NASA, ESA, and K. Sahu (STScI) Observation dataEpoch J2000      Equinox J2000 Constellation Camelopardalis Stein 2051 A Right ascension 04h 31m 11.5181s[2] Declination +58° 58′ 37.461″[2] Apparent magnitude (V) 10.977[2] Stein 2051 B Right ascension 04h 3...

Sathya Sai Baba

Indian spiritual guru (1926–2011) Sathyanarayana Raju redirects here. For other uses, see Sathyanarayana Raju (disambiguation). Sathya Sai BabaPersonalBornRatnakaram Sathyanarayana Raju(1926-11-23)23 November 1926Puttaparthi, Madras Presidency, British India (present-day Andhra Pradesh, India)Died24 April 2011(2011-04-24) (aged 84)Puttaparthi, Andhra Pradesh, IndiaReligionHinduismNationalityIndianSectSathya Sai Baba movementSignatureOrganizationInstitute Sri Sathya Sai Central Trust Sr...

 

 

Ozark–St. Francis National Forest

United States National Forest located in the state of Arkansas Ozark-St. Francis National ForestLocationArkansas, U.S.Nearest cityRussellville, ARCoordinates35°16′30″N 94°28′32″W / 35.27500°N 94.47556°W / 35.27500; -94.47556Area1,159,801 acres (4,693.55 km2)EstablishedMarch 6, 1908; 116 years ago (March 6, 1908)Governing bodyU.S. Forest ServiceWebsiteOzark-St. Francis National Forests The Ozark – St. Francis National Forest is ...

 

 

Barocco a Milano

Galleria degli arazzi con gli affreschi del Tiepolo di Palazzo Clerici: uno degli interni più significativi del panorama barocco milanese Per barocco a Milano[1] si intende lo stile artistico dominante tra il Seicento e la prima metà del Settecento nella città. Infatti grazie all'operato dei cardinali Borromeo e alla sua importanza nei domini italiani, prima spagnoli e poi austriaci, Milano visse una vivace stagione artistica[2] in cui assunse il ruolo di centro propulsore ...

Marie Souvestre

Cet article est une ébauche concernant les femmes ou le féminisme. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Souvestre. Marie SouvestreBiographieNaissance 28 avril 1830BrestDécès 30 mars 1905 (à 74 ans)SurreyNationalité françaiseActivités Éducatrice, pédagoguePère Émile Souvestremodifier - modifier le code - modifier Wikidata Marie Claire Souvestre, née l...

 

 

Musée océanographique de Kaliningrad

Le Musée océanographique de Kaliningrad. Le Musée océanographique de Kaliningrad (en russe : Музей Мирового океана, Mouzeï Mirovogo okeana, « Musée du monde des océans ») est un musée océanographique situé à Kaliningrad en Russie. Le musée possède aussi une filiale à Saint-Pétersbourg. Ce musée est consacré à tous les aspects des océans et mers du monde : la biologie, la géographie et la géologie marines, ainsi que l'histoire de la...