1

我正在为 VB.NET 中的预测文本输入实现一个 trie - 就 trie 的使用而言，基本上是自动完成。我已经使我的 trie 成为基于通用字典类的递归数据结构。

基本上是：

class WordTree Inherits Dictionary(of Char, WordTree)

单词中的每个字母（全部大写）都用作新 WordTrie 的键。叶子上的空字符表示单词的终止。要找到以前缀开头的单词，我会一直走到我的前缀，然后收集所有子单词。

我的问题基本上是关于 trie 本身的实现。我正在使用字典哈希函数来分支我的树。我可以使用一个列表并对列表进行线性搜索，或者做其他事情。这里有什么流畅的动作？这是进行分支的合理方法吗？

谢谢。

更新：

只是为了澄清，我基本上是在问字典分支方法是否明显不如其他替代方法。我使用此数据结构的应用程序仅使用大写字母，因此数组方法可能是最好的。我可能会在未来更复杂的预输入情况（更多字符）中使用相同的数据结构。在这种情况下，听起来字典是正确的方法——直到我需要使用更复杂的东西。

4

5 回答 5

3

如果只是 26 个字母，则作为 26 个条目的数组。然后查找是按索引。如果桶列表长于 26，它可能比字典使用更少的空间。

于 2009-03-23T19:26:31.257 回答
3

如果您担心空间，您可以在有效字节转换上使用位图压缩，假设 26char 限制。

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 ];
    }
};
于 2009-03-23T21:01:20.687 回答
2

三元搜索树是一种在空间上高效并可能提供亚线性前缀查找的良好数据结构。Peter Kankowski 有一篇关于它的精彩文章。他使用 C，但是一旦你理解了数据结构，它就是简单的代码。正如他所提到的，这是 ispell 用于拼写更正的结构。

于 2009-03-23T19:46:02.660 回答
2

我已经用 8 位字符在 C 中完成了这个（trie 实现），并且简单地使用了数组版本（正如“26 字符”答案所暗示的那样）。

但是，我猜你想要完整的 unicode 支持（因为 .NET char 是 unicode 以及其他原因）。假设你必须支持 unicode，hash/map/dictionary 查找可能是你最好的选择，因为每个节点中的 64K 条目数组并不能很好地工作。

关于我能想到的唯一破解方法是将整个字符串（后缀或可能的“in-fixes”）存储在尚未分裂的分支上，具体取决于树的稀疏程度，呃，trie，是。但是，这增加了很多逻辑来检测多字符字符串，并在引入替代路径时将它们拆分。

什么是读取 vs 更新模式？

---- 2013 年 7 月更新 ---

如果 .NET 字符串具有类似 java 的函数来获取字符串的字节（如 UTF-8），那么在每个节点中都有一个数组来表示当前位置的字节值可能是一个不错的方法。您甚至可以使数组大小可变，在每个节点中使用第一个/最后一个边界指示符，因为许多节点无论如何都只有小写 ASCII 字母，或者在某些情况下只有大写字母或数字 0-9。

于 2009-03-23T19:49:11.840 回答
0

我发现Burst Trie非常节省空间。我在 Scala 中编写了自己的突发 trie，它还重用了我在 GWT 的 trie 实现中发现的一些想法。我在 Stripe 的 Capture the Flag 竞赛中使用了它来解决一个具有少量 RAM 的多节点问题。

于 2014-04-29T19:38:03.613 回答