Узнайте, какие слова в большом списке встречаются в маленькой строке

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 (Сэм + Джек + Фред + Фред)
для части (2) выражение будет возвращать «Сэм Джек Фред»
и часть (3) составляет 3

«Рубиновый способ» сделать это ускользает от меня через 4 часа ... с итерацией это достаточно просто (но медленно). Любая помощь будет оценена!

Answer 1

Вот альтернативная реализация, для вашего назидания:

def match_freq( words, str )
  words  = words.split(/\s+/)
  counts = Hash[ words.map{ |w| [w,str.scan(w).length] } ]
  counts.delete_if{ |word,ct| ct==0 }
  occurring_words = counts.keys
  [
    counts.values.inject(0){ |sum,ct| sum+ct }, # Sum of counts
    occurring_words,
    occurring_words.length
  ]
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)
p x   #=> [4, ["fred", "sam", "jack"], 3]

Обратите внимание, что если бы мне понадобились эти данные, я бы, вероятно, просто возвратил хэш 'counts' из метода, а затем сделал бы любой анализ, который мне нужен,Если бы я собирался вернуть несколько «значений» из метода анализа, я мог бы вернуть хэш именованных значений.Хотя, возвращая массив, вы можете убрать результаты:

hits, words, word_count = match_freq(list1, str)
p hits, words, word_count  
#=> 4
#=> ["fred", "sam", "jack"]
#=> 3

Answer 2

Вот мой шанс:

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 - это размер входной строки, я не думаю, что вы можете сделать это лучше (в терминах big-oh).Но есть меньшие оптимизации, которые могут окупиться, как сохранение отдельного счетчика для общего числа совпадений, а не вычисление его впоследствии.Это был только мой быстрый взлом.

Вы можете извлечь только соответствующие слова из вывода следующим образом:

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

Обратите внимание, что порядок не будет сохранен обязательно, если этоважно, чтобы вы вели отдельный список порядка, в котором они были найдены.

Answer 3

Для более быстрых регулярных выражений , используйте https://github.com/mudge/re2. Это рубиновая оболочка для Google re2 https://code.google.com/p/re2/