> For the complete documentation index, see [llms.txt](https://xiaoyang-liu.gitbook.io/programming-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiaoyang-liu.gitbook.io/programming-notes/computer-science/data-structures/compression.md).

# Compression

Compression Model #1: Algorithms Operating on Bits.

* Bitstream -> Algorithms Operating on Bits -> Compressed bits C
* Compressed bits C -> Decompression Algorithm -> Bitstream

A lossless compression algorithm require that no information is lost.

## Prefix Free Codes

English text is usually represented by sequences of characters, each 8 bits long. Use fewer than 8 bits for each letter: Have to decide which bit sequences should go with which letters.

Morse code creates ambiguity. Avoid ambiguity by making code prefix free. A prefix-free code is one in which no codeword is a prefix of any other.

Some prefix-free codes are better for some texts than others. It’d be useful to have a procedure that calculates the optimized code for a given text.

## Huffman Coding

### General Idea

Calculate relative frequencies.

* Assign each symbol to a node with weight = relative frequency.
* Take the two smallest nodes and merge them into a super node with weight equal to sum of weights.
* Repeat until everything is part of a tree.

### Data Structures

For encoding (bitstream to compressed bitstream):

* Array of BitSequence\[], to retrieve, can use character as index.
* HashMap. (Lookup in a hashmap consists of: Compute hashCode, mod by number of buckets, look in a linked list.)

Compared to HashMaps, Arrays are faster, but use more memory if some characters in the alphabet are unused.

For decoding (compressed bitstream back to bitstream):

* Tries. (Need to look up longest matching prefix.)

### Practice

Two possible philosophies for using Huffman Compression: 1. Build one corpus per input type. 2. For every possible input file, create a unique code just for that file. Send the code along with the compressed file.

* Approach 1 will result in suboptimal encoding.
* Approach 2 requires to use extra space for the codeword table in the compressed bitstream. (Use in real world.)

Given a file X.txt that prepares to compress into X.huf:

* Consider each b-bit symbol of X.txt, counting occurrences of each of the 2b possibilities, where b is the size of each symbol in bits.
* Use Huffman code construction algorithm to create a decoding trie and encoding map. Store this trie at the beginning of X.huf.
* Use encoding map to write codeword for each symbol of input into X.huf.

To decompress X.huf:

* Read in the decoding trie.
* Repeatedly use the decoding trie’s `longestPrefixOf` operation until all bits in X.hug have been converted back to their uncompressed form.

## Compression Theory

The big idea in Huffman Coding is representing common symbols with small numbers of bits.

General idea: Exploit redundancy and existing order inside the sequence.

Different compression algorithms achieve different compression ratios on different files.

There's no compression algorithm that can compress any bitstream by 50%.

* Argument 1: If true, it will be able to compress any bitstream down to a single bit. Interpreter would have to be able to do the following task for any output sequence.
* Argument 2: There are far fewer short bitstreams than long ones.

### Compression Model

Universal compression is impossible, but the following example implies that comparing compression algorithms could still be quite difficult.

Suppose there is a special purpose compression algorithm that simply hardcodes small bit sequences into large ones. Example, represent GameOfThronesSeason6-Razor1911-Rip-Episode1.mp4 as 010. To avoid this sort of trickery, the compression model should include the bits needed to encode the decompression algorithm itself.

Compression Model #2: Self-Extracting Bits

As a model for the decompression process, the algorithm and the compressed bitstream could be treated as a single sequence of bits. (Can think of the algorithm and compressed bitstream as an input to an interpreter.)