computer science

Lempel–Ziv–Storer–Szymanski

Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski rather than just read about it. In short: Lempel–Ziv–Storer–Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James A. Storer and Thomas Szymanski.

Key takeaways

Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Lempel–Ziv–Storer–Szymanski from memory before moving on to harder problems.

Reference excerpt

Lempel–Ziv–Storer–Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James A. Storer and Thomas Szymanski. LZSS was described in article "Data compression via textual substitution" published in Journal of the ACM (1982, pp. 928–951). LZSS is a dictionary coding technique. It attempts to replace a string of symbols with a reference to a dictionary location of the same string. The main difference between LZ77 and LZSS is that in LZ77 the dictionary reference could actually be longer than the string it was replacing. In LZSS, such references are omitted if the length is less than the "break even" point. Furthermore, LZSS uses one-bit flags to indicate whether the next chunk of data is a literal (byte) or a reference to an offset/length pair.

Example Here is the beginning of Dr. Seuss's Green Eggs and Ham, with character numbers at the beginning of lines for convenience. Green Eggs and Ham is a good example to illustrate LZSS compression because the book itself only contains 50 unique words, despite having a word count of 170. Thus, words are repeated, however not in succession.

0: I am Sam 9: 10: Sam I am 19: 20: That Sam-I-am! 35: That Sam-I-am! 50: I do not like 64: that Sam-I-am! 79: 80: Do you like green eggs and ham? 112: 113: I do not like them, Sam-I-am. 143: I do not like green eggs and ham.

This text takes 177 bytes in uncompressed form. Assuming a break even point of 2 bytes (and thus 2 byte pointer/offset pairs), and one byte newlines, this text compressed with LZSS becomes 95 bytes long:

0: I am Sam 9: 10: (5,3) (0,4) 16: 17: That(4,4)-I-am!(19,15) 32: I do not like 46: t(21,14) 50: Do you(58,5) green eggs and ham? 79: (49,14) them,(24,9).(112,15)(92,18).

Note: this does not include the 11 bytes of flags indicating whether the next chunk of text is a pointer or a literal. Adding it, the text becomes 106 bytes long, which is still shorter than the original 177 bytes.

Implementations Many popular archivers like ARJ, RAR, ZOO, LHarc use LZSS rather than LZ77 as the primary compression algorithm; the encoding of literal characters and of length-distance pairs varies, with the most common option being Huffman coding. Most implementations stem from a public domain 1989 code by Haruhiko Okumura. Version 4 of the Allegro library can encode and decode an LZSS format, but the feature was cut from version 5. The Game Boy Advance BIOS can decode a slightly modified LZSS format. Apple's macOS uses LZSS as one of the compression methods for kernel code.

Worked examples

Example 1 — a first encounter with Lempel–Ziv–Storer–Szymanski

Start with the simplest possible case. Write down what Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski 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–Storer–Szymanski 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–Storer–Szymanski

In research: Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski 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–Storer–Szymanski 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–Storer–Szymanski 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–Storer–Szymanski” →

Affiliate

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

How to study Lempel–Ziv–Storer–Szymanski in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Lempel–Ziv–Storer–Szymanski in simple terms?

Lempel–Ziv–Storer–Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James A. Storer and Thomas Szymanski.

Why does Lempel–Ziv–Storer–Szymanski 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–Storer–Szymanski?

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–Storer–Szymanski.