Trie实现问题
我正在为VB.NET中的预测文本输入实现一个trie --就trie的使用而言，基本上是自动补全。我的trie是一个基于泛型字典类的递归数据结构。
它基本上是：
class WordTree Inherits Dictionary(of Char, WordTree)单词中的每个字母(全部大写)用作新WordTrie的键。叶子上的空字符表示单词的终止。为了找到以前缀开头的单词，我遍历trie，直到我的前缀，然后收集所有孩子的单词。
我的问题基本上是关于trie本身的实现。我正在使用字典哈希函数来分支我的树。我可以使用列表，对列表进行线性搜索，或者做其他事情。这里的平稳移动是什么？这是一种合理的分支方式吗？
谢谢。
更新：
只是为了澄清，我基本上是在问字典分支方法是否明显不如其他替代方法。我使用这种数据结构的应用程序只使用大写字母，所以数组方法可能是最好的。将来，我可能会在更复杂的typeahead情况下使用相同的数据结构(更多字符)。在这种情况下，听起来字典是正确的方法-直到我需要使用更复杂的东西。
回答 5
Stack Overflow用户
发布于 2009-03-23 19:26:31
如果它只有26个字母，就像一个26个条目的数组。然后按索引进行查找。如果bucket-list长于26，则它可能比字典使用更少的空间。
Stack Overflow用户
发布于 2009-03-23 21:01:21
如果您担心空间问题，您可以对有效的字节转换使用位图压缩，假设限制为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 );
}
};还有其他方法可以进行位计数Here，向量中的索引是有效位集中设置的位数。另一种选择是状态的直接索引数组；
class State
{
State transitions[ 26 ]; // use the char as the index.
State getNextState( int ch )
{
return transitions[ ch ];
}
};Stack Overflow用户
发布于 2009-03-23 19:46:03
一个好的数据结构是三元搜索树，它在空间上是有效的，并且可能提供亚线性前缀查找。关于它的Peter Kankowski has a article。他使用的是C，但是一旦你理解了数据结构，代码就会变得简单明了。正如他提到的，这是ispell用于拼写更正的结构。
https://stackoverflow.com/questions/674844
复制相似问题
腾讯云开发者
