我正在 VB.NET 中实现一个用于预测文本输入的 trie - 就 trie 的使用而言，基本上是自动完成。我已经使我的 trie 成为基于通用字典类的递归数据结构。
基本上是：
class WordTree Inherits Dictionary(of Char, WordTree)
单词中的每个字母（全部大写）都用作新 WordTrie 的键。叶子上的空字符表示单词的终止。为了找到以前缀开头的单词，我会遍历字典树直到我的前缀为止，然后收集所有子单词。
我的问题基本上是关于 trie 本身的实现。我正在使用字典哈希函数来分支我的树。我可以使用一个列表并对列表进行线性搜索，或者做其他事情。这里的平滑移动是什么？这是进行分支的合理方式吗？
谢谢。
更新：
为了澄清，我基本上是在问字典分支方法是否明显不如其他替代方法。我使用此数据结构的应用程序仅使用大写字母，因此数组方法可能是最好的。我可能会在将来使用相同的数据结构来处理更复杂的预输入情况（更多字符）。在这种情况下，听起来字典是正确的方法 - 直到我需要使用更复杂的东西。
如果只是 26 个字母，则作为 26 个条目的数组。然后通过索引查找。如果存储桶列表长于 26，它可能使用比字典更少的空间。
如果您担心空间问题，可以对有效字节转换使用位图压缩（假设有 26 个字符的限制）。
class State // could be struct or whatever
{
int valid; // can handle 32 transitions -- each bit set is valid
vector<State> transitions;
State getNextState( int ch )
{
int index;
int mask = ( 1 << ( toupper( ch ) - 'A' )) -1;
int bitsToCount = valid & mask;
for( index = 0; bitsToCount ; bitsToCount >>= 1)
{
index += bitsToCount & 1;
}
transitions.at( index );
}
};
还有其他方法来进行位计数这里，向量的索引是有效位集中设置位的数量。另一种选择是直接索引状态数组；
class State
{
State transitions[ 26 ]; // use the char as the index.
State getNextState( int ch )
{
return transitions[ ch ];
}
};
三元搜索树是一种在空间上高效并可能提供亚线性前缀查找的良好数据结构。 Peter Kankowski 有一篇关于此的精彩文章。他使用 C，但一旦你理解了数据结构，它就是简单的代码。正如他提到的，这是 ispell 用于拼写纠正的结构。
我已经用 8 位字符在 C 中完成了这个（一个 trie 实现），并且简单地使用了数组版本（如“26 个字符”答案所暗示的）。
但是，我猜测您需要完整的 unicode 支持（因为 .NET 字符是 unicode，以及其他原因）。假设您必须支持 unicode，那么哈希/映射/字典查找可能是您最好的选择，因为每个节点中的 64K 条目数组不会真正很好地工作。
我能想到的唯一解决方案是将整个字符串（后缀或可能的“内修复”）存储在尚未分裂的分支上，具体取决于树（呃，trie）的稀疏程度。不过，这增加了很多逻辑来检测多字符字符串，并在引入备用路径时将它们分开。
读取与更新模式是什么？
---- 2013 年 7 月更新 ---
如果 .NET 字符串具有像 java 这样的函数来获取字符串的字节（作为 UTF-8），那么在每个节点中使用一个数组来表示当前位置的字节值可能是一个好方法。您甚至可以使数组大小可变，在每个节点中使用第一个/最后一个边界指示符，因为许多节点无论如何都只有小写 ASCII 字母，或者在某些情况下只有大写字母或数字 0-9。
我发现burst trie's非常节省空间。我在 Scala 中编写了自己的 burst trie，它也重新使用了我在 GWT 的 trie 实现中发现的一些想法。我在 Stripe 的夺旗竞赛中使用了它，解决了一个具有少量 RAM 的多节点问题。
// we start with the TrieNode
const TrieNode = function (key) {
// the "key" value will be the character in sequence
this.key = key;
// we keep a reference to parent
this.parent = null;
// we have hash of children
this.children = {};
// check to see if the node is at the end
this.end = false;
this.getWord = function() {
let output = [];
let node = this;
while (node !== null) {
output.unshift(node.key);
node = node.parent;
}
return output.join('');
};
}
const Trie = function() {
this.root = new TrieNode(null);
// inserts a word into the trie.
this.insert = function(word) {
let node = this.root; // we start at the root
// for every character in the word
for(let i = 0; i < word.length; i++) {
// check to see if character node exists in children.
if (!node.children[word[i]]) {
// if it doesn't exist, we then create it.
node.children[word[i]] = new TrieNode(word[i]);
// we also assign the parent to the child node.
node.children[word[i]].parent = node;
}
// proceed to the next depth in the trie.
node = node.children[word[i]];
// finally, we check to see if it's the last word.
if (i == word.length-1) {
// if it is, we set the end flag to true.
node.end = true;
}
}
};
// check if it contains a whole word.
this.search = function(word) {
let node = this.root;
// for every character in the word
for(let i = 0; i < word.length; i++) {
// check to see if character node exists in children.
if (node.children[word[i]]) {
// if it exists, proceed to the next depth of the trie.
node = node.children[word[i]];
} else {
// doesn't exist, return false since it's not a valid word.
return false;
}
}
// we finished going through all the words, but is it a whole word?
return node.end;
};
// returns every word with given prefix
this.startsWith = function(prefix) {
let node = this.root;
let output = [];
// for every character in the prefix
for(let i = 0; i < prefix.length; i++) {
// make sure prefix actually has words
if (node.children[prefix[i]]) {
node = node.children[prefix[i]];
} else {
// there's none. just return it.
return output;
}
}
// recursively find all words in the node
findAllWords(node, output);
return output;
};
// recursive function to find all words in the given node.
const findAllWords = (node, arr) => {
// base case, if node is at a word, push to output
if (node.end) {
arr.unshift(node.getWord());
}
// iterate through each children, call recursive findAllWords
for (let child in node.children) {
findAllWords(node.children[child], arr);
}
}
// removes a word from the trie.
this.remove = function (word) {
let root = this.root;
if(!word) return;
// recursively finds and removes a word
const removeWord = (node, word) => {
// check if current node contains the word
if (node.end && node.getWord() === word) {
// check and see if node has children
let hasChildren = Object.keys(node.children).length > 0;
// if has children we only want to un-flag the end node that marks the end of a word.
// this way we do not remove words that contain/include supplied word
if (hasChildren) {
node.end = false;
} else {
// remove word by getting parent and setting children to empty dictionary
node.parent.children = {};
}
return true;
}
// recursively remove word from all children
for (let key in node.children) {
removeWord(node.children[key], word)
}
return false
};
// call remove word on root node
removeWord(root, word);
};
}