TAOCP 6.3 Exercise 3

Let each key $x$ in the set of 31 words have frequency $f(x)$ as given by Fig.

taocpmathematicsalgorithmsvolume-3medium

Section 6.3: Digital Searching

Exercise 3. [21] [21] Design an algorithm for the deletion of a key from an M-ary trie, using the conventions of Algorithm T.

» 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:

LN] OD] SPD OLR] WO! RDILO; AI NM] A] wW]/ OLR] WO! A Ol/aIN|] MO) ] 109

Position ASSIS] aI SAI AI RAININININININ bs 5] x| v2

S n| =a] lala) a) 4a Q A) AN a

a aD al ee) oA) oy ale o/a fea] aSInil~wm| ols

Entry a B/B/Clojas/e}m| Ss] s/e S|) G) HH] H] 4] G]O/S) a]

Positi OLE] DI DIOL AIA MI FPO] OLE DIDI OlSAIANIM/MPSloses/a!oa OSitiON |N} AN] A] AN] | od] 69] od] om] od | os} oof a5 | os | SY Se] Se] SE] Se] SY] SY I SS

= ea) B|~ fax} O;ale|A~) ae] 4

~~ “A, ~| |E/A |p 5 S|>|2) 2/2) SiC Gl alanlelale = 8 Entry |Z BRS a alae Sells] S/FlAlSlafl) |aziS) |=

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

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

  1. [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: yes
Solve time: 1m40s

Solution

Let each key $x$ in the set of 31 words have frequency $f(x)$ as given by Fig. 32. For any node $v$ in the forest of Fig. 31, let $S(v)$ denote the set of keys whose search path passes through $v$, and define the subtree weight

$$ w(v)=\sum_{x\in S(v)} f(x). $$

In the binary representation described in the text, each node with children is implemented by a chain of sibling nodes linked by RLINK pointers. A search among the children of a node $v$ proceeds by comparing the argument character with the key at each sibling in order until a match is found. If the siblings of $v$ are ordered as $c_1,c_2,\dots,c_m$, then a key routed through child $c_i$ requires exactly $i$ comparisons at this level.

Let $p_i$ denote the probability that a search at node $v$ proceeds into child $c_i$, so $p_i = w(c_i)/w(v)$. The expected number of comparisons contributed by node $v$ equals

$$ E(v)=\sum_{i=1}^m i,p_i. $$

Local optimality condition

Fix the multiset ${p_1,\dots,p_m}$. Consider two adjacent children $c_i,c_{i+1}$ with probabilities $p_i$ and $p_{i+1}$. Their contribution to $E(v)$ is

$$ i p_i + (i+1)p_{i+1}. $$

If they are swapped, the contribution becomes

$$ i p_{i+1} + (i+1)p_i. $$

The difference between the original and swapped costs equals

$$ (i p_i + (i+1)p_{i+1}) - (i p_{i+1} + (i+1)p_i) = p_{i+1} - p_i. $$

If $p_i < p_{i+1}$, the swap strictly decreases $E(v)$. If $p_i > p_{i+1}$, swapping increases $E(v)$.

Repeated application of such exchanges yields a nonincreasing order

$$ p_1 \ge p_2 \ge \cdots \ge p_m, $$

and no further adjacent exchange can reduce $E(v)$. Hence this ordering minimizes $E(v)$ for fixed probabilities.

Global optimality

The total successful search cost of the forest equals the sum of $E(v)$ over all nodes $v$ on the access paths of the keys, weighted by their frequencies. Since each node contributes independently to the total cost and the ordering choices at distinct nodes affect disjoint sets of comparisons, minimizing each $E(v)$ independently minimizes the total cost.

Therefore, an optimal rearrangement of the forest is obtained by ordering, at every node, its outgoing branches in nonincreasing order of subtree weight $w(c)$.

Interpretation for Fig. 31

At the root, each first-letter group (A, B, D, E, F, H, N, O, R, S, T, U, V, W, Y) must be ordered by the total frequency of words beginning with that letter. Within each such group, the second-level branches are ordered by the total frequency of the corresponding two-letter prefixes, and so on recursively.

Conclusion

The optimal rearrangement of Fig. 31 is obtained by replacing the alphabetic ordering within every sibling list by ordering in decreasing subtree frequency, where subtree frequency is computed from Fig. 32. This ordering minimizes the expected number of successful comparisons in the binary (RLINK/LLINK) representation of the forest.

This completes the proof. ∎