> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/38.-compression-and-complexity/38.6-lzw-compression.md). # 38.6 LZW Compression ## Key Idea The LWZ approach is based on the idea of exploiting redundancy and patterns in the input data to achieve compression. Basically, each codeword can represent multiple symbols. For example, imagine a sequence of symbols `ABCABCA`. In traditional compression, each symbol would be mapped to a fixed-length codeword, resulting in a compressed sequence like `010001001000100100`. With the LWZ approach, the codewords can be based on patterns in the input data. In this case, the algorithm might start with a codeword table. (A --> 0, B --> 1, C --> 2). This could result in a compressed sequence looking something like `01201201`. By allowing for codewords that can represent multiple symbols, the LWZ approach can achieve more efficient compression than traditional approaches. ## Algorithm * The algorithm starts with a simple codeword table where each codeword corresponds to a single symbol. * Whenever a codeword is used, a new codeword is created by concatenating the previous codeword with the next symbol. * The algorithm does not specify what happens when the codeword table becomes full, but there are many variants of the algorithm that handle this differently. * A neat fact about the LWZ approach is that it is possible to reconstruct the codeword table from the compressed bitstream alone, without needing to send the table along with the compressed data. * LWZ decompression [demo](https://docs.google.com/presentation/d/1U8XO6CWfcU4QgrFOZmGjAgmaKxLc8HXk6qB1JQVlqrg/edit#slide=id.g53705ba95_0259). ## Fun Facts * The algorithm is named after its inventors, Lempel, Ziv, and Welch. * The LWZ algorithm is used as a component in many compression tools, including .gif files, .zip files, and more. * The LWZ algorithm was once controversial due to attempts to enforce licensing fees, but the patent expired in 2003. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/38.-compression-and-complexity/38.6-lzw-compression.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `build a script that syncs our docs to a CMS` lets GitBook tailor the answer to that use case. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.