A DAWG-building algorithm incrementally constructs a minimal directed acyclic word graph from alphabetically sorted words. It shares prefixes like a trie, then deduplicates equivalent suffix paths. After each insertion, every earlier word is minimized; only the newest word may still contain redundant nodes. A final fix-up produces a minimal graph. section 5.4
Each insertion follows a deliberately staged process:
- Find the common prefix shared with the previously added word. section 5.4.3
- Minimize the completed suffix of the previous word, working backward from its end. section 5.4.3
- Append nodes for the new word’s remaining suffix and mark its final node as accepting. section 5.4.3
- Canonicalize equivalent nodes with a hash set; recurse before registering a node because eliminating a deeper duplicate can expose a shallower one. section 5.4.3
A small sorted dictionary
For car, care, cares, cars, fir, fire, firer, firers, and firs, the graph initially resembles a trie. Adding firers leaves its ers suffix temporarily unoptimized; backward fix-up discovers redundant nodes and redirects edges to canonical equivalents. After the final fix-up, the result is the smallest DAWG representing all nine words. section 5.4
The sorted-input requirement is substantive: this version expects ordinal, character-by-character ordering. A more complex arbitrary-order variant exists but lies outside the procedure here. DAWG and DAFSA name the same general kind of deterministic acyclic word graph, with DAWG emphasizing stored words. section 5.4
Listing 5.8 Building the DAWG algorithm
sealed class DawgBuilder
{
private class NodeEquality : IEqualityComparer<Node> { … }
private Node root = new();
private HashSet<Node> canonicalNodes =
new HashSet<Node>(new NodeEquality()); #1
private DawgBuilder() { }
public static Node MakeDawg(IEnumerable<string> words) #2
{
var db = new DawgBuilder();
foreach (var word in words)
db.Add(word); #3
db.FixUpLastWord(db.root); #4
return db.root;
}
private void Add(string word)
{
int i = 0;
Node n = root;
for (; i < word.Length; i += 1) #5
{
if (!n.HasEdge(word[i]))
break;
n = n.FollowEdge(word[i]);
}
FixUpLastWord(n); #6
for (; i < word.Length; i += 1) #7
n = n.AddNewNode(word[i]);
n.IsEnd = true;
}
private void FixUpLastWord(Node n)
{
if (n.Count == 0) #8
return;
char c = n.LastEdgeLabel;
Node s = n.FollowEdge(c); #9
FixUpLastWord(s); #10
Node? canonical;
canonicalNodes.TryGetValue(s, out canonical); #11
if (canonical == null)
canonicalNodes.Add(s); #12
else
n.ReplaceEdge(c, canonical); #13
}
}
The C# listing makes the invariant concrete: it scans the shared prefix, fixes the previous word, appends the new suffix, and performs a final root-level fix-up. section 5.4.3
