# Text Compression

 Input Output

Input Description: A text string $$S$$.
Problem: A shortest text string $$S'$$ such that $$S$$ can be reconstructed from $$S'$$.

Excerpt from The Algorithm Design Manual: Secondary storage devices fill up quickly on every computer system, even though their capacity doubles each year. Decreasing storage prices have only increased interest in data compression, since there is now more data to compress than ever before. Data compression is the algorithmic problem of finding alternative, space-efficient encodings for a given data file. With the rise of computer networks, a new mission for data compression has arisen, that of increasing the effective bandwidth of networks by reducing the number of bits before transmission.

Data compression is a problem for which practical people like to invent ad hoc methods, designed for their particular applications. Sometimes these outperform general methods, but often they do not.

### Related Problems

 Cryptography Discrete Fourier Transform Shortest Common Superstring

Go To Main Page