# Optimal coding and the origins of Zipfian laws

arXiv: https://arxiv.org/abs/1906.01545 · HTML: https://mlsanity.com/paper/1906.01545/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2019.

## Built on by (most cited first, 10 of 10)

- [How (Non-)Optimal is the Lexicon?](https://mlsanity.com/paper/2104.14279/) (2021)
- [Linguistic laws in biology](https://mlsanity.com/paper/2310.07387/) (2023)
- [The optimal placement of the head in the noun phrase. The case of demonstrative, numeral, adjective and noun](https://mlsanity.com/paper/2402.10311/) (2024)
- [Direct and indirect evidence of compression of word lengths. Zipf's law of abbreviation revisited](https://mlsanity.com/paper/2303.10128/) (2023)
- [The advent and fall of a vocabulary learning bias from communicative efficiency](https://mlsanity.com/paper/2105.11519/) (2021)
- [The optimality of word lengths. Theoretical foundations and an empirical study](https://mlsanity.com/paper/2208.10384/) (2022)
- [Multiple evolutionary pressures shape identical consonant avoidance in the world's languages](https://mlsanity.com/paper/2309.14006/) (2023)
- [How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization](https://mlsanity.com/paper/2604.01938/) (2026)
- [Dependency distance minimization predicts compression](https://mlsanity.com/paper/2109.08900/) (2021)
- [Principles of semantic and functional efficiency in grammatical patterning](https://mlsanity.com/paper/2410.15865/) (2024)

## Abstract (arXiv)

The problem of compression in standard information theory consists of assigning codes as short as possible to numbers. Here we consider the problem of optimal coding -- under an arbitrary coding scheme -- and show that it predicts Zipf's law of abbreviation, namely a tendency in natural languages for more frequent words to be shorter. We apply this result to investigate optimal coding also under so-called non-singular coding, a scheme where unique segmentation is not warranted but codes stand for a distinct number. Optimal non-singular coding predicts that the length of a word should grow approximately as the logarithm of its frequency rank, which is again consistent with Zipf's law of abbreviation. Optimal non-singular coding in combination with the maximum entropy principle also predicts Zipf's rank-frequency distribution. Furthermore, our findings on optimal non-singular coding challenge common beliefs about random typing. It turns out that random typing is in fact an optimal coding process, in stark contrast with the common assumption that it is detached from cost cutting considerations. Finally, we discuss the implications of optimal coding for the construction of a compact theory of Zipfian laws and other linguistic laws.