Как получить строку и массив строк, как эффективно рассчитать вхождения массива в строку?

Question

Предположим, 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.

Я пришел с несколькими решениями, но ни одно из них меня не убедило.Любое предложение?

Answer 1

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

Answer 2

То, что вы делаете, это очень мини-версия поисковой системы. Ваши данные достаточно малы, вы можете просто пропустить их, разделить на пробелы для каждой строки, которую вы хотите найти. Когда ваш текст увеличивается до сотен страниц, это становится не так хорошо.

Есть некоторые сумасшедшие вещи, которые вы можете сделать, чтобы сделать это быстрее. Если вы посмотрите на исходный код для Lucene (http://lucene.apache.org/java/docs/index.html),, вы, вероятно, получите несколько подсказок ... так как это в основном то, для чего предназначен базовый режим для lucene (найти совпадения текста X в гигантском тексте Y). Внутренне я не на 100% конечно, что он делает, но я чувствую, что это что-то вроде сканирования всего гигантского текста и создания гигантских хеш-таблиц встречаемости и местоположения слов, так что он будет предварительно сканировать и составлять список каждого слова, которое может произойти ... и тогда вы можете очень быстро спросить, есть ли в тексте слово «dolor».

Answer 3

Это хорошо изученная проблема: сопоставление с множеством строк, из которых в литературе существует много хороших решений. Aho-Corasick предоставляет алгоритм прямого согласования в худшем случае (т.е. сложность выполнения O (| P | + | T |), где | P | - сумма длин всех строк, которые вы хотите сопоставить) и | T | длина текста, с которым вы сопоставляете). Алгоритм сопоставления оракулов с обратным множеством (SBOM) является примером хорошего алгоритма обратного сопоставления, который имеет O (| P | X | T |) сложность в наихудшем случае, но работает лучше, чем Aho-Corasick в среднем.

Answer 4

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

Я не уверен, насколько быстрое хэширование.