computer science

Lempel–Ziv–Stac

Lempel–Ziv–Stac is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Lempel–Ziv–Stac rather than just read about it. In short: Lempel–Ziv–Stac (LZS, or Stac compression or Stacker compression) 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.

Key takeaways

Lempel–Ziv–Stac belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Lempel–Ziv–Stac to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Lempel–Ziv–Stac from memory before moving on to harder problems.

Reference excerpt

Lempel–Ziv–Stac (LZS, or Stac compression or Stacker compression) 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. 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:

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. 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.

Worked examples

Example 1 — a first encounter with Lempel–Ziv–Stac

Start with the simplest possible case. Write down what Lempel–Ziv–Stac claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Lempel–Ziv–Stac before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Lempel–Ziv–Stac ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Lempel–Ziv–Stac

In research: Lempel–Ziv–Stac appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Lempel–Ziv–Stac in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Lempel–Ziv–Stac is common in secondary-school and first-year university syllabi. It links to neighbouring topics Data compression, Lossless compression algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Lempel–Ziv–Stac outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Lempel–Ziv–Stac” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Lempel–Ziv–Stac in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Lempel–Ziv–Stac means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Lempel–Ziv–Stac out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Lempel–Ziv–Stac in simple terms?

Why does Lempel–Ziv–Stac matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Lempel–Ziv–Stac?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Lempel–Ziv–Stac.