Re:Automatic Generation of Regular Expressions from Examples
by khafra on Monday October 22, 2012 @02:20PM
(#4684554)
Actually, the last point can be overstated, because the optimizations he applied created a functionally equivalent state machine to the non-optimized version. If it overfitted, the original GA-generated algorithm overfitted as well.
Re:Automatic Generation of Regular Expressions from Examples
by tlrobinson on Monday October 22, 2012 @03:09PM
(#4684882)
My "optimizations" were trivial, in that they don't change the behavior of the regex at all, they just simplify it. As khafra points out, they are equivalent.
I also wasn't trying to say those simplifications should be applied between iterations of the algorithm, only at the end.
Re:Automatic Generation of Regular Expressions from Examples
by mdda on Monday October 22, 2012 @06:24PM
(#4685867)
Understood - and I was just making the observation that the expressions produced during the process were junky in a way that's characteristic of the way they are evolving : Mixing together two honed expressions would produce much more extreme deviations in 'children' than the offspring of two of these hairy expressions.
Not only are the expressions tending to get more accurate with each generation, but their degree of 'evolvability' is also being selected for.
For example, given training data 000001 000002 000003 000004
The "optimized" version would be \d+[1-4]
If the goal was simply to find the smallest regex that matches all the training data, that's trivial to code, NP-hard to execute.
But the goal isn't to find the smallest regexp, it's to find a "good" regexp.