Heaps' law

Short description: Heuristic for distinct words in a document

Verification of Heaps' law on War and Peace, as well as a randomly shuffled version of it. Both cases fit well to the Heaps' law with very similar exponents β, but different K.

A schematic Heaps-law plot. The x-axis represents the text size, and the y-axis represents the number of distinct vocabulary elements present in the text. Compare the values of the two axes.

In linguistics, Heaps' law (also called Herdan's law) is an empirical law which describes the number of distinct words in a document (or set of documents) as a function of the document length (so called type-token relation). It can be formulated as

[math]\displaystyle{ V_R(n) = Kn^\beta }[/math]

where V_R is the number of distinct words in an instance text of size n. K and β are free parameters determined empirically. With English text corpora, typically K is between 10 and 100, and β is between 0.4 and 0.6.

The law is frequently attributed to Harold Stanley Heaps, but was originally discovered by Gustav Herdan (1960). Under mild assumptions, the Herdan–Heaps law is asymptotically equivalent to Zipf's law concerning the frequencies of individual words within a text. This is a consequence of the fact that the type-token relation (in general) of a homogenous text can be derived from the distribution of its types.

Empirically, Heaps' law is preserved even when the document is randomly shuffled, meaning that it does not depend on the ordering of words, but only the frequency of words. This is used as evidence for deriving Heaps' law from Zipf's law.

Heaps' law means that as more instance text is gathered, there will be diminishing returns in terms of discovery of the full vocabulary from which the distinct terms are drawn.

Deviations from Heaps' law, as typically observed in English text corpora, have been identified in corpora generated with large language models.

Heaps' law also applies to situations in which the "vocabulary" is just some set of distinct types which are attributes of some collection of objects. For example, the objects could be people, and the types could be country of origin of the person. If persons are selected randomly (that is, we are not selecting based on country of origin), then Heaps' law says we will quickly have representatives from most countries (in proportion to their population) but it will become increasingly difficult to cover the entire set of countries by continuing this method of sampling. Heaps' law has been observed also in single-cell transcriptomes considering genes as the distinct objects in the "vocabulary".

See also

• Zipf's law  – Probability distribution
• Brevity law
• Menzerath's law
• Bradford's law – Pattern of references in science journals
• Benford's law – Observation that in many real-life datasets, the leading digit is likely to be small
• Pareto distribution – Probability distribution
• Principle of least effort
• Rank-size distribution

References

Sources

• Baeza-Yates, Ricardo; Navarro, Gonzalo (2000), "Block addressing indices for approximate text retrieval", Journal of the American Society for Information Science 51 (1): 69–82, doi:10.1002/(sici)1097-4571(2000)51:1<69::aid-asi10>3.0.co;2-c .
• Egghe, L. (2007), "Untangling Herdan's law and Heaps' law: Mathematical and informetric arguments", Journal of the American Society for Information Science and Technology 58 (5): 702–709, doi:10.1002/asi.20524 .
• Heaps, Harold Stanley (1978), Information Retrieval: Computational and Theoretical Aspects, Academic Press . Heaps' law is proposed in Section 7.5 (pp. 206–208).
• Herdan, Gustav (1960), Type-token mathematics, The Hague: Mouton .
• Kornai, Andras (1999), "Zipf's law outside the middle range", in Rogers, James, Proceedings of the Sixth Meeting on Mathematics of Language, University of Central Florida, pp. 347–356 .
• Milička, Jiří (2009), "Type-token & Hapax-token Relation: A Combinatorial Model", Glottotheory. International Journal of Theoretical Linguistics 1 (2): 99–110, doi:10.1515/glot-2009-0009 .
• van Leijenhorst, D. C; van der Weide, Th. P. (2005), "A formal derivation of Heaps' Law", Information Sciences 170 (2–4): 263–272, doi:10.1016/j.ins.2004.03.006 .