Chapter 5: What’s up with you, Directed Acyclic Word Graph?

Introduction

This chapter introduces the problem of storing and quickly searching large word lists, and previews a progression from sorted lists to tries and DAWGs.

• Word-list search requirements: Describe the practical word-list problems motivating the chapter, including finding words for Scrabble-like games and supporting typing completion, and state that the desired structure must search quickly without using excessive memory.
  Why it matters: These requirements provide the criteria for comparing the word-list data structures that follow.
• Word-list representation progression: Trace the chapter's planned progression from a sorted word list, through deduplicating shared prefixes with a prefix tree or trie, to deduplicating suffixes as well with a Directed Acyclic Word Graph (DAWG).
  Why it matters: The progression explains why the chapter moves from straightforward storage toward increasingly compressed word graphs.
• Automata theory connection: State that the chapter will connect DAWGs and the word-list problem to finite state machines or finite state automata.
  Why it matters: This connection supplies another way to understand the graph-based representation of a word list.

Key terms: word list, typing completion, word games, prefix, memory, sorted list, prefix tree, trie, Directed Acyclic Word Graph, DAWG

5.1 Two problems, two weak solutions

This section defines the word-list search and prefix-completion problems, their required interface operations, scope, and performance notation for comparing solutions.

• Word-list query operations: Describe the three operations required of the word-list ADT: enumerating its strings, testing whether it contains a given word, and enumerating every word that begins with a specified prefix.
  Why it matters: These operations are the criteria used to evaluate hash sets, sorted lists, tries, and DAWGs in the rest of the chapter.
• Autocomplete response requirement: Explain why prefix enumeration must be fast for autocomplete, including that users type quickly and the example C# IDE completion budget was 30 milliseconds, roughly a screen-refresh time.
  Why it matters: The responsiveness requirement explains why a merely workable representation may not be good enough for prefix completion.
• Representation scope and notation: State that the chapter considers efficiently searching an already existing word list, not dynamically adding or removing items while preserving search performance; describe n as the number of words and m as word length, with maximum versus average length determined by context.
  Why it matters: This scope and notation keep the chapter's performance comparisons focused on static word-list searching.

Key terms: abstract data type, word list, enumerable sequence of strings, contained, prefix, autocompletion, IntelliSense completions, 30 milliseconds, n, m

5.1.1 Hash sets are a nonsolution

This subsection rejects hash sets for a word list because they make exact membership fast but cannot efficiently answer prefix queries.

• Hash-set membership performance: Explain why a HashSet<string> can implement Contains in O(m) time, where m is the string length rather than the number of stored words.
  Why it matters: This establishes the useful operation that makes hash sets attractive before exposing why they still fail this problem.
• Hash sets and prefix search: Explain why a hash set is unsuitable for StartsWith: a well-designed hash function deliberately distributes similar words across different buckets, so words sharing a prefix cannot be located efficiently.
  Why it matters: The inability to support efficient prefix lookup is the reason this representation is rejected for the word-list problem.

Key terms: HashSet<string>, Contains, hash code, buckets, O(m), StartsWith, hashing algorithm

5.1.2 Sorted lists are… fine?

This section evaluates a sorted List<string> as a word-list representation, explaining its binary-search operations, time costs, and substantial memory overhead.

• Sorted-list word lookup: Describe how a sorted List<string> implements Contains and StartsWith using BinarySearch. Explain how StartsWith identifies its starting position and then scans consecutive matching words.
  Why it matters: A sorted list is a practical baseline for judging why a prefix tree may be worthwhile.
• Prefix-search time costs: Explain the time cost of searching the sorted list when typical words and prefixes have length m. Distinguish the O(m log n) binary-search cost from the additional O(m) work for each StartsWith match, which can involve as many as n matches.
  Why it matters: The potentially expensive scan over many prefix matches motivates a data structure designed around shared prefixes.
• String-list memory overhead: Describe why storing ENABLE as a List<string> takes roughly 8 MB despite its character data using only about 3 MB. State how UTF-8-style one-byte characters and a single byte array indexed by 4-byte integers could reduce the representation to roughly 2.5 MB, while avoiding many separate garbage-collected string objects.
  Why it matters: Memory layout and object overhead can matter as much as asymptotic complexity when choosing a word-list representation.

Key terms: List<string>, sorted list, BinarySearch, Contains, StartsWith, bitwise complement, O(m log n), O(log n), string comparison, string.StartsWith

5.2 The prefix tree

This section motivates prefix trees (tries) as a way to deduplicate shared word prefixes and introduces how a trie represents words visually.

• Prefix-sharing motivation: Explain why a word list with many words and a small alphabet benefits from a prefix tree: repeated starting sequences can be stored once rather than copied in every word.
  Why it matters: Sharing common prefixes is the space-saving idea that motivates tries and later DAWGs.
• Trie word representation: Describe how a trie represents a set of words: edges represent characters, the path from the root spells a prefix, and a node separates that prefix from the suffixes reachable beyond it. State how the diagram marks a prefix that is also a complete legal word.
  Why it matters: This path-based representation is needed to build, traverse, and recognize words in a trie.
• Trie diagram orientation: State that this chapter draws tries with the root on the left and traversal proceeding left to right, rather than using the usual top-down tree layout.
  Why it matters: Knowing the diagram orientation makes the chapter's trie figures easier to read.

Key terms: prefix tree, trie, deduplicate, prefix, ENABLE, edge, node, root, suffix, doubled circle

5.2.1 Nodes and edges

This section defines the mutable trie-node representation, its edge-oriented interface, and the constant-time operations used to navigate and extend it.

• Trie node representation: Describe the three pieces of information stored in a trie node: whether it ends a word, the character labels of its outgoing edges, and the nodes those edges lead to. Explain that outgoing edges are represented by a dictionary from char to Node, with no parent reference because traversal is only left to right.
  Why it matters: A trie works by following character-labeled edges, so this representation is the basis for constructing and searching the word list.
• Mutable node choice: Explain why trie nodes are mutable in this implementation: trie construction proceeds from the root toward leaves, whereas immutable trees are most convenient to build from leaves upward. State that later DAWG construction also requires more complex node mutations.
  Why it matters: The mutability choice makes incremental trie construction practical and prepares the representation for the later DAWG algorithm.
• Edge-oriented node interface: Describe the node operations in terms of trie edges: listing labels, following an edge, trying to follow an absent edge, testing for an edge, and adding or reusing a node for an edge. Distinguish FollowEdge throwing when an edge is absent from TryFollowEdge returning null, and distinguish AddNewNode from TryAddNewNode reusing an existing edge target.
  Why it matters: These operations are the vocabulary that later code uses to traverse and grow the trie without exposing its dictionary implementation.
• Encapsulated edge storage: Justify keeping the edge dictionary private and exposing node-and-edge operations instead. Explain that this makes client code express trie meaning rather than dictionary mechanics, and permits a different edge implementation without changing callers.
  Why it matters: Encapsulation keeps the trie API understandable and protects client code from changes to the underlying edge-storage choice.
• Node operation complexity: State that the node class is a thin wrapper around a dictionary keyed by one character, so its described operations are O(1) in both time and space. Distinguish this per-operation claim from the later question of the total byte cost of all trie nodes.
  Why it matters: Constant-time edge operations explain why a trie can efficiently process each character while total memory usage remains a separate concern.

Key terms: node, edge, outgoing edges, edge labels, IsEnd, Dictionary<char, Node>, mutable, immutable, root, leaves

5.2.2 The trie-building algorithm

This section explains how to build a trie by sharing word prefixes and establishes the algorithm’s optimal O(mn) construction time.

• Trie insertion by shared prefixes: Describe how adding a word to a trie creates nodes for a new path when no prefix exists, but reuses existing nodes through a common prefix and adds only the remaining suffix. State that the final node for the word is marked as an end-of-word node.
  Why it matters: Sharing prefix nodes is the defining construction idea that lets a trie represent many words without repeating their common beginnings.
• Empty trie root initialization: State that construction begins with a root node having no outgoing edges and no end-node mark, representing an empty word list. Describe how adding the first word creates a node sequence for all of its characters.
  Why it matters: The empty root provides the common starting point from which every word path in the trie is built.
• Trie construction time complexity: Explain that building a trie for n words of m characters each takes O(mn) time because Add examines every character of every word and TryAddNewNode is O(1). Justify that this is asymptotically unavoidable because the algorithm must inspect every character in the input word list.
  Why it matters: This shows that prefix sharing can reduce representation duplication without avoiding the necessary work of reading the input words.

Key terms: trie, common prefix, root node, end node, TryAddNewNode, outgoing edges, empty word list, Add, O(mn), O(1)

5.2.3 Using a trie as a word list

This section shows how a trie-backed WordGraph implements word containment and prefix search efficiently by locating a prefix node and enumerating its suffixes.

• Prefix-node lookup: Describe how Find follows the edges labeled by each character of a prefix from the root and returns the associated node or null when an edge is missing. Explain how Contains uses that result and the node’s end-of-word marker to distinguish a complete stored word from a mere prefix.
  Why it matters: Locating the prefix node is the shared first step for both exact-word and prefix queries.
• Prefix-result enumeration: Explain how StartsWith uses Find to reject an absent prefix or enumerate every word below the prefix node. Describe how Words yields the prefix itself when its node ends a word, recursively follows outgoing edges, and restores the StringBuilder before returning.
  Why it matters: This traversal returns all matching words without repeatedly scanning the entire word list or copying partial strings unnecessarily.
• Trie query complexity: State that Contains takes O(m) time because it follows at most m edges and TryFollowEdge is O(1). Explain that StartsWith reaches the common prefix point in O(m) time and then takes O(m) to construct each yielded word, improving on the sorted word list’s O(m log n) lookup cost and repeated prefix checks.
  Why it matters: The performance comparison explains why trie traversal is preferable to sorted-list searching for these word queries.

Key terms: WordGraph, Find, Contains, TryFollowEdge, end-of-word marker, StartsWith, Words, StringBuilder, prefix, suffixes

5.2.4 How much memory are we saving with a trie?

This subsection evaluates trie memory savings, exposes node overhead and duplicated suffix leaves, and motivates compressing a trie into a word graph.

• Prefix-sharing space savings: Explain that a trie's character storage savings depend entirely on how many prefixes its words share, because common prefixes are represented once.
  Why it matters: Prefix sharing is the basic reason a trie can use fewer character-bearing edges than a plain word list.
• Node overhead and leaf duplication: Describe why fewer character edges do not automatically make a trie memory-efficient: every edge points to a node with a dictionary, and many terminal leaf nodes can be logically identical yet separately allocated.
  Why it matters: Object and dictionary overhead can erase the apparent memory savings suggested by counting characters alone.
• Suffix deduplication opportunity: Explain that a normal prefix tree deduplicates prefixes but not common suffixes, and that sharing equivalent suffix portions from both ends can produce a logically equivalent word graph with fewer nodes.
  Why it matters: Recognizing equivalent suffix subgraphs is the key motivation for moving from tries to directed acyclic word graphs.
• ENABLE trie memory result: State what the ENABLE statistics demonstrate: prefix sharing reduces the node count substantially, but 111,507 non-prefix words create separate end leaves whose memory cost prevents meaningful savings over a sorted list with duplicated prefixes.
  Why it matters: The large-word-list result shows why the small trie example understates the practical cost of duplicate terminal nodes.

Key terms: trie, prefix tree, common prefixes, edges, edge, node, dictionary, end-of-word node, leaf node, common suffixes

5.3 Tries are not-so-secretly finite state automata

This section recasts a trie as a finite state automaton and motivates building a minimal automaton directly rather than minimizing a fully built trie.

• Finite state automaton model: Explain a finite state automaton as a machine with finitely many internal states and inputs, where each input causes a transition determined only by the current state and that input.
  Why it matters: This model provides the vocabulary for viewing word-storage structures as machines that accept strings.
• Trie as word automaton: Describe how a trie maps onto an FSA: trie nodes are states, labeled edges are input-driven transitions, the root is the start state, and word-ending nodes are success states. Explain that Contains asks whether a string reaches a success state, and that all accepted strings form the machine's language.
  Why it matters: This correspondence turns trie lookup and word storage into an automaton-recognition problem that can be optimized.
• Direct minimal FSA construction: Explain why equivalent FSA states can be deduplicated without changing the accepted language, and why building a complete trie and then minimizing it is unsuitable when memory is constrained. State that the desired approach constructs the minimal FSA directly from a word list.
  Why it matters: Avoiding the oversized intermediate trie is the reason to build a DAWG while processing the words.

Key terms: finite state automaton, FSA, states, inputs, transitions, trie, start state, success states, Contains, language

5.4 Building a DAWG

This section introduces DAWGs and explains the sorted, incremental minimization strategy that builds a minimal word-recognizing graph while safely deferring optimization of the most recently added word.

• DAWG suffix deduplication: Explain that a Directed Acyclic Word Graph deduplicates equivalent suffixes as well as shared prefixes, so the word structure becomes an acyclic graph rather than a tree. State that this kind of graph is also called a Deterministic Acyclic Finite State Automaton (DAFSA).
  Why it matters: Sharing suffixes is the additional compression that lets a DAWG improve on a trie.
• Incremental minimization invariant: Describe the DAWG-building invariant: after each sorted word is added, the graph is minimal for every earlier word, but nodes on the most recently added word may remain unoptimized. Explain that adding the next word first optimizes the previous word, and the final word is optimized after input ends.
  Why it matters: This invariant permits a nearly minimal graph throughout construction without preventing later words from extending the newest path.
• Safe deferred node merging: Explain why nodes on the latest word must not be merged prematurely: a later word can extend one of those nodes, making it no longer equivalent to the node it seemed to match. Describe optimizing the previous word by examining its nodes from right to left, while leaving the shared path of the incoming word available for extension.
  Why it matters: Deferring merges prevents the builder from accidentally accepting words that were never supplied.
• Sorted ordinal input requirement: State that this version of the DAWG-building algorithm requires words in alphabetical, character-by-character ordinal order. Distinguish ordinal sorting from nonordinal collation, which can treat characters such as German ß and the sequence ss as equal even though ordinal sorting does not.
  Why it matters: Supplying words in the required ordering is necessary for the presented construction algorithm to operate as described.
• Example graph size reduction: State that the example trie has 14 nodes, combining leaf nodes reduces it to 11, and the fully minimized DAWG has 10 nodes, the smallest FSA recognizing that word set.
  Why it matters: The example gives a concrete measure of the extra savings gained by minimizing equivalent internal suffix states.

Key terms: Directed Acyclic Word Graph, DAWG, Deterministic Acyclic Finite State Automaton, DAFSA, suffixes, prefixes, almost minimal DAWG, minimal DAWG, invariant, last word added

5.4.1 What problems must we solve to build a DAWG?

This subsection breaks DAWG construction into four tasks and introduces Node operations needed to revisit and optimize the previously added word.

• DAWG construction tasks: Describe the four tasks required when adding a word to a DAWG: find its common prefix with the previous word, identify prior-word nodes to inspect, optimize equivalent nodes by replacement, and append the new suffix.
  Why it matters: These tasks organize the incremental algorithm that builds a minimized word graph.
• Previous-word path recovery: Explain how alphabetical insertion order lets the builder find nodes belonging to the most recently added word: from the common-prefix node, repeatedly follow the highest-letter, or last, outgoing edge.
  Why it matters: Recovering this path identifies exactly which earlier nodes can be checked for merging.
• Node support operations: Describe the three Node members added for DAWG construction: Count reports outgoing-edge count, LastEdgeLabel reports the highest-label outgoing edge and fails for a node with no edges, and ReplaceEdge redirects an existing edge to a specified node.
  Why it matters: These operations provide the path traversal and edge rewiring needed to optimize the graph incrementally.

Key terms: common prefix, optimization opportunities, already-optimized node, new suffix, DAWG, sorted order, highest letter, LastEdgeLabel, previously added word, Count

5.4.2 Equivalence of nodes

This section defines DAWG node equivalence, implements it as equality and hashing, and uses a canonical-node hash set to detect duplicates efficiently.

• DAWG node equivalence criteria: Describe when two DAWG nodes are equivalent: they have the same end-of-word status, the same outgoing edge labels, and each matching label leads to the identical target node by reference.
  Why it matters: This definition determines which graph nodes can be deduplicated without changing the words represented by the DAWG.
• Equality comparer hash contract: Explain how the Node equality comparer and GetHashCode must agree: equivalent nodes must produce equal hash codes, while unequal nodes may still collide; the hash must include the equivalence-relevant state in a consistent order.
  Why it matters: A hash set can only reliably find equivalent canonical nodes when equality and hashing obey the required contract.
• Canonical node hash set: Explain that a hash set of canonical nodes from the already optimized graph portion provides expected O(1) duplicate detection, and that a node must be fully optimized and never mutated before entering that set.
  Why it matters: This avoids prohibitively expensive scans of the graph while preserving reliable hash-set membership tests.

Key terms: equivalent nodes, IsEnd, outgoing edges, edge labels, reference-equal, Leaf nodes, IEqualityComparer<Node>, GetHashCode, HashCode, Add

5.4.3 The DAWG-building algorithm

This section presents the incremental algorithm for building a minimal DAWG by optimizing the previous word’s suffix before appending the new word’s suffix.

• Incremental DAWG insertion: Describe how the DAWG Add method processes each new word: it finds the prefix shared with the previous word, optimizes the unshared suffix of the previous word, and then appends the new word’s suffix. Explain why these stages are separate rather than combined as in trie construction.
  Why it matters: This is the central process that lets a word graph be minimized while words are added one at a time.
• Recursive suffix canonicalization: Explain how FixUpLastWord recursively optimizes suffix nodes from the end of the previous word toward its shared prefix. Describe how replacing a node with an equivalent canonical node can make nodes closer to the middle newly equivalent and therefore requires recursive processing first.
  Why it matters: Processing from the end backward ensures that all downstream structure is canonical before the builder decides whether an earlier node can be merged.
• Canonical HashSet mutation rules: Describe how HashSet<T>.TryGetValue is used to retrieve an equivalent canonical node or indicate that none exists. Explain why mutating a node with ReplaceEdge is safe only before that node enters the canonical set, while its successor has already been fully fixed up before being added.
  Why it matters: The algorithm can safely use a hash set of canonical nodes only if objects are not changed after their hash-set membership is established.
• DAWG word-query reuse: State that Contains and StartsWith need no DAWG-specific implementation because the existing WordGraph code works for a DAWG as well as for a trie.
  Why it matters: A DAWG changes how the word graph is built and shared, without requiring new code for these word-list queries.

Key terms: Add, common prefix, suffix, TrieBuilder, TryAddNewNode, FixUpLastWord, equivalent, canonical, ReplaceEdge, HashSet<T>

5.4.4 How much expense does optimizing the graph as you go add?

This section shows that optimizing a DAWG during construction adds constant-factor work but does not worsen the builder’s asymptotic time or space complexity compared with building a trie.

• DAWG construction time complexity: Explain why the DAWG-building algorithm remains O(mn), the same asymptotic time complexity as trie building, even though it performs graph optimization after adding words.
  Why it matters: This establishes that DAWG compression can be gained without an asymptotic construction-time penalty.
• FixUpLastWord operation costs: Describe why the operations inside FixUpLastWord are treated as O(1), including why finding the last edge label with Max() does not change the asymptotic result.
  Why it matters: The constant-time parts of FixUpLastWord are what allow its total cost to remain linear.
• DAWG builder memory overhead: Explain why maintaining the canonical-node set does not increase the DAWG builder’s asymptotic space complexity over a trie builder.
  Why it matters: The DAWG’s construction-time bookkeeping does not erase the space-saving purpose of the compressed graph.

Key terms: DAWG builder, trie builder, O(mn), FixUpLastWord, asymptotic complexity, canonical set, Max(), last edge label, alphabet, canonical nodes

5.5 DAWG vs. trie for ENABLE

This section compares a DAWG with a trie for the ENABLE word list, explaining its large structural savings, practical object-memory tradeoff, and compact byte-array representation.

• DAWG suffix-sharing savings: Explain why the DAWG for ENABLE has far fewer nodes than the equivalent trie, including the effect of merging redundant leaves and common English suffixes.
  Why it matters: Suffix sharing is the reason a DAWG can represent a searchable word list much more compactly than a trie.
• Node and edge count relationship: Describe why DAWG edge counts decrease less dramatically than node counts: merging nodes deletes redundant nodes but gives each remaining canonical node more inbound edges.
  Why it matters: This explains why node savings and edge savings should not be expected to move in lockstep when a tree becomes a shared graph.
• Packed DAWG byte layout: Describe the compact byte-array encoding for a DAWG: a 4-byte node header records IsEnd and outgoing-letter bits, followed by 3-byte offsets for its outgoing edges, and the pattern repeats in one array.
  Why it matters: A packed layout preserves the DAWG's searchable structure while making it feasible in severely memory-constrained environments.
• Memory tradeoff and packed size: Compare the memory costs of the object-based DAWG and the packed DAWG, including why the former is practical on modern machines but the latter fits within a 640KB limit.
  Why it matters: Choosing a representation requires distinguishing structural compactness from the runtime overhead of ordinary objects and collections.

Key terms: DAWG, trie, suffix deduplication, redundant leaf nodes, canonical nodes, ENABLE, inbound edges, tree, byte array, 4-byte header

5.6 Summary

This summary compares word-completion structures and explains how incrementally built, minimized DAWGs achieve compact prefix search.