|Perl: the Markov chain saw|
Re: string match using with an N in any positionby Marshall (Monsignor)
|on Nov 18, 2011 at 03:08 UTC||Need Help??|
There are a number of ways to proceed. I would consider a dynamic regex. Bascially write a little subroutine that writes the regex! /^$regex/ where $regex winds up being something like: "NCGAT|GNGAT|GCNAT|GCGNT|GCGAN".
You can use substr or whatever in the code that lists out the combinations. When the regex engine compiles this automagically built regex, it can deal with it very efficiently even if there are a lot of "OR" terms because there isn't any backtracking or forward looking or anything fancy.
So I am suggesting: think simple regex that is program generated. Oh, I don't see any reason for the search patterns to be in hash keyed by a sequential number, why not just have an array?
Update: I saw BrowserUk's solution and I like it. I wasn't aware that you could calculate the XOR byte by byte of 2 strings in a single Perl operation. Cool. There are some approximate pattern matching algorithms (eg agrep) where this is useful and the manner in which BrowserUk is using the XOR function is apropos.
Perl has made some very significant enhancements to the regex engine as of late. I am still on Perl 5.10. What I am wondering (I don't know the answer) is how sophisticated the regex compiler has become in 5.14 and what its optimization points are. For example if the data to matched against starts with 'C', then none of the optional patterns will ever match and all of the rest of the calculations become irrelevant - first character isn't a 'G' or 'N' so: stop! If it does that then the result is likely to be faster than the procedure of XOR'ing the strings together and going thru the resultant XOR produced string to count the 0's (fewer character by character operations get done on average vs a smarter "give up early" strategy..well maybe..).
What I am suggesting is that if performance matters, benchmarking is definitely in order!
I have used the above algorithm in other situations where for example certain character positions can be swapped and others not. The requirement described in the OP is at the lower limit of what this "write a program to write a program" approach can do (the regex is essentially a program that is compiled by the regex engine at run time). Next year I am going to attempt a performance increase on my regex writing code - I'll report back if I find something particularly stunning.