标签: trie

因此,如果我必须在哈希表或前缀树之间进行选择,那么哪些区别因素会导致我选择一个而不是另一个.从我自己的天真的角度来看,似乎使用trie有一些额外的开销,因为它没有存储为数组但是就运行时而言(假设最长的键是最长的英语单词)它可以基本上是O (1)(就上限而言).也许最长的英文单词是50个字符？

获得索引后,哈希表会立即查找.然而,散列获得索引的关键似乎很容易接近50步.

有人能为我提供更有经验的观点吗？谢谢!

我是Python的新手并且正在努力学习和进步.我对TRIE和DAWG很感兴趣,我一直在阅读它,但我不明白输出TRIE或DAWG文件应该是什么样的.

• TRIE应该是嵌套字典的对象吗？每个字母被分成字母等等？
• 如果有100k或500k条目,那么在这样的字典上查找是否会很快？
• 如何实现由多个单词组成的字块 - 或用空格分隔？
• 如何将单词的前缀或后缀链接到结构中的另一个部分？[对于DAWG]

我想了解最佳输出结构,以便弄清楚如何创建和使用它.

我也很感激DAWG和TRIE的输出应该是什么.

我不希望看到彼此相关的气泡的图形表示,我在阅读时看到它们很多.

一旦将一组单词转换为TRIE或DAWG,我想知道输出对象.

谢谢.

我有一个Java程序,它存储了很多从Strings到各种对象的映射.

现在,我的选择是依赖哈希(通过HashMap)或二进制搜索(通过TreeMap).我想知道在流行的高质量馆藏图书馆中是否有一个高效且标准的基于trie的地图实施？

我过去曾写过自己的文章,但如果可以的话,我宁愿选择标准的东西.

快速说明:虽然我的问题很普遍,但在当前项目中,我处理的是大量数据,这些数据由完全限定的类名或方法签名索引.因此,有许多共享前缀.

我正在阅读Tries通常称为前缀树和Suffix Trees.
虽然我找到了代码,但Trie我找不到一个例子Suffix Tree.此外,我感觉构建a的代码与a的代码Trie相同,Suffix Tree唯一的区别是在前一种情况下我们存储前缀但在后面的后缀中.
这是真的？任何人都可以帮我解决这个问题吗？一个示例代码将是很好的帮助!

在C/C++中是否有任何速度和缓存效率的trie实现？我知道什么是特里,但我不想重新发明轮子,自己实施.

我远程记住,尝试不存储每个节点的整个数据,只存储父节点的后缀.

树存储整个数据,但只根据前缀组织自己.

因此尝试变得更小,这允许例如非常好地压缩字典.

这真的是唯一的区别吗？

从实际应用程序中我记得尝试在范围查询中更快.甚至还有特殊的solr/lucene trie字段来加速范围查询.但那是怎么回事？

尝试和树木的实际差异是什么,优点和缺点是什么？

哪种结构提供最佳性能结果; trie(前缀树),后缀树或后缀数组？还有其他类似的结构吗？这些结构有哪些优秀的Java实现？

编辑:在这种情况下,我想在一个大的名字字典和一大组自然语言文本之间进行字符串匹配,以便识别文本上字典的名称.

更新3

完成.下面是最终通过我所有测试的代码.再次,这是模仿Murilo Vasconcelo的Steve Hanov算法的修改版本.感谢所有帮助!

/**
 * Computes the minimum Levenshtein Distance between the given word (represented as an array of Characters) and the
 * words stored in theTrie. This algorithm is modeled after Steve Hanov's blog article "Fast and Easy Levenshtein
 * distance using a Trie" and Murilo Vasconcelo's revised version in C++.
 * 
 * http://stevehanov.ca/blog/index.php?id=114
 * http://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/
 * 
 * @param ArrayList<Character> word - the characters of an input word as an array representation
 * @return int - the minimum …

有谁知道我在哪里可以找到如何在C#中构建一个trie的例子.我正在尝试使用字典/单词列表并用它创建一个trie.

可能重复:
我在哪里可以找到基于Trie的标准地图实现？

我想在Java中使用Trie,是否有可以使用的实现？(我试过寻找一个,但我没找到它).