> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/compression.md).

# compression

## Basic idea

Encoding data with fewer bits by exploiting statistical structure. Lossless compression is bounded below by Shannon entropy; lossy compression trades fidelity for size.

## Key formulas

* Shannon source-coding bound: $\bar L \ge H(X)$
* Kraft inequality: $\sum\_i 2^{-l\_i} \le 1$
* Shannon entropy: $H(X) = -\sum\_i p\_i \log\_2 p\_i$