ruby - 找出大列表中的哪些单词出现在小字符串中

Question

我有一个静态的“大”单词列表，大约 300-500 个单词，称为“list1”

给定一个比较短的字符串str，大约40个单词，ruby中最快的获取方法是什么:

1. list1中的单词在str中出现的次数(计算多次出现)
2. list1 中的单词在字符串 str 中出现一次或多次的列表
3. (2)中的单词数

str 中的“出现”表示 str 中的整个单词，或 str 中单词的部分。因此，如果 'fred' 在 list1 中并且 str 包含 'fred' 和 'freddie' 那将是两个匹配项。

一切都是小写的，所以任何匹配都不必关心大小写。

例如:

list1 ="fred sam sandy jack sue bill"
str = "and so sammy went with jack to see fred and freddie"

所以 str 包含 sam、jack、fred(两次)

对于第 (1) 部分，表达式将返回 4 (sam+jack+fred+fred)
对于第 (2) 部分，表达式将返回“sam jack fred”
第(3)部分是3

4 小时后，我无法使用“ruby 方式”来执行此操作...通过迭代它很容易(但速度很慢)。任何帮助将不胜感激!

Answer 1

这是我的尝试:

def match_freq(exprs, strings)
  rs, ss, f = exprs.split.map{|x|Regexp.new(x)}, strings.split, {}
  rs.each{|r| ss.each{|s| f[r] = f[r] ? f[r]+1 : 1 if s=~r}}
  [f.values.inject(0){|a,x|a+x}, f, f.size]
end

list1 = "fred sam sandy jack sue bill"
str = "and so sammy went with jack to see fred and freddie"
x = match_freq(list1, str)
x # => [4, {/sam/=>1, /fred/=>2, /jack/=>1}, 3]

“match_freq”的输出是您的输出项 (a,b,c) 的数组。算法本身是 O(n*m)，其中 n 是 list1 中的项目数，m 是输入字符串的大小，我不认为你能做得比这更好(就大哦而言)。但是有一些较小的优化可能会有所返回，例如为匹配总数保留一个单独的计数器而不是事后计算它。这只是我的快速技巧。

您可以只从输出中提取匹配的词，如下所示:

matches = x[1].keys.map{|x|x.source}.join(" ") # => "sam fred jack"

请注意，顺序不一定会保留，如果这很重要，您必须保留一个单独的列表，列出它们被发现的顺序。