首页 文章

实施问题

提问于
浏览 次
1

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

它基本上是：

class WordTree Inherits Dictionary(of Char, WordTree)

单词中的每个字母（所有大写字母）都用作新WordTrie的键 . 叶子上的空字符表示单词的终止 . 为了找到一个以前缀开头的单词，我将前往trie，然后收集所有的子单词 .

我的问题基本上是关于trie本身的实现 . 我正在使用字典哈希函数来分支我的树 . 我可以使用列表并对列表进行线性搜索，或者执行其他操作 . 这里的顺利举动是什么？这是一种合理的分支方式吗？

谢谢 .

更新：

只是为了澄清，我基本上都在问，字典分支方法是否明显不如其他选择 . 我使用此数据结构的应用程序仅使用大写字母，因此阵列方法可能是最好的 . 我将来可能会使用相同的数据结构来处理更复杂的类型结构（更多字符） . 在这种情况下，听起来字典是正确的方法 - 直到我需要使用更复杂的东西 .

trie

5 回答

  • 3

    我发现burst trie's非常节省空间 . 我写了自己的burst trie in Scala，它还重新使用了我在GWT 's trie implementation. I used it in Stripe' s Capture the Flag竞赛中发现的一些想法，这个想法是一个多节点且少量RAM的问题 .

    回复于
  • 0

    如果它只是26个字母，作为26个入口数组 . 然后按索引查找 . 如果bucket-list超过26，它可能比Dictionary使用更少的空间 .

    回复于
  • 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 );
    }
};

    还有其他方法可以进行位计数Here，向量索引是有效位集中的设置位数 . 另一种选择是直接索引的状态数组;

    class State
{
    State transitions[ 26 ]; // use the char as the index.

    State getNextState( int ch )
    {
        return transitions[ ch ];
    }
};
    回复于
  • 2

    三元搜索树是一种在空间中有效且可能提供子线性前缀查找的良好数据结构 . Peter Kankowski has a fantastic article关于它 . 他使用C语言，但一旦理解了数据结构，它就是简单的代码 . 正如他所提到的，这是用于拼写校正的结构 .

    回复于
  • 2

    我在C中用8位字符完成了这个（trie实现），并简单地使用了数组版本（由“26个字符”答案提到） .

    但是，我猜你想要完全的unicode支持（因为.NET char是unicode，除其他原因外） . 假设您必须支持unicode，哈希/ Map /字典查找可能是您最好的选择，因为每个节点中的64K条目数组将无法正常工作 .

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

    什么是读取与更新模式？

    ----更新jul 2013 ---

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

    回复于

相关问题