CoreSource checked

LZW

Compresses streams by replacing repeated phrases with dictionary codes built during encoding.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Intermediate
Family: Dictionary Compression
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

LZW starts from a dictionary of single symbols and adds longer phrases as it reads the input. The decoder rebuilds the same dictionary from the emitted codes, so explicit phrase strings do not need to be transmitted.

Core Concepts

dictionary referencecodeword encodingdictionary compressionsymbol representationlossless decodingstream encoding

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(k)

When to Use

Use when adaptive phrase dictionaries are appropriate and decoder synchronization is straightforward.
Use when a simple dictionary compressor is more useful than match-distance coding.

When Not to Use

Avoid when dictionary reset and code-width policy are not defined.
Avoid expecting gains on short, random, or already-compressed inputs.

What It Does

Maintains a synchronized phrase dictionary
Emits codes for the longest known phrase
Adds new phrases formed by previous phrase plus next symbol

Use Cases

Dictionary-based lossless compression
Educational compression examples
Data with recurring phrases over a stable alphabet

Inputs

Byte or symbol stream

Outputs

Sequence of dictionary codes

Key Formulas (1)

Dictionary extension

dictionary_{[next_code]} = current_phrase + next_symbol

dictionary[next_code] = current_phrase + next_symbol

Adds the next unseen phrase so later repeats can be emitted as compact codes.

Pseudocode

1.Initialize dictionary with single-symbol phrases
2.Let current phrase be empty
3.Read the next symbol and test current + symbol
4.If it exists, extend current
5.Otherwise emit current's code and add current + symbol to the dictionary
6.Emit the final current phrase

Canonical Example

Input: 'ABABABA'
Output: codes that reuse dictionary entries for repeated 'AB' and 'ABA' phrases
Explanation: As phrases are emitted, both encoder and decoder add the same longer phrases to their dictionaries.

Implementation Notes

Start with a known alphabet dictionary.
Document maximum dictionary size and reset behavior.
Test repeated patterns such as ABABABA and edge cases around new dictionary entries.

Common Pitfalls

Encoder and decoder dictionary updates must occur in the same order.
The special case where a code refers to the phrase currently being created must be handled.
Code-width growth and dictionary reset rules affect interoperability.