草庐IT

c++ - 在基数树/patricia trie 中进行前缀搜索

coder 2024-02-09 原文

我目前正在实现一个基数树/patricia trie(随便你怎么调用它)。我想用它在一个功能严重不足的硬件上的字典中进行前缀搜索。它应该或多或少像自动完成一样工作，我。 e.显示输入的前缀匹配的单词列表。

我的实现基于on this article ，但其中的代码不包括前缀搜索，尽管作者说:

[...] Say you want to enumerate all the nodes that have keys with a common prefix "AB". You can perform a depth first search starting at that root, stopping whenever you encounter back edges.

但我不明白它应该如何工作。例如，如果我从这些词构建一个基数树:

illness
imaginary
imagination
imagine
imitation
immediate
immediately
immense
in

对于前缀“i”和“in”，我将获得完全相同的“最佳匹配”，因此我似乎很难通过从最佳匹配开始遍历树来收集所有匹配的词。

此外，还有一个 radix tree implementation in Java在 RadixTreeImpl.java 中实现了前缀搜索.该代码显式检查所有节点(从某个节点开始)的前缀匹配 - 它实际上比较字节。

任何人都可以指出有关在基数树上实现前缀搜索的详细说明吗？ Java 实现中使用的算法是唯一的方法吗？

最佳答案

想想您的 trie 编码的内容。在每个节点，您都有通往该节点的路径，因此在您的示例中，您从 Λ(这是一个大写的 Lambda，这种希腊字体有点糟糕)开始，根节点对应于一个空字符串。 Λ 为使用的每个字母都有子代，因此在您的数据集中，您有一个分支，用于“i”。

  • Λ
  • Λ→"i"

在“i”节点，有两个子节点，一个用于“m”，一个用于“n”。下一个字母是“n”，所以你接受它，

  • Λ→"i"→"n"

并且由于在您的数据集中唯一以“i”、“n”开头的词是“in”，因此没有来自“n”的子项。这是一场比赛。

现在，假设数据集没有“in”，而是“infindibulum”。 (我引用的 SF 留作练习。)您仍然会以相同的方式到达“n”节点，但是如果您得到的下一个字母是“q”，您就知道这个词没有出现在你的数据集中，因为没有“q”分支。那时，你说“好吧，不匹配”。 (也许你然后开始添加这个词，也许不，这取决于应用程序。)

但是如果下一个字母是“f”，你可以继续前进。不过，您可以使用一些技巧将其短路:一旦您到达代表唯一路径的节点，您可以将整个字符串卡在该节点上。当您到达该节点时，您知道字符串的其余部分必须 是“findibulum”，因此您使用前缀来匹配整个字符串并返回它。

你如何使用它？在许多非 UNIX 命令解释器中，例如旧的 VAX DCL，您可以使用命令的任何唯一前缀。因此，ls(1) 的等价物是 DIRECTORY，但没有其他命令以 DIR 开头，因此您可以键入 DIR，这就像就像做整个词一样好。如果您不记得正确的命令，您可以只输入“D”，然后按(我认为)ESC； DCL CLI 会向您返回所有 以D 开头的命令，它可以非常快速地搜索这些命令。

关于c++ - 在基数树/patricia trie 中进行前缀搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/794601/

中进行前section的c++algorithmprefixpatricia-trie

有关c++ - 在基数树/patricia trie 中进行前缀搜索的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  6. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  7. ruby - Ruby 中的必应搜索 API - 2

    我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐