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

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FO7UqH9ubjgskBevPScdz%2Fimage.png?alt=media&amp;token=3e947dc1-ed7b-4403-a5b2-7dcc1c672412" alt=""><figcaption><p>Different compression formats applied to <code>mobydick.txt</code></p></figcaption></figure>

One might argue, however, that the best possible compression algorithm for `mobydick.txt` is simply as follows:

<pre><code>D(B):
<strong>    if input == 0:
</strong>        return "Call me Ishamel. ...."
    else:
        return the text as is
</code></pre>

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

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FMCYkJqoXfJQjA9H4QEtj%2Fimage.png?alt=media&amp;token=8a2f85f6-19f2-410b-a7c4-57ff339cd5c2" alt=""><figcaption><p>Our compression model applied to <code>mobydick.txt</code>.</p></figcaption></figure>

## Improving Compression

Recall the `HugPlant` example from the previous chapter. Using Huffman encoding, we can achieve a compression ratio of 25%.&#x20;

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.

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FhQU7fNItG1XxGIxo6VRl%2Fimage.png?alt=media&amp;token=42238a0b-5344-4478-8f31-00b7716240c0" alt=""><figcaption><p>A mystery compression algorithm that outperforms Huffman encoding by a large margin.</p></figcaption></figure>

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?