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.
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.