From: Joshua Ballanco <jballanc@...>
Date: 2009-10-15T19:22:01+09:00
Subject: Re: matching against a zillion patterns

On Oct 14, 2009, at 11:24 PM, George George wrote:

> i have some script in which i would like to match a string against
> 'many' regular expressions patterns.
>
> def group(string)
> if string=~ /pattern1 |patter2|pattern3|pattern(N)/  #where N =>100
>   group =1
> else
> ....
> end
> end
>
> My worry is the amount of patterns that i have (exceeding 400) and the
> efficiency and sanity of such an approach.What would you advice?

Regarding efficiency and sanity, I'd have to echo the previous  
responders that it depends a lot on what exactly you're trying to do.  
The one application that comes to mind where you'd have a large number  
of patterns to match is a parser. If you can redefine your problem so  
that it looks more like a parser, then that would open a whole world  
of potential solutions.

Just for fun, taking the simple case where your patterns are actually  
simple strings, one strategy would be to construct a tree from the  
patterns. I'll "borrow" the dataset from stocknames.info:

 > cat ./check_guest_list
#!/usr/bin/env ruby1.9

require "hpricot"
require "open-uri"

stock_names = open("http://stocknames.info") { |page| Hpricot(page) }
GUEST_LIST = stock_names.search("//li").map(&:innerHTML)

tree = {}
GUEST_LIST.each do |name|
   cur_leaf = tree
   name.each_char do |char|
     cur_leaf = cur_leaf[char] ||= {}
   end
   cur_leaf[:greeting] = "puts 'Hello, #{name}, welcome to the party!'"
end
print "Name please: "
guest = $stdin.gets.chomp

cur_leaf = tree
guest.each_char do |char|
   cur_leaf = cur_leaf[char]
   break unless cur_leaf
end

if cur_leaf
   eval cur_leaf[:greeting]
else
   puts "Sorry, you're not on the list."
end

 > ./check_guest_list
Name please: Josh Ballanco
Sorry, you're not on the list.

 > ./check_guest_list
Name please: Ed Vanders
Hello, Ed Vanders, welcome to the party!


Hope that helps some!

Cheers,

Josh