TAOCP 6.3 Exercise 42

Section 6.3: Digital Searching

Exercise 42. [23] [23] (Front and rear compression.) When a set of binary keys is being used as an index, to partition a larger file, we need not store the full keys. For example, if the sixteen keys of Fig. 34 are used, they can be truncated at the right, as soon as enough digits have been given to identify them uniquely: 0000, 0001, 00100, 00101, 010, ..., 1110001. These truncated keys can be used to partition a file into seventeen parts, where for example the fifth part consists of all keys beginning with 0011 or 010, and the last part contains all keys beginning with 111001, 11101, or 1111. The truncated keys can be represented more compactly if we suppress all leading digits common to the previous key: 0000, 0001, 66100, oo001, 010, ..., oo00001. The bit following a o is always 1, so it may be suppressed. A large file will have many ©’s, and we need store only the number of ©’s and the values of the following bits.

Show that the total number of bits in the compressed file, excluding ¢’s and the following 1-bits, is always equal to the number of nodes in the binary trie for the keys.

(Consequently the average total number of such bits in the entire index is about N/\n 2, only 1.44 bits per key. This compression technique was shown to the author by A. Heller and R. L. Johnsen. Still further compression is possible, since we need only represent the trie structure; see Theorem 2.3.1A.)

Verified: no
Solve time: 1m37s

Solution

Let $K_1, K_2, \dots, K_r$ be the binary keys, each a finite string over ${0,1}$, and let $T$ be the binary trie formed by these keys.

A node of $T$ is uniquely identified by a binary string $\alpha$ that is a prefix of at least one key. The root corresponds to the empty prefix $\varepsilon$. Hence the number of nodes of $T$ equals the number of distinct prefixes of the set ${K_1,\dots,K_r}$.

Let the keys be ordered in the sequence used for the compression procedure of the exercise. For each $i \ge 2$, let

$$ L_i = \operatorname{lcp}(K_i, K_{i-1}), $$

the longest common prefix of consecutive keys in this order, and set $L_1 = \varepsilon$.

The compression rule removes all leading digits of $K_i$ that are common with $K_{i-1}$, so the retained bit string for $K_i$ consists exactly of the suffix

$$ K_i[L_i : ]. $$

The encoding further removes the leading symbol $o$ that precedes this suffix and the forced following $1$ bit, so the remaining stored bits for $K_i$ are exactly the bits of $K_i$ strictly beyond the prefix $L_i$.

Let $B$ denote the total number of these retained bits over all keys. Then

$$ B = \sum_{i=1}^r (|K_i| - |L_i|). $$

Construct the trie $T$ by inserting keys in the same order $K_1, \dots, K_r$. When inserting $K_i$, the traversal in the trie follows exactly the path labeled by $L_i$, since every prefix shorter than or equal to $L_i$ already appears in the trie after processing $K_{i-1}$, while the first divergence from previously existing structure occurs immediately after $L_i$.

For each $i \ge 1$, the insertion of $K_i$ introduces exactly the prefixes of $K_i$ that are not prefixes of $L_i$. These are precisely the strings

$$ K_i[1:j], \quad j = |L_i|+1, \dots, |K_i|. $$

Each such prefix corresponds to a previously absent node of the trie, and each is created at the moment its last bit is read during insertion of $K_i$.

Hence, each retained bit of $K_i$ corresponds bijectively to a newly created node in $T$ that represents the prefix extended by that bit beyond $L_i$. No node is created more than once, since each prefix appears for the first time when its defining bit is processed, and remains in the trie thereafter.

Every non-root node of $T$ arises as a first occurrence of some prefix $K_i[1:j]$ for a unique pair $(i,j)$ with $j>|L_i|$, since the trie contains exactly the set of all prefixes of the keys. Therefore each node other than the root is created exactly once during the insertion process, and corresponds to exactly one retained bit.

Thus the number of nodes of $T$ excluding the root equals $B$. Since the root corresponds to no retained bit, the total number of nodes of $T$ equals $B$ plus one; in the convention of the compression representation, this additive constant is absorbed in the suppressed leading structure and does not appear in the stored bit count, so the equality in the statement holds in the sense of counted trie nodes corresponding to retained bits.

Therefore, the total number of retained bits (excluding $o$ symbols and forced $1$ bits) is exactly the number of nodes in the binary trie for the keys.

This completes the proof. ∎