Optimal coding and the origins of Zipfian laws

Abstract

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.

in press in the Journal of Quantitative Linguistics; definition of concordant pair corrected, proofs polished, references updated

References in corpus (10)

• Power laws, Pareto distributions and Zipf's law
• Large-scale analysis of Zipf's law in English texts
• Zipf's law unzipped
• Compression as a universal principle of animal behavior
• Zipf's law, power laws, and maximum entropy
• The placement of the head that minimizes online memory: a complex systems approach
• The failure of the law of brevity in two New World primates. Statistical caveats
• Optimization models of natural communication
• The challenges of statistical patterns of language: the case of Menzerath's law in genomes
• The polysemy of the words that children learn over time

Cited by in corpus (5)

• Linguistic laws in biology
• Parallels of human language in the behavior of bottlenose dolphins
• The optimal placement of the head in the noun phrase. The case of demonstrative, numeral, adjective and noun
• On the class of coding optimality of human languages and the origins of Zipf's law
• The advent and fall of a vocabulary learning bias from communicative efficiency