ConceptDBISAI-written · not yet proofread

Zipf's Law

Also Zipf

Zipf's law is the empirical observation that the frequency F_n of the n-th most frequent word of a text collection follows a power law F_n = C · n^(−α), i.e. a falling straight line in a log-log plot.

Formula#

Taking logarithms on both sides:

F_n = C \cdot n^{-\alpha} \iff \log F_n = -\alpha \cdot \log n + \log C.

ProofStraight line in the log-log plot (exam WS 21/22, Task 2.1)

In the plain plot, $x = n$ and $y = F_n = C / x^\alpha$ . Then $\log y = \log(C / x^\alpha) = -\alpha \log x + \log C$ . With $X = \log x$ on the x-axis and $Y = \log y$ on the y-axis this is $Y = -\alpha X + \log C$ : a straight line with slope $-\alpha < 0$ and intercept $\log C$ . $\blacksquare$

Fitting $C$ and $\alpha$ when the law holds exactly (frequencies sorted descending, $F_1 \ge F_2 \ge \dots$ ):

$F_1 = C \cdot 1^{-\alpha} = C$ , so $C = F_1$ .
$F_2 = C \cdot 2^{-\alpha}$ , so $\alpha = -\log_2 (F_2 / C) = \log_2 (F_1 / F_2)$ .
Check $F_n = C \cdot n^{-\alpha}$ for $n \ge 3$ .

Properties#

In the plain plot ( $n$ against $F_n$ ) the curve looks like a hyperbola: there are only a few very frequent words, and most words are rare (long tail).
Frequency here is the collection frequency (sum of the term frequencies over all documents), not the document frequency $\mathrm{df}$ .
One way to estimate the number of web pages is based on Zipf’s law (DBIS_VL01 > Keyword Search: Problem and Naive Solution).

Example#

ExampleExam WS 23/24, Task 1.1

$D_1$ = b c a c d c, $D_2$ = b c a c d c b c, $D_3$ = a d a c c b, $D_4$ = c a a c c. Frequencies over all documents: c: $3 + 4 + 2 + 3 = 12$ , a: $1 + 1 + 2 + 2 = 6$ , b: $1 + 2 + 1 = 4$ , d: $1 + 1 + 1 = 3$ .

Rank $n$	Word	$F_n$	$12 / n$
1	c	12	12
2	a	6	6
3	b	4	4
4	d	3	3

$C = F_1 = 12$ , $\alpha = \log_2(12/6) = 1$ ; the law holds exactly with $F_n = 12/n$ .

Sources#

Slides 01, p. 22
DBIS_VL01 > Zipf’s Law
Exams: DBIS Exam WS1920 (not published) Task 1.1, DBIS Exam WS2122 (not published) Task 2.1, DBIS Exam WS2324 (not published) Task 1.1, DBIS Exam WS2324-2 (not published) Task 1.3 (1)

Connections

Mentioned in inline links6

List Intersection
The $O(\log m \cdot \sum_i |L_i|)$ bound comes from a min-heap holding the current head of each of the $m$ lists: each element is inserted and extracted once, at cost $O(\log m)$ each. Ordering by length pays off because of Zipf’s Law: a f… §
Term Frequency
Summing $\mathrm{tf}(w, D)$ over all documents gives the total frequency of $w$ in the collection, the $F_n$ of Zipf’s Law. §
VL01 – Introduction, Inverted Index, Zipf's Law
The lecture outlines the course (indexing, ranking, databases, knowledge graphs, error-tolerant search, web apps, embeddings, vector databases and RAG) and its organisation. Its technical part solves keyword search: instead of scanning all… §
One way to estimate the number of web pages is based on Zipf’s Law (see the last section). §
Encodings and Compression
Where the numbers come from. The sorted document IDs of an inverted list are large, but their differences are small, especially in the long lists of frequent words (Zipf’s law: a few words account for most occurrences). Gap Encoding turns… §
Inverted Index and Ranking
Keyword search is answered by an Inverted Index: each word maps to the sorted list of documents containing it, and multi-keyword queries intersect (AND) or merge (OR) these lists. To rank the hits, each posting carries a score for how much… §
Zipf’s Law — word frequencies follow $F_n = C \cdot n^{-\alpha}$ ; few very long lists, many short ones §
List Intersection and Search
More than two lists. Intersect pairwise, shortest lists first, so the intermediate results stay short; by Zipf’s Law list lengths vary enormously. Alternatively a $k$ -way intersect/merge with a priority queue in… §

Search in these mentions →