These regex's are generated with genetic programming techniques, so they are not guaranteed to be an optimal solution, just a good (by the metric of working) one.
Applying some fairly simple optimizations to my example result I get the following equivalent regular expression:
\d{2}[\d\.]{3,}
which isn't too bad.EDIT: Here are the optimizations:
The original:
(?:\d\d[\d\d\.\d\.][\d\.](?:(?=([\d\.]+))\1))
1. Remove non-capturing groups and lookahead: \d\d[\d\d\.\d\.][\d\.]([\d\.]+)\1
2. Simplify set: \d\d[\d\.][\d\.]([\d\.]+)\1
3. Remove redundant backreference: \d\d[\d\.][\d\.][\d\.]+
4. Combine duplicates: \d{2}[\d\.]{3,}Putting it another way, your highly optimized version (4) is likely to be much more brittle to small 'defects' than (1).
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.
I also wasn't trying to say those simplifications should be applied between iterations of the algorithm, only at the end.
Not only are the expressions tending to get more accurate with each generation, but their degree of 'evolvability' is also being selected for.
- find "small" regex that defines the language for the example — hard problem
- minimize the regex (the language stays the same) — can be solved efficiently
See the link from http://news.ycombinator.com/item?id=4682623
It's also got a useless non-capturing group and lookahead.