Suffix deduplication stores identical word endings once instead of repeating them for every word. A trie already shares prefixes; a word graph can share common suffixes too, removing redundant leaves and repeated endings such as s, ed, and ing. section 5.2.4 section 5.5
The technique changes the structure and the construction rules:
- Deduplicating suffixes turns a prefix tree into a directed acyclic graph rather than a tree. section 5.4
- Equivalent nodes can share one continuation: several outgoing s edges may point to the same leaf, allowing redundant nodes to be deleted. section 5.2.4
- An incremental construction keeps the graph minimal for every earlier word while leaving only the newest word temporarily unoptimized; finalization minimizes that last path. section 5.4
- The described algorithm requires words in alphabetical ordinal order; handling arbitrary order requires a more complex variant. section 5.4
From a trie to a compact word graph
For car, care, cares, cars, fir, fire, firer, firers, and firs, shared suffixes collapse equivalent continuations. On the ENABLE list of 172,820 words, the resulting DAWG has 54,167 nodes instead of the trie's 387,881—86% fewer nodes and only 14% as many. The graph still costs more memory than a custom contiguous byte-array string list because its many node and dictionary objects carry overhead. section 5.4 section 5.5
Table 5.1 Comparison of nodes by outgoing edge count
| Outgoing edges |
Trie nodes |
DAWG nodes |
|---|---|---|
| 0 |
111,507 |
1 |
| 1 |
214,096 |
25,921 |
| 2 |
39,181 |
12,840 |
| 3 |
13,525 |
6,755 |
| 4 |
4,490 |
3,618 |
| 5 |
1,994 |
1,944 |
| 6–26 |
3,088 |
3,088 |
| Total nodes |
387,881 |
54,167 |
| Total edges |
387,880 |
122,975 |
Compare trie and DAWG node and edge counts by outgoing-edge category. section 5.5
