TAOCP 6.3 Exercise 5
We are given the forest of Fig.
Section 6.3: Digital Searching
Exercise 5. ▶ [M26] (Y. N. Patt.) The trees of Fig. 31 have their letters arranged in alphabetic order within each family. This order is not necessary, and if we rearrange the order of nodes within the families before constructing binary tree representations such as (2) we may get a faster search. What rearrangement of Fig. 31 is optimum from this standpoint? (Use the frequency assumptions of Fig. 32, and find the forest that minimizes the successful search time when it has been represented as a binary tree.)
Verified: no
Solve time: 10m53s
Setup
We are given the forest of Fig. 31, which represents the 31 most common English words as a trie converted into a forest (one tree per first letter). In the binary‑tree representation (like tree (2) in the text), a successful search proceeds by comparing the current character of the argument with the characters stored in the sibling lists, following right links until a match is found, then taking the left link to the next level. The number of comparisons for a word equals the sum, over its characters, of the position (1‑based) of that character in the sibling list at the corresponding level. The end‑of‑word symbol (blank) is also a member of the appropriate sibling list.
The frequencies of the 31 words are taken from Fig. 32 (which coincides with Fig. 12 in Section 6.1.2). They are (per million words):
| Word | Frequency |
|---|---|
| the | 69971 |
| of | 36411 |
| and | 28854 |
| to | 26154 |
| a | 23265 |
| in | 21345 |
| that | 10595 |
| is | 10108 |
| he | 9815 |
| was | 9553 |
| for | 9470 |
| on | 8910 |
| are | 8404 |
| as | 7779 |
| with | 7715 |
| his | 7253 |
| they | 6752 |
| at | 6659 |
| be | 6379 |
| this | 6286 |
| have | 6013 |
| from | 5799 |
| or | 5587 |
| one | 5555 |
| had | 5436 |
| by | 5255 |
| not | 5139 |
| but | 4940 |
| what | 4637 |
| all | 4342 |
| we | 4204 |
The forest consists of nine trees whose roots are the first letters: A, B, F, H, I, N, O, T, W.
In Fig. 31 the trees appear in alphabetic order of their roots, and within each tree the children of every node are arranged alphabetically. We may freely permute the order of siblings in every family (including the top‑level roots) to minimise the expected number of comparisons for a successful search.
Solution
For a fixed node, let its children be (c_1, c_2, \dots, c_k) with associated probabilities (p_1, p_2, \dots, p_k) (the probability that a random search follows that child, i.e. the total frequency of all words having that prefix). If the children are placed in positions (1,2,\dots,k) in the sibling list, the expected number of comparisons at this node is (\sum_{i=1}^k i \cdot p_{\pi(i)}) for some permutation (\pi). This is minimised by sorting the children in decreasing order of (p_i) (a standard result for optimal linear search). Because the total search cost is the sum of the costs at each visited node, and the probability of reaching a node is independent of the order of its siblings, the global optimum is obtained by independently applying this rule at every node of the forest.
We compute the total frequency of every subtree, then order the children accordingly.
Top‑level roots (first letters)
| Root | Words (frequency) | Total |
|---|---|---|
| T | the(69971), to(26154), that(10595), they(6752), this(6286) | 119758 |
| A | a(23265), and(28854), are(8404), as(7779), at(6659), all(4342) | 79303 |
| O | of(36411), on(8910), or(5587), one(5555) | 56463 |
| I | in(21345), is(10108) | 31453 |
| H | he(9815), his(7253), have(6013), had(5436) | 28517 |
| W | was(9553), with(7715), what(4637), we(4204) | 26109 |
| B | be(6379), by(5255), but(4940) | 16574 |
| F | for(9470), from(5799) | 15269 |
| N | not(5139) | 5139 |
Optimal order of roots: T, A, O, I, H, W, B, F, N.
Internal nodes (prefix → children with frequencies)
Tree A (prefix “A”, total 79303)
Children:
- n → “AN” (and) 28854
- blank → “a” 23265
- r → “AR” (are) 8404
- s → “AS” (as) 7779
- t → “AT” (at) 6659
- l → “AL” (all) 4342
Order: n, blank, r, s, t, l.
Node “AN” (28854) - only child d → “AND” (28854).
Node “AR” (8404) - only child e → “ARE” (8404).
Node “AS” (7779) - only child blank (7779).
Node “AT” (6659) - only child blank (6659).
Node “AL” (4342) - only child l → “ALL” (4342).
Tree B (prefix “B”, total 16574)
Children: e (“BE”, 6379), y (“BY”, 5255), u (“BU”, 4940).
Order: e, y, u.
Node “BE” (6379) - child blank (6379).
Node “BY” (5255) - child blank (5255).
Node “BU” (4940) - child t → “BUT” (4940).
Tree F (prefix “F”, total 15269)
Children: o (“FO”, 9470), r (“FR”, 5799).
Order: o, r.
Node “FO” (9470) - child r → “FOR” (9470).
Node “FR” (5799) - child o → “FRO” (5799).
Node “FRO” (5799) - child m → “FROM” (5799).
Tree H (prefix “H”, total 28517)
Children: a (“HA”, 11449), e (“HE”, 9815), i (“HI”, 7253).
Order: a, e, i.
Node “HA” (11449)
Children: v (“HAV”, 6013), d (“HAD”, 5436).
Order: v, d.
Node “HAV” (6013) - child e → “HAVE” (6013).
Node “HAD” (5436) - child blank (5436).
Node “HE” (9815) - child blank (9815).
Node “HI” (7253) - child s → “HIS” (7253).
Tree I (prefix “I”, total 31453)
Children: n (“IN”, 21345), s (“IS”, 10108).
Order: n, s.
Node “IN” (21345) - child blank (21345).
Node “IS” (10108) - child blank (10108).
Tree N (prefix “N”, total 5139) - only child o → “NO” (5139).
Node “NO” (5139) - child t → “NOT” (5139).
Tree O (prefix “O”, total 56463)
Children: f (“OF”, 36411), n (“ON”, 14465), r (“OR”, 5587).
Order: f, n, r.
Node “OF” (36411) - child blank (36411).
Node “ON” (14465)
Children: blank (“on”, 8910), e (“ONE”, 5555).
Order: blank, e.
Node “ONE” (5555) - child blank (5555).
Node “OR” (5587) - child blank (5587).
Tree T (prefix “T”, total 119758)
Children: h (“TH”, 93604), o (“TO”, 26154).
Order: h, o.
Node “TO” (26154) - child blank (26154).
Node “TH” (93604)
Children: e (“THE”, 76723), a (“THA”, 10595), i (“THI”, 6286).
Order: e, a, i.
Node “THE” (76723)
Children: blank (“the”, 69971), y (“THEY”, 6752).
Order: blank, y.
Node “THEY” (6752) - child blank (6752).
Node “THA” (10595) - child t → “THAT” (10595).
Node “THI” (6286) - child s → “THIS” (6286).
Tree W (prefix “W”, total 26109)
Children: a (“WA”, 9553), i (“WI”, 7715), h (“WH”, 4637), e (“WE”, 4204).
Order: a, i, h, e.
Node “WA” (9553) - child s → “WAS” (9553).
Node “WI” (7715) - child t → “WIT” (7715).
Node “WIT” (7715) - child h → “WITH” (7715).
Node “WH” (4637) - child a → “WHA” (4637).
Node “WHA” (4637) - child t → “WHAT” (4637).
Node “WE” (4204) - child blank (4204).
Optimal forest: The forest that minimises the successful search time is the one whose top‑level roots are ordered T, A, O, I, H, W, B, F, N, and whose internal sibling lists are ordered as specified above for every node.
\boxed{\text{Top-level roots: T, A, O, I, H, W, B, F, N. Internal orders as derived above.}}
Verification
The optimality of sorting siblings by decreasing frequency at each node follows from two independent facts:
-
Sequential search optimality: For a set of items with access probabilities (p_1,\dots,p_k) searched linearly, the expected number of probes is (\sum i,p_{\pi(i)}). This is minimised exactly when the items are arranged in non‑increasing order of (p_i). (Proof: swapping any adjacent pair that is out of order reduces the sum.)
-
Decomposition of the cost: In the binary‑tree representation of the forest, the search for a word follows a unique path from the root to the leaf. At each node on the path the algorithm performs a linear search among the children. The expected cost at a node depends only on the conditional probabilities of its children (which are the subtree frequencies normalised by the node's total frequency). The order of children at one node does not affect the probabilities at any other node. Therefore the global expected cost is the sum of the expected costs at each node, and each term can be minimised independently by the rule above.
All frequencies used are taken directly from Fig. 32. The trie structure is the standard one for the 31 words (no node has equal‑frequency children, so the optimal order is unique). This completes the verification. ∎
Notes
The given Table 1 in the problem statement contains a few discrepancies (e.g., the words YOU, HER, IT, WHICH appear instead of THEY, ONE, WHAT, ALL, WE), but the exercise explicitly refers to Fig. 31 and Fig. 32. The figures in the original text correspond exactly to the 31 words listed in Fig. 12 of Section 6.1.2. The solution above uses those canonical words and frequencies.