News for hackers. Stuff that matters.
Re:Automatic Generation of Regular Expressions from Examples by reader5000 on Monday October 22, 2012 @08:22AM (#4682802)
Instead of randomized hill-climbing (genetic programming's search algo) why not try a little A*?
Re:Automatic Generation of Regular Expressions from Examples by sunir on Monday October 22, 2012 @09:03AM (#4682914)
How would you envision that working? What is the estimated distance function?
Re:Automatic Generation of Regular Expressions from Examples by DasIch on Monday October 22, 2012 @01:02PM (#4684120)
The "distance" of a regular expression could be the specifity (think CSS) or the size of the language described by the regular expression (with some adjustments to account for repetition as a* being infinite is probably not what is intended.)

The real problem is that the space of possible solutions is very large, so you will have to do that lazily, which would make an implementation in a lot of languages rather annoying.

I'd also expect this algorithm to be biased towards regular expressions that are more specific than the user intended them to be, especially for example sets that are small or not very diverse.

Re:Automatic Generation of Regular Expressions from Examples by __alexs on Monday October 22, 2012 @04:00PM (#4685198)
Is a* more or less infinite than .*?
Re:Automatic Generation of Regular Expressions from Examples by DasIch on Tuesday October 23, 2012 @01:09PM (#4689031)
I intended `a` to mean `a` repeated zero or more times, meaning that `a` defines a language of infinite size as there are an infinite number of strings that match that grammar.
Re:Automatic Generation of Regular Expressions from Examples by krallja on Monday October 22, 2012 @04:24PM (#4685333)
Re:Automatic Generation of Regular Expressions from Examples by __alexs on Tuesday October 23, 2012 @04:18AM (#4687062)
Re:Automatic Generation of Regular Expressions from Examples by songgao on Monday October 22, 2012 @10:11AM (#4683191)
The searching space is too large - there are too many combinations to search for. Genetic Programming makes it faster to get a good solution. The solution might not be the optimal one, but it's good enough :-)