给定一个字符串和一个字符串数组，我如何有效地计算字符串中数组的出现？

我们假设text是一个字符串并包含一个文本。 tags是一个字符串数组。给定一个字符串和一个字符串数组，我如何有效地计算字符串中数组的出现？

text = <<-EOS 
Lorem ipsum dolor sit amet, consectetur adipisicing elit, 
sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. 
Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris 
nisi ut aliquip ex ea commodo consequat. 
Duis aute irure dolor in reprehenderit in voluptate velit 
esse cillum dolore eu fugiat nulla pariatur. 
Excepteur sint occaecat cupidatat non proident, 
sunt in culpa qui officia deserunt mollit anim id est laborum. 
EOS 

tags = [ "some", "in", "dolor", "laborum", "missing" ]

该算法应返回至少一次在text中包含的所有标签。在上面的示例中，

[ "in", "dolor", "laborum" ]

结果数组不需要排序。另外，我实际上并不需要知道text中每个标签的出现次数。

我带了几个解决方案，但他们都没有真正说服我。任何建议？

来源

2010-10-08 Simone Carletti

text.gsub!(/[[:punct:]]/,"").split 
p tags.select{|x| x if text.include?(x)}

来源

2010-10-08 12:25:25 ghostdog74

谢谢！这或多或少是我想到的相同算法。我的解决方案不是使用'.include？'和'.select'，而是利用Arrat'＆'交叉运算符来选择标签和文本中的常用元素作为数组。 – 2010-10-09 15:10:43

你在做什么是一个非常迷你的搜索引擎版本。您的数据足够小，您可以对其中的每个字符串进行查找，分割空间。随着文本长到100页，这变得不太好。

有一些疯狂的东西，你可以做得更快。如果你看Lucene的源代码（http://lucene.apache.org/java/docs/index.html），你可能会得到一些提示..因为这基本上是lucene的基本模式（查找巨大文本Y中的文本X的匹配）。在内部，我不是100％确定它的功能，但我觉得这是沿着扫描整个巨型文本的方式，以及构建巨大的单词出现和位置的哈希表。因此，它会预先扫描并建立可能发生的每个单词列表......然后，如果文本中出现“dolor”，您可以很快问到它。

来源

2010-10-08 12:22:41 bwawok

hsh = {} 
text.gsub(/[[:punct:]]/,"").split.each {|t| hsh[t]=true} 
tags.select{|x| hsh.has_key?(x)}

我不知道哈希有多快。

来源

2010-10-08 12:57:30 Reactormonk

这是一个很好研究的问题：多字符串模式匹配，其中许多好的解决方案存在于文献中。 Aho-Corasick提供了最坏情况下的最优前向匹配算法（即O（| P | + | T |）的执行复杂度，其中| P |是你想匹配的所有字符串的长度之和）和| T |是你匹配的文本的长度）。后置预处理匹配（SBOM）算法是一个好的后向匹配算法的例子，它具有O（| P | X | T |）最差的情况下的复杂度，但平均比Aho-Corasick执行得更好。

来源

2010-10-09 18:47:11 fritzv

给定一个字符串和一个字符串数组，我如何有效地计算字符串中数组的出现？

回答

相关问题