I'm looking for the most efficient way to search a blob of text (± 1/2KB) for many regular expressions stored in an array.
Example code:
patterns = [/patternA/i,/patternB/i,/patternC/m,...,/patternN/i]
content = "Lorem ipsum dolor sit amet, consectetur... officiam id est laborum."
r = patterns.collect{ |pattern|
pattern unless ( content =~ pattern ).blank?
}.compact
Where r now contains patterns that matched the content string.
Solution 1
Do this:
r = patterns.select{|pattern| content =~ pattern}
Since the string is huge, it is better to implement this method on String rather then on something else because passing a large argument seems to be slow.
class String
def filter_patterns patterns
patterns.select{|r| self =~ pattern}
end
end
and use it like:
content.filter_patterns(patterns)
Solution 2
it has restrictions that each regex does not include a named/numbered capture.
combined_regex = Regexp.new(patterns.map{|r| "(?=[.\n]*(#{r.source}))?"}.join)
content =~ combined_regex
The following part will have problem if the regex inside patterns include a named/numbered capture. If there is a way to know for each regex how many potential captures there are, then it will solve the problem.
r = patterns.select.with_index{|pattern, i| Regexp.last_match[i]}
Addition
Given:
dogs = {
'saluki' => 'Hounds',
'russian wolfhound' => 'Hounds',
'italian greyhound' => 'Hounds',
..
}
content = "Running in the fields at great speeds, the sleek saluki dog comes from..."
you can do this:
combined_regex =
Regexp.new(dogs.keys.map{|w| "(?=[.\n]*(#{w}))?"}.join, Regexp::IGNORECASE)
content =~ combined_regex
r = patterns.select.with_index{|pattern, i| Regexp.last_match[i]}
"This article talks about #{r.collect{|x| dogs[x]}.to_sentence}."
=> "This article talks about Hounds."
To avoid outputs like This article talks about Hounds, Hounds and Hounds., you might want to put uniq in it.
"This article talks about #{r.uniq.collect{|x| dogs[x]}.to_sentence}."
If you are only interested in whether any of the patterns match the text, then consider combining all patterns into a single big regex, using the regex 'or' operator, and compiling that giant regex once.
For instance, if your patterns are: A, B, C, create a single regex of the form A|B|C
Sorry, I don't know Ruby, but hopefully you can turn that into code (:
Side Note: This is how Mercurial's .hgignore files are handled last I looked. In that case there are 1000s of filenames that get thrown at the one big regex, which is more efficient than those filenames getting thrown at each of hundreds of smaller regexes.
How about:
text = 'Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor magna'
targets = [ /(am?et)/, /(ips.m)/, /(elit)/, /(magna)/, /([Ll]or[eu]m)/ ]
regex = Regexp.union(targets)
hits = []
text.scan(regex) { |a| hits += a.each_with_index.to_a }
r = hits.select{ |w,i| w }.map{ |w,i| targets[i]} # => [/([lL]or[eu]m)/, /(ips.m)/, /(am?et)/, /(elit)/, /(magna)/]
This works to return the matched patterns in the order that the words were found in the text.
There's probably a way to do it using named-captures too.
What you want is exactly what a lexer has been designed to do. Pick out a set of regular expressions from an input stream with only a single pass over the input required.
Unfortunately I haven't been able to find a good lexer gem for Ruby which lets you define your own lexer. I'll update the answer if I find anything.
