Seminar 3
Algorithm 1 (Variable byte code) A number 𝑛 is encoded in variable byte code in the
following procedure:
1. Take a binary representation of 𝑛 with padding to the length of a multiple of 7.
2. Split into of 7 bit blocks right-to-left.
3. Add 1 to the beginning of the last block and 0 to the beginning of all previous blocks.
Example: 𝑉 𝐵(824) = 00000110 10111000
Definition 1 (Unary code) Unary code, also referred to as 𝛼 code, is a coding type where
a number 𝑛 is represented by a sequence of 𝑛 1s (or 0s) and terminated with one 0 (or
1). That is, 6 in unary code is 1111110 (or 0000001). The alternative representation in
parentheses is equivalent but for this course we use the default representation.
Definition 2 (𝛾 code) 𝛾 code is a coding type, that consists of an offset and its length:
𝛾(𝑛) = length of offset(𝑛) in 𝛼,offset(𝑛). Offset is a binary representation of a number 𝑛
without the highest bit (1). Length of this offset encoded in the unary (𝛼) code. Then the
number 60 is encoded in 𝛾 as 111110,11100.
Definition 3 (𝛿 code) A number 𝑛 is encoded in 𝛿 code in the following way. First
calculate the offset of 𝑛 and the length of 𝑛 encode with 𝛾 code. Then add the offset of 𝑛.
The final form is 𝛿(𝑛) = length of offset(𝑛) in 𝛾,offset(𝑛). Analogously, 600 is encoded in 𝛿
as 1110,001,001011000.
Definition 4 (Zipf’s law) Zipf’s law says that the 𝑖-th most frequent term has the frequency
1
𝑖 . In this exercise we use the dependence of the Zipf’s law 𝑐𝑓𝑖 ∝ 1
𝑖 = 𝑐𝑖 𝑘
where 𝑐𝑓𝑖 is the
number of terms 𝑡𝑖 in a given collection with 𝑘 = −1.
Definition 5 (Heaps’ law) Heaps’ law expresses an empiric dependency of collection size
(number of all words) 𝑇 and vocabulary size (number of distinct words) 𝑀 by 𝑀 = 𝑘𝑇 𝑏
where 30 ≤ 𝑘 ≤ 100 and 𝑏 ≈ 1
2 .
Exercise 1
Count variable byte code for the postings list ⟨777, 17 743, 294 068, 31 251 336⟩. Bear in mind
that the gaps are encoded. Write in 8-bit blocks.
Encode the list of gaps ⟨777, 16 966, 276 325, 30 957 268⟩. Variable byte code of the gaps:
∙ 𝑉 𝐵(777) = 00000110 10001001
∙ 𝑉 𝐵(16 966) = 00000001 00000100 11000110
∙ 𝑉 𝐵(276 325) = 00010000 01101110 11100101
∙ 𝑉 𝐵(30 957 268) = 00001110 01100001 00111101 11010100
Result: 𝑉 𝐵(⟨777, 17 743, 294 068, 31 251 336⟩) = 00000110 10001001 00000001 00000100 11000110 00010000
01101110 11100101 00001110 01100001 00111101 11010100
1
Exercise 2
Count 𝛾 and 𝛿 codes for the numbers 63 and 1023.
According to the definition 2 it is necessary to count the offsets as binary representations
without the highest bit 6310 = 1111112 and offset(63) = 11111. Offset length is encoded
in 𝛼 as |11111| = 5 𝛼(5) = 111110. Finally, 𝛾(63) = 111110, 11111. Analogically for
1023. 102310 = 11111111112, offset is 111111111, its length is |111111111| = 9 𝛼(9) =
1111111110. Then 𝛾(1023) = 1111111110, 111111111.
𝛿 is a little more complicated. First we count the offset 63 = 11111 and its length
|11111| = 5. The value of 5 we encode in 𝛾 so 𝛾(5) = 110, 01. By definition 3 we have
𝛿(63) = 110, 01, 11111. And finally, 𝛿(1023) = 1110, 010, 111111111.
Exercise 3
A collection of documents contains 4 words: one, two, three, four of decreasing word
frequencies 𝑓1, 𝑓2, 𝑓3 and 𝑓4. The total number of tokens in the collection is 5000. Assume
that the Zipf’s law holds for this collection perfectly. What are the word frequencies?
We use the Zipf’s law in Definition 4. The least frequent term is four, then three, two and
the most frequent is one. Applying the Zipf’s law we get
𝑐𝑓1 + 𝑐𝑓2 + 𝑐𝑓3 + 𝑐𝑓4 = 5000
𝑐 · 1−1
+ 𝑐 · 2−1
+ 𝑐 · 3−1
+ 𝑐 · 4−1
= 5000
𝑐 + 1
2 𝑐 + 1
3 𝑐 + 1
4 𝑐 = 5000
12𝑐 + 6𝑐 + 4𝑐 + 3𝑐 = 60000
25𝑐 = 60000
𝑐 = 2400
and, plugging in to the formula 𝑐𝑓𝑖 = 𝑐𝑖−1
, we obtain the term frequency values:
𝑐𝑓1 = 24001
1 = 2400
𝑐𝑓2 = 24001
2 = 1200
𝑐𝑓3 = 24001
3 = 800
𝑐𝑓4 = 24001
4 = 600
Exercise 4
How many distinct terms are expected in a document of 1,000,000 tokens? Use the Heaps’
law with parameters 𝑘 = 44 and 𝑏 = 0.5
By Definition 5,
44 × 1,000,0000.5
= 44,000.
2