A prefix is an initial substring of a word or string. In a word list, it identifies a shared path through a trie: the prefix car leads to the node reached by following c, a, and r. section 5.2.3
A prefix supports two closely related word-list operations:
- Find follows the prefix from the root; a missing edge proves that no stored word begins with it. section 5.2.3
- StartsWith locates the prefix node, then enumerates the words reachable below it, including the prefix itself when it is a complete word. section 5.2.3
- A StringBuilder carries the current prefix while recursive traversal appends and resets characters, avoiding unnecessary repeated string copying. section 5.2.3
The prefix car
Following car reaches one trie node. The words below it can contribute car, care, cares, and cars; the associated suffixes are the empty suffix, e, es, and s. section 5.2.3
Listing 5.4 A word list backed by a trie (or graph)
using System.Text;
sealed class WordGraph : IWords #1
{
private Node root;
public WordGraph(Node root)
{
this.root = root;
}
private Node? Find(string prefix)
{
Node? n = root;
foreach (char c in prefix)
{
n = n.TryFollowEdge(c);
if (n == null)
break;
}
return n;
}
public bool Contains(string word) => Find(word)?.IsEnd ?? false;
public IEnumerable<string> StartsWith(string prefix)
{
Node? n = Find(prefix);
return n == null ?
Enumerable.Empty<string>() :
Words(n, new StringBuilder(prefix));
}
private IEnumerable<string> Words(Node n, StringBuilder prefix)
{
if (n.IsEnd)
yield return prefix.ToString();
foreach (char c in n.EdgeLabels)
{
prefix.Append(c);
foreach (var word in Words(n.FollowEdge(c), prefix))
yield return word;
prefix.Remove(prefix.Length - 1, 1); #2
}
}
public IEnumerator<string> GetEnumerator() =>
StartsWith("").GetEnumerator(); #3
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
The C# implementation makes prefix lookup concrete: Find traverses character edges, while StartsWith reuses the resulting node to enumerate matching words. section 5.2.3
