首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >后缀树搜索时间

问后缀树搜索时间
EN

Stack Overflow用户
提问于 2011-04-28 14:24:58
回答 2查看 1.3K关注 0票数 0

有人知道以下陈述的原因吗?还是有一个更好的网站来问这类问题?任何指针都将不胜感激。

如果一个模式出现在文本中(长度n) k次,则搜索该文本后缀树中的所有k次将花费O(n+k).

。

EN

回答 2

Stack Overflow用户

发布于 2011-04-28 14:33:29

后缀树搜索的时间长度与正在搜索的模式的长度成正比。如果您为密西西比构建后缀树并搜索ssi。必须执行的查找是3,时间是O(n),其中n是模式的长度。

票数 0
EN

Stack Overflow用户

发布于 2012-03-04 17:09:28

根据您在何处找到该语句,在上下文中可能有特定的原因说明它是正确的。

但是,“+k”通常的原因仅仅是需要额外的O(k)操作来插入返回给用户的结果列表中的每个匹配项。当使用倒排文件而不是后缀树时,情况不一定如此,因为索引中的倒排列表(也称为公告列表)已经是最终的结果列表(至少如果我们假设(a)查询只包含一个令牌,(b)倒排列表是未压缩的)。

但是后缀树通常(除非是特别准备的)不包含这样的匹配列表。因此,在匹配过程中,您可以通过树标识路径,结束于某个内部节点。从那里开始,您必须跟踪该内部节点的子树中的所有路径,以标识告诉您匹配的实际位置(每个匹配的一个叶节点)的叶节点,并在返回给用户的结果列表中插入匹配位置。这最后一步需要O(k)时间。

还请注意,跟踪内部节点子树中的所有路径可能会花费大量额外时间,其中总复杂度甚至高于O(n+k)。这取决于是否有从内部节点到子树中的叶节点的直接指针。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5820153

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档