I've seen a few people asking for this elsewhere, so here's a basic
implementation of a string trie in C#. I'm using this to load and
search a dictionary of about two hundred thousand words. It's fairly
quick (a couple of seconds for the full load). It's a bit of a memory
hog -- about 50MB resident, once the file is loaded -- but most of my
C#/.NET programs are.
Example usage:
StringTrie st = new StringTrie();
st.LoadFromFile("wordlist.txt");
st.Add("additionalword");
st.Add("additionalotherword");
if ( st.Search("myword") == StringTrie.Found )
etc...
using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
namespace TrieLib
{
class StringTrie
{
private StringTrieBucket bucket = new StringTrieBucket(' ');
public enum SearchResults
{
NotFound,
Found,
FoundPartial
}
public StringTrie()
{
}
public void LoadFromFile(string pathname)
{
TextReader tr = File.OpenText(pathname);
string line;
while ( (line = tr.ReadLine() ) != "")
{
string[] sa = line.Split(' ');
foreach (string s in sa)
if (s.Length < 11)
Add(s);
}
tr.Close();
GC.Collect();
}
public void Add(string s)
{
Queue<charletters = new
Queue<char>(s.ToLower().ToCharArray());
AddToTrie(bucket, letters);
}
public SearchResults Search(string s)
{
Queue<charletters = new
Queue<char>(s.ToLower().ToCharArray());
return SearchTrie(bucket, letters);
}
private SearchResults SearchTrie(StringTrieBucket b,
Queue<charletters)
{
if (letters.Count == 0)
if (b.terminal)
return SearchResults.Found;
else
return SearchResults.FoundPartial;
Char c = letters.Dequeue();
StringTrieBucket bucket = b;
foreach (StringTrieBucket stb in b.kids)
if (stb.letter == c)
return SearchTrie(stb, letters);
return SearchResults.NotFound;
}
private void AddToTrie(StringTrieBucket b, Queue<char>
letters)
{
if (letters.Count == 0)
{
b.terminal = true;
return;
}
Char c = letters.Dequeue();
StringTrieBucket bucket = null;
bool found = false;
foreach (StringTrieBucket stb in b.kids)
if (stb.letter == c)
{
bucket = stb;
found = true;
break;
}
if (! found)
{
bucket = new StringTrieBucket(c);
b.kids.Add(bucket);
}
AddToTrie(bucket, letters);
}
}
class StringTrieBucket
{
internal char letter;
internal List<StringTrieBucketkids;
internal bool terminal;
internal StringTrieBucket(char c)
{
this.letter = c;
kids = new List<StringTrieBucket>();
terminal = false;
}
}
}