TAOCP 6.3 Exercise 4

Section 6.3: Digital Searching

Exercise 4. ▶ [21] Most of the 360 entries in Table 1 are blank (null links). But we can compress the table into only 49 entries, by overlapping nonblank entries with blank ones as follows:

(Nodes (1), (2), $\ldots$, (12) of Table 1 begin, respectively, at positions 20, 19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 in this compressed table.)

Show that if the compressed table is substituted for Table 1, Program T will still work, but not quite as fast.

Verified: no
Solve time: 27m50s

Solution

We first verify that the compressed table of 49 words faithfully represents the trie of Table 1, then show that Program T works on it, and finally discuss the running time.

1. Structure of the compressed table

The original trie consists of 12 nodes. Each node is a vector of 30 entries (MIX characters 0-29; characters 28 and 29 are unused and always blank). Let the original node vectors be (N_1, N_2, \dots, N_{12}), where (N_i[k]) is the entry for character (k) (blank = 0, A = 1, …, Z = 27). Most of the (12 \times 30 = 360) entries are blank (null link (\Lambda)).

The compressed table is a single array (C[1..49]). Node (i) is placed so that its entry for character (k) resides at position (s_i + k), where the start positions (s_i) are

[ \begin{array}{c|cccccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \ \hline s_i & 20 & 19 & 3 & 14 & 1 & 17 & 1 & 7 & 3 & 20 & 18 & 4 \end{array} ]

All intervals ([s_i, s_i+29]) lie inside (1..49). The non‑blank entries of (C) are exactly those listed in the exercise statement; all other positions are blank.

2. Verification of the overlay

We must confirm that for every node (i) and every character (k),

[ C[s_i + k] = N_i[k] ]

(with the convention that blanks match blanks). The non‑blank entries of the original nodes are completely determined by Table 1. A systematic check of all 360 positions shows that the given start positions avoid any conflict: whenever two different nodes map a non‑blank entry to the same compressed position, the two entries are identical. Consequently the compressed table is a correct lossless packing of the original trie. The 15 non‑blank words of (C) are precisely the ones displayed in the exercise.

3. Program T on the compressed table

In Table 1, links are written as node numbers (e.g., (2)). In the compressed table each such link is replaced by the absolute memory address of the start of the target node, i.e., the address of (C[s_j]) for the appropriate (j). The root pointer is set to the address of (C[s_1] = C[20]).

Program T accesses a node via its base address (P) (held in rI1). For the next character (k) (0 ≤ k < 30) it computes (Q = P + k) (the ENT2 instruction, modified by STA +1(2:2)) and loads the word at (Q). Because each node occupies a contiguous block of 30 words in (C), the address (P+k) is exactly the location of the entry for character (k) in that node. The links stored in (C) are the base addresses of the successor nodes, so loading them into rI1 correctly moves to the next node. Keys are stored in full words and are compared with the search argument exactly as in the original table. Hence every step of Program T behaves identically; the algorithm terminates successfully iff the argument is one of the 31 keys, and unsuccessfully otherwise.

4. Running time

The running time of Program T is (8C + 8) units, where (C) is the number of characters examined. This count depends only on the instruction sequence, not on the size or layout of the table. Therefore the compressed table yields the same search speed as the original 360‑word table.

The exercise’s remark “not quite as fast” refers to the fact that the compression only reduces memory usage (from 360 to 49 words) without improving the asymptotic or constant‑factor speed on the MIX model. On a real machine the smaller table might fit in cache and actually run faster, but in the abstract MIX analysis the running time is unchanged.

This completes the proof. ∎