Cra*_*lus 70 algorithm suffix-tree trie data-structures
我正在阅读Tries通常称为前缀树和Suffix Trees.
虽然我找到了代码,但Trie我找不到一个例子Suffix Tree.此外,我感觉构建a的代码与a的代码Trie相同,Suffix Tree唯一的区别是在前一种情况下我们存储前缀但在后面的后缀中.
这是真的？任何人都可以帮我解决这个问题吗？一个示例代码将是很好的帮助!
Ze *_*lob 56
后缀树可以被视为构建在trie之上的数据结构,而不仅仅是将字符串本身添加到trie中,您还可以添加该字符串的每个可能后缀.例如,如果要在后缀树中索引字符串banana,则应使用以下字符串构建trie:
banana
anana
nana
ana
na
a
完成后,您可以搜索任何n-gram并查看它是否存在于您的索引字符串中.换句话说,n-gram搜索是对字符串的所有可能后缀的前缀搜索.
这是构建后缀树的最简单,最慢的方法.事实证明,在这种数据结构上有许多更好的变体可以改善空间和构建时间.我在这个领域不够精通概述,但您可以从查看后缀数组或此类高级数据结构开始(讲座16和18).
这个答案也很好地解释了这种数据结构的变体.
如果您想象一个Trie,其中您放置了一些单词的后缀,您将能够非常轻松地查询它的字符串的子串.这是后缀树背后的主要思想,它基本上是一个"后缀trie".
但是使用这种天真的方法,为一个大小为n的字符串构造这个树将是O(n ^ 2)并占用大量内存.
由于此树的所有条目都是相同字符串的后缀,因此它们共享大量信息,因此有一些优化的算法可以让您更有效地创建它们.例如,Ukkonen的算法允许您以O(n)时间复杂度在线创建后缀树.