The dictionary of Reuters-21578 holds 29,187 terms, and that of the Reuters RCV1 collection about 400,000. Every query consults the dictionary, once for each of its terms, before any postings list is read. Stored in the obvious way, as an array of fixed-size entries, the RCV1 dictionary takes 11.2 megabytes. How small can the dictionary be made without losing anything? About half that size: three changes of layout bring it to about 5.9 megabytes (Manning, Raghavan, and Schütze, 2008, §5.2).
The dictionary is the smaller of the two structures of an inverted index, and compressing it is a matter of layout, not of codes. This article covers it, and Index Compression, the next article, covers the postings. The compression here is lossless: every term, frequency and pointer can be recovered exactly. That article's first section sets lossless compression against the lossy kind that text processing applies.
Here is the route, following Manning, Raghavan, and Schütze (2008, §5.2). First we shrink the RCV1 dictionary in four layouts: fixed-width entries, the dictionary as a string, blocked storage, and front coding. Then we repeat the same steps on the Reuters-21578 vocabulary, where every byte can be counted, and decode a front-coded block. A worked problem takes up the choice of block size.
Compressing the dictionary
The dictionary is small compared with the postings, but it should stay in memory, since every query consults it. The RCV1 dictionary has about 400,000 terms. Four layouts shrink it in turn.
Fixed-width entries. The simplest layout is an array of fixed-size entries. Each has 20 bytes for the term, 4 bytes for its document frequency, and 4 bytes for a pointer to its postings list. At 28 bytes per entry, the dictionary needs $400{,}000 \times 28 = 11.2$ megabytes. Most of that is wasted. The average English term is about 8 characters long, while the 20-byte field must fit the longest terms, and still cannot fit some.
Dictionary as a string. Store all the terms, sorted, in one long string, and give each array entry a pointer into that string instead of the term itself. A pointer to one of about 3.2 million character positions needs 3 bytes. Each entry now needs:
- 4 bytes for frequency;
- 4 for the postings pointer;
- 3 for the term pointer;
- an average of 8 characters in the string.
That is a total of 19 bytes, or $400{,}000 \times 19 = 7.6$ megabytes.
Blocking. Group the terms into blocks of $k$ and keep a string pointer only for the first term of each block. Each term's length is then stored as a single byte before it in the string. With $k = 4$, each block saves three 3-byte pointers (9 bytes) and adds four 1-byte lengths (4 bytes), a net saving of 5 bytes per four terms. That removes $400{,}000 / 4 \times 5 = 500{,}000$ bytes, bringing the dictionary to 7.1 megabytes. The cost is lookup speed. Binary search finds the right block, and then the terms within the block are scanned in sequence.
Front coding. Sorted terms share prefixes with their neighbors, so within a block the shared prefix can be written once. With blocking alone, the four terms automata, automate, automatic, and automation are stored as
8automata8automate9automatic10automation
which is 40 characters as printed, and 39 bytes as stored, since each length is one byte. With front coding, the common prefix automat is written once, followed by each term's remaining characters:
8automat*a1◊e2◊ic3◊ion
Here 8automat*a gives the first term, of length 8, with * marking the end of the shared prefix automat. Each later term is then given by the number of extra characters, a ◊, and those characters: 1◊e is automate, 2◊ic is automatic, and 3◊ion is automation. In this notation the block shrinks from 40 printed characters to 22. Counted in bytes, with one byte for each length and for the length of the shared prefix as in the next section, it shrinks from 39 bytes to 19. Front coding brings the RCV1 dictionary to about 5.9 megabytes (Manning, Raghavan, and Schütze, 2008, §5.2).
The four layouts on RCV1, side by side:
| Structure | Method | RCV1 size |
|---|---|---|
| Dictionary | Fixed-width entries | 11.2 MB |
| Dictionary as a string | 7.6 MB | |
| String with blocking, $k = 4$ | 7.1 MB | |
| Blocking and front coding | 5.9 MB |
The first three dictionary sizes are computed in this article. The front-coding size is the one reported by Manning, Raghavan, and Schütze (2008, §5.2).
The same steps on a real dictionary
Do these savings hold on a dictionary we can inspect? They do. Reuters-21578 (Lewis, 1997) has 29,187 distinct terms when its text is lowercased and split into runs of letters, as in the term statistics article. Their average length is 6.99 characters, and together they take 203,992 characters. A pointer into a string of that length needs $\lceil \log_2 203{,}992 \rceil = 18$ bits, so 3 bytes, as for RCV1. Each layout's size is the sum of its parts:
| Layout | Bytes per term (or block) | Total |
|---|---|---|
| Fixed width | 20 + 4 + 4 = 28 | 817.2 kB |
| Dictionary as a string | 4 + 4 + 3 + 6.99 = 17.99 | 525.0 kB |
| Blocking, $k = 4$ | 4 + 4 + 1 length byte + 6.99, plus 3 per block | 488.6 kB |
| Blocking and front coding, $k = 4$ | as above, minus each block's repeated prefixes | 422.5 kB |
(Kilobytes are thousands of bytes, rounded to one decimal.) The fixed-width layout fails in the other direction too: four of the terms are longer than 20 characters and would not fit.
The front-coded size counts three things for each block. There is one byte for the length of the shared prefix, then the first term in full with its length byte, and then each later term as a length byte plus the characters after the shared prefix. A real block shows where the savings come from. The four consecutive terms computer, computerised, computerization, and computerized share the prefix computer. Blocked, they take $9 + 13 + 16 + 13 = 51$ bytes. Front coded, in the textbook's notation,
8computer*4◊ised7◊ization4◊ized
they take 28 bytes: 1 for the prefix length, 9 for the first term, and $5 + 8 + 5$ for the other three.
Example (decoding a front-coded block). The block 8computer*4◊ised7◊ization4◊ized decodes to computer, computerised, computerization, computerized. The leading 8 says the first term has eight characters, and the * after computer says all eight belong to the shared prefix. 4◊ised then says: four more characters, ised, appended to the prefix, giving computerised. 7◊ization gives computerization and 4◊ized gives computerized. In the textbook's block, 8automat*a1◊e2◊ic3◊ion, the * comes one character before the end of the first term: the prefix is automat and the first term is automata. A lookup that lands in this block must rebuild each term in turn until it finds the one it wants, which is the scan that blocking already required.
Larger blocks save more pointer bytes but make lookups scan further. On this dictionary, blocks of 8 bring the front-coded size to 412.1 kB. Blocks of 16 give 412.3 kB, slightly larger, because the common prefix of sixteen consecutive terms is usually shorter than that of four.
Worked problems
The problem is an exercise from chapter 5 of the course text (Manning, Raghavan, and Schütze, 2008), restated here with its data and solved in our own words. The script tools/experiments/indexing/dictionary_compression.py checks its arithmetic, every size in the tables above, and both front-coded blocks.
Problem 1 (Exercise 5.2 of the course text). Estimate the size of the RCV1 dictionary with blocked storage for blocks of $k = 8$ and $k = 16$ terms.
Solution. The sizes are 6.95 and 6.875 megabytes. Start from the dictionary as a string, 7.6 megabytes for 400,000 terms. A block of $k$ terms keeps one 3-byte string pointer instead of $k$, saving $3(k-1)$ bytes, and adds one length byte for each of its $k$ terms. The net saving per block is $3(k - 1) - k = 2k - 3$ bytes.
- For $k = 8$ the saving is 13 bytes per block, and there are $400{,}000/8 = 50{,}000$ blocks: $50{,}000 \times 13 = 650{,}000$ bytes. The dictionary takes $7.6 - 0.65 = 6.95$ megabytes.
- For $k = 16$ the saving is 29 bytes per block over $25{,}000$ blocks: $725{,}000$ bytes, leaving $7.6 - 0.725 = 6.875$ megabytes.
The same formula gives the article's $k = 4$: 5 bytes over 100,000 blocks, 7.1 megabytes. Each doubling of $k$ saves less than the one before, 0.15 and then 0.075 megabytes, while the scan inside a block doubles. The saving per term, $(2k-3)/k$, can never reach 2 bytes.
What we have learned
The dictionary shrinks by storing terms as one string, in blocks, with shared prefixes written once: 817.2 kB to 422.5 kB on the Reuters vocabulary, and 11.2 megabytes to about 5.9 for RCV1. Each step trades a little lookup time for space, since a lookup must scan within a block and rebuild front-coded terms.
The dictionary was the small part of the index. The next article, Index Compression, turns to the postings, where the bytes are: it stores each postings list as gaps and encodes the gaps with variable-length codes.
References
- Lewis, D. D. (1997). Reuters-21578 text categorization test collection, distribution 1.0. record · 9 pages
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 5. Cambridge University Press. record · 93 pages