# Matching against a zillion patterns **URL:** \ **Category:** Ruby\ **Created:** [October 15, 2009, 8:24am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340 "2009-10-15T08:24:32Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 8:24am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/1 "2009-10-15T08:24:32Z")
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? Thank you. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 10:15am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/2 "2009-10-15T10:15:58Z")
George G. wrote: > 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? > > Thank you. Are the matches randomly distributed across the patterns? If not, perhaps you could arrange for the most common patterns in the first search, the next most common in a subsequent search and so on. Also recall that compiled regexps can be assigned to variables or constants, including arrays. Regards Steve. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 11:13am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/3 "2009-10-15T11:13:55Z")
2009/10/15 steve [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > end > > most common in a subsequent search and so on. > > Also recall that compiled regexps can be assigned to variables or constants, > including arrays. Yep, this could be used to do something like PATTERNS = { 1 =\> [/p1|p2|p3/, /p4|p5|p6/], 2 =\> [/p7|p8/], } def group(s) PATTERNS.each do |gr, pats| return gr if pats.any? {|rx| rx =~ s} # short circuit! end nil # or exception end Obviously you want the most frequent patterns in the beginning of arrays and the least frequent at the end. I’m not sure though about the sanity aspect of this. George, can you disclose more details about the nature of your matching? Maybe there’s a better and / or more efficient solution. Kind regards robert ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 11:35am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/4 "2009-10-15T11:35:50Z")
George G. wrote: > 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? I would advise you measure it, with your real regexp and your real data. I would expect that the regexp engine (written in C) would be much faster than something you could cobble together yourself in Ruby. Even 400 times “match C1, skip match C1, match C2, skip, match C1, …” in C will be very fast. Ideally, see if you can find a true regular expression engine that compiles to a DFA (deterministic finite state automaton). This will never backtrack, looking at each incoming character no more than once. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 11:20am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/5 "2009-10-15T11:20:57Z")
On Thu, Oct 15, 2009 at 8:24 AM, George G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > 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? Your mega-pattern will be quite slow if many strings doesn’t match any pattern, and even slower if many strings matches some patterns partially, since the regexp engine would end up backtracking a lot. Are you sure you can’t construct a more general pattern and test for values of the match data after? I find it hard to imagine 400 useful patterns without any similar structure. For example, GROUPS = { “somegroup” =\> 1, “othergroup” =\> 2 } if string =~ /^(\w+)\s+(\d+)$/ group = GROUPS[$1.downcase] end Another strategy is divide and conquer. See if you can group your patterns into groups that are similar and construct a more general regexp which use can use as a initial filter to determine which of the actual patterns you need to test against. E.g. if string =~ /superpattern1/ if string =~ /pattern1|pattern2|pattern3/ group = 1 end end if string =~ /superpattern2/ if string =~ /pattern4|pattern5|pattern6/ … ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 12:37pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/6 "2009-10-15T12:37:02Z")
Hi, Am Donnerstag, 15. Okt 2009, 15:24:35 +0900 schrieb George G.: > 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 How about this: p = [/a/, /b/, /c/] p.find { |q| “x” =~ q } #=\> nil p.find { |q| “a” =~ q } #=\> /a/ p.find { |q| “c” =~ q } #=\> /c/ Bertram ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 12:36pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/7 "2009-10-15T12:36:27Z")
Take a look at the ragel language and parser generator. You can generate your parser as a ruby c plugin. Ragel compiles to an DFA, deterministic finite automata, it does not look on a character twice. I got great success on a similar problem… [http://www.complang.org/ragel/](http://www.complang.org/ragel/) ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 12:48pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/8 "2009-10-15T12:48:45Z")
On Oct 14, 2009, at 11:24 PM, George G. wrote: > 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](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 ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 4:17pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/9 "2009-10-15T16:17:44Z")
2009/10/15 George G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > depending on which pattern the string contains. > Looks like this is tricky to become right. There seem to be some > people around that do bioinformatics, maybe some of them do have a > solution already. Things you could do off the top of my head: since it seems your patterns are only strings you could optimize the pattern by building a trie from it and then creating a RX from that. I’ve done this before (see below). Advantage is that your regular expression gets smaller and matching becomes more efficient (because of eliminated backtracking for NDA based RX engines). > **[Trie](https://en.wikipedia.org/wiki/Trie)** > > In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key. > Unlike a binary... There might be other options using one of the string matching algorithms around (boyer moore and the like). Kind regards robert def treeify(strings) root = TextTreeNode.new strings.each {|s| root.put s} root.to\_s end TextTreeNode = Struct.new :children, :char, :term do def initialize(chr = nil) self.char = chr self.children = Hash.new {|h,k| h[k] = self.class.new(k)} end def put(s) node = self s.each\_byte do |char| node = node.children[char] end node.term = true self end def to\_s dump(“”) end def dump(out) out \<\< Regexp.escape(char.chr) if char ch = children.values ``` unless ch.empty? first = ch.shift bracket = term || !ch.empty? out << "(?:" if bracket first.dump(out) ch.each do |v| out << "|" v.dump(out) end out << ")" if bracket out << "?" if term end out ``` end end puts treeify %w{foo fort bar baz battery} ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 4:16am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/10 "2009-10-16T04:16:03Z")
> Robert, let me disclose some more information about the nature of the > problem. Actually I have Protein sequences (strings of variable length > composed of a 20 letter alphabet) for example “CAARGNDLYSKNIG” can be > considered as a protein sequence. basically it’s just a string. Have you looked at the BioRuby project? They may have classes that can help. [http://bioruby.org/](http://bioruby.org/) ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 15, 2009, 1:12pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/11 "2009-10-15T13:12:34Z")
> I’m not sure though about the sanity aspect of this. George, can you > disclose more details about the nature of your matching? Maybe > there’s a better and / or more efficient solution. > > Kind regards > > robert Thank you so much for all the replies and suggestions! Robert, let me disclose some more information about the nature of the problem. Actually I have Protein sequences (strings of variable length composed of a 20 letter alphabet) for example “CAARGNDLYSKNIG” can be considered as a protein sequence. basically it’s just a string. In my case each of the strings that i have may fall into 2 distinct classes or groups depending on whether they match a collection of about 400 distict patterns in the first instance or another 200 or so patterns in the second instance. I do not have information on which is the most common pattern. To know which of the two groups that each of my sequences fall into, i resulted in to writing the code that i had presented ealier but realised that it may be inferior, inefficient or buggy and would like to improve it. I hope this helps to define the problem. In a nutshell; Given a set of strings A, each of which may belong to a group and where a group is characterised by a huge set of patterns(to be matched against), create a method that classifies each of the strings depending on which pattern the string contains. Thank you. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 6:59am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/12 "2009-10-16T06:59:12Z")
> Robert, let me disclose some more information about the nature of the > problem. Actually I have Protein sequences (strings of variable length > composed of a 20 letter alphabet) for example “CAARGNDLYSKNIG” can be > considered as a protein sequence. basically it’s just a string. I happen to be a molecular biologist myself, so this of course gets my attention 😉 I assume there is a particular reason why you are looking for sequence features using regexp? Because it seems somewhat inefficient - which of course got you here in the first place. There is no way that you can use distance measures of sequences to cluster them, for example (like Blast - MCL)? If you are looking to group your seqs, that is. Also, databases like ProDom do basically just that - looking for particular sequence features in protein sequences. Sure, they focus on domains, but depending of the nature of your regexps, their tools may be applicable regardless. Then there is the new CS-BLAST, which uses scoring matrices - which may perhaps be derivable from your regexps, dunno. Well I suppose I could offer more help if the idea behind this fishing-experiment was a little clearer (i.e. what is it that you want to find out). In any case, I suppose depending on your search space, ruby may really not be the ideal approach. Hope it works out in the end! ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 6:25am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/13 "2009-10-16T06:25:50Z")
Robert K. wrote: > 2009/10/15 George G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > > depending on which pattern the string contains. > > Looks like this is tricky to become right. There seem to be some > > people around that do bioinformatics, maybe some of them do have a > > solution already. > > Things you could do off the top of my head: since it seems your > patterns are only strings you could optimize the pattern by building a > trie from it and then creating a RX from that. I’ve done this before > (see below). Advantage is that your regular expression gets smaller > and matching becomes more efficient (because of eliminated > backtracking for NDA based RX engines). Thank you so much Robert! I have tried your approach and compressed the patterns to a single regular expression. (removed backtracking). Seems like a parser solution approach may also help. e.g. the one that Josh had illustrated Thomas, I have looked at bioruby and I regulary use it and relatively know it quite well, but we dont have a solution that i am aware of. I might repost this on the bioruby list, together with a reference to this thread. Thank you so much. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 8:23am UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/14 "2009-10-16T08:23:57Z")
Marc H. wrote: > I assume there is a particular reason why you are looking for sequence > features using regexp? Because it seems somewhat inefficient - which of > course got you here in the first place. There is no way that you can use > distance measures of sequences to cluster them, for example (like Blast > > - MCL)? First i cannot use any of the local alignment programs to do the clustering since my sequences are known to undergo lots of recombination, secondly i question the idea of BLAST BLOSUM matrices that have been derived from unbiased genomes. Am working with a pathogen that is famous for its high A/T content in its genome. Then why not use adjusted matrices? Yes we can, but then The high recombinations in the sequences renders that approach unusable. MCL is good for grouping proteins but also depends on pairwise local alignments and may be applicable for looking at unsupervised clustering or grouping. Secondly there is the issue of a relevant BLAST e-cut off as well as Inflation parameters to use with MCL.(Actually I have tried that approach already with diff’ I values) and we are analysing the results. > Also, databases > like ProDom do basically just that - looking for particular sequence > features in protein sequences. Sure, they focus on domains, but > depending of the nature of your regexps, their tools may be applicable > regardless. Their tools may be applicable but we already know the motifs that we are searching for and they are not in ProDom or swissprot domains. > Then there is the new CS-BLAST, which uses scoring matrices > > - which may perhaps be derivable from your regexps, dunno. Again BLAST and any alignment method for highly recombining sequences is not of much use. Instead we are using alignment free approaches to infer relationships in the sequences. The exact patterns that we have, are known(from our experimental evidence) to be associated with pathogenicity of a particular type and that is why am looking for exact matches. Else i could just have aligned the patterns and generated a HMM profile which i can again use to search in a generic way for the groups. Actually that is the next step. But first, I have opted to go for simple approaches first. > ruby may really not be the ideal approach > True Ruby may not be suited for some jobs and applications but again, so > is C++, java,php etc. The most important thing i think is the approach > and not the choice of programming language. Secondly i don’t like the > idea of black boxes that i don’t understand. 🙂 Please feel free to contact me at georgkam address hosted at google’s email domain. We don’t want to hijack this excellent mailing list that is meant for Ruby with molecular biology discussions. I have re-posted this thread to bioruby and we can discuss it there. For now Robert’s suggestion seems to have generated something that i wanted, a non redundant motif that is free from backtracking. Thank you. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 1:57pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/15 "2009-10-16T13:57:52Z")
2009/10/16 George G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > trie from it and then creating a RX from that. I’ve done this before > > (see below). Advantage is that your regular expression gets smaller > > and matching becomes more efficient (because of eliminated > > backtracking for NDA based RX engines). > > Thank you so much Robert! I have tried your approach and compressed the > patterns to a single regular expression. (removed backtracking). And what did it do to performance? How many patterns do you need now or were you able to squeeze everything into one? Kind regards robert ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 4:03pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/16 "2009-10-16T16:03:26Z")
Jan Arts approach to the problem. forwarded from the bioruby list; Hey George, So if I understand correctly you’ve got a huge number of aminoacid sequences (how many?) and about 400 regular expressions. And for each of the aminoacid sequences: if they match just one of the regular expressions they are put in box A and if they match none of the regexps, they go into box B. Correct? It just happens that something very similar was the subject of Jim Tisdall’s (from Beginning Perl for Bioinformatics fame) talk at the bioinformatics course we’re teaching at the moment 🙂 First thing: avoid loops. You don’t want to take loop over all regexps for each AA sequences, or the other way around. Are all regexps of the same length? Would be nice if they are, but not critical. My approach would be to go over the data just once. So suppose the regexps all are of the same length. A. Prepare your data: a. “Decode” the regexps into literal strings: e.g. /A[BC]D/ become “ABD” and “ACD”. b. Create a hash that contains all those things as keys. c. Concatenate all AA sequences together, joined with a non-AA, let’s say a semicolon “;”. E.g. CAARGNDLYSKNIG;GGARGNDLYSKNIG;KKARGNDLYSKNIG B. Do the actual search a. If the length of the strings to match (what used to be the regexps, and are now the keys in the hash) is 5: take the first 5 characters of your concatenated AA string and check if that substring exists as a key in the hash. If so: you know that the AA sequence between the surrounding “;” characters should go in box A. b. Advance 1 position: take AAs 2 to 6. c. Go back to a. You might have to tweak this approach to exactly fit your requirements, but if your code used to take a very long time, this might speed things up immensely. (George: can you forward this to the ruby mailing list it was discussed on initially? Cheers) Good luck, jan. ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 18, 2009, 2:08pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/17 "2009-10-18T14:08:42Z")
- Lars C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) (2009-10-15) schrieb: > Your mega-pattern will be quite slow if many strings doesn’t match any > pattern, and even slower if many strings matches some patterns > partially, since the regexp engine would end up backtracking a lot. Why would it do try to backtrack here? mfg, simon … l ---
**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\ **Post date:** [October 16, 2009, 9:37pm UTC](https://www.ruby-forum.com/t/matching-against-a-zillion-patterns/177340/18 "2009-10-16T21:37:23Z")
On 10/16/2009 08:23 AM, George G. wrote: > Please feel free to contact me at georgkam address hosted at google’s > email domain. We don’t want to hijack this excellent mailing list that > is meant for Ruby with molecular biology discussions. I have re-posted > this thread to bioruby and we can discuss it there. I don’t mind having the discussion on this list - the topic is really interesting and provides some insights into classes of problems we are rarely confronted with. > For now Robert’s suggestion seems to have generated something that i > wanted, a non redundant motif that is free from backtracking. Sounds good! I’m glad the approach proves useful. Cheers robert