> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/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/39.-compression-complexity-p-np/39.1-models-of-compression.md). # 39.1 Models of Compression ## Comparing Compression Algorithms In the last chapter, we saw many approaches to compression. This raises an interesting question: for a given bitstream, what is the best algorithm for compression? For example, consider compression the text of Moby Dick using different compression formats. In this case, `bzip2` yields the best compression.

Different compression formats applied to mobydick.txt

One might argue, however, that the best possible compression algorithm for `mobydick.txt` is simply as follows: 
D(B):
    if input == 0:
        return "Call me Ishamel. ...."
    else:
        return the text as is
Using this as our decompression function, we can condense all of Moby Dick into a single bit! However, there is a problem with this approach. If we include the code for the decompression algorithm as part of the compressed model (recall compression model 2 from the previous chapter), we see that Moby Dick is not compressed to one bit, but actually requires *more* bits than the original text! ## Decompression Algorithms Ultimately, the goal of a compresion algorithm is to find short sequences of bits that generate desired longer sequences of bits. Formally stated, our problem is as follows: * Given a sequence of bits `B`, find a shorter sequence `DA + C(B)` that produces `B` when fed into an interpreter. `DA` represents the bits for the decompression algorithm, while `C(B)` represents the compressed version of `B`.

Our compression model applied to mobydick.txt.

## Improving Compression Recall the `HugPlant` example from the previous chapter. Using Huffman encoding, we can achieve a compression ratio of 25%. However, using another algorithm we'll call `MysteryX` for now, we can compress `HugPlant.bmp` down to 29,432 bits! This achieves a 0.35% compression ratio. Out of the $$2^{8389594}$$ possible bistreams of length $$8,389,594$$, only one in $$2^{8360151}$$ can achieve such a compression ratio.

A mystery compression algorithm that outperforms Huffman encoding by a large margin.

What is `MysteryX`? Well, it's simply the Java code `HugPlant.java` written to generate the `.bmp` file! Going back to the model of self-extracting bits, we see the power of code and interpreters in compression. This leads us to two interesting questions: * **comprehensible compression:** given a target bitstream `B`, can we create an algorithm that outputs useful, readable Java code? * **optimal compression**: given a target bitstream `B`, can we find the *shortest* possible program that outputs this bitstream? --- # 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 current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook/39.-compression-complexity-p-np/39.1-models-of-compression.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. 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.