Automatic Generation of Regular Expressions from Examples

http://regex.inginf.units.it/

by ColinWright • 14 years ago

170 59 14 years ago

regex.inginf.units.it

wib• 14 years ago

Cool & handy

"When there are less than 200 examples, the training set and validation set have the same size. Otherwise, the training set is composed of 100 examples and the other examples constitute the validation set."

Why divide the data into sets like that? Assuming the sample data is representative, wouldn't it be better to use much more for training, say 90% with 10% for validation?

haffi112• 14 years ago

Then you might have the problem of over-fitting the training set.

See here for example: http://en.wikipedia.org/wiki/Overfitting

StavrosK2• 14 years ago

You use the validation set precisely to avoid overfitting. I agree that a 90/10 split would be more reasonable.

msellout• 14 years ago

More training data helps prevent overfitting.

Cyranix• 14 years ago

The other replies, directly discussing overfitting, are spot on. However, I did want to point out explicitly that the stated assumption of representative sample data can be a fundamental challenge, not to be taken lightly.

superasn• 14 years ago

Sounds neat, but unfortunately it isn't working with a "Server is busy!" error.

songgao2• 14 years ago

I wonder why the GP has to be running at server side, rather than in JavaScript in the browser.

mistercow• 14 years ago

It certainly does not have to be running on the server side. I'm guessing that it's just a matter of what environment the creator was comfortable with.

a3_nm2• 14 years ago

Interestingly, there is much to say about the theoretical problem of finding the smallest regular expression for a set of positive and negative examples. A nice overview: http://cstheory.blogoverflow.com/2011/08/on-learning-regular...

tlarkworthy• 14 years ago

The sledge hammer approach.

vineet• 14 years ago

There is a related cool system: http://groups.csail.mit.edu/uid/lapis/

It is actually a text editor, and doesn't come up with Regular Expressions but similar textual constraint patterns.

RyanMcGreal• 14 years ago

I can see how this supports TDD. Write a test suite and it will generate a regex that passes it.

ajanuary• 14 years ago

I can't find it now, but I've read about projects generating haskell code from unit tests. Anyone got links?

IsTom• 14 years ago

I don't know about generating code from unit tests, but there's Djinn for generating code from type signatures.

egonschiele• 14 years ago

Do you mean QuickCheck? http://www.haskell.org/haskellwiki/Introduction_to_QuickChec...

reader5000• 14 years ago

Instead of randomized hill-climbing (genetic programming's search algo) why not try a little A*?

sunir• 14 years ago

How would you envision that working? What is the estimated distance function?

DasIch2• 14 years ago

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.

songgao2• 14 years ago

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 :-)

jcromartie• 14 years ago

Slightly off-topic: I was surprised to see a ".it" domain that was actually Italian.

Ecio78• 14 years ago

It's an italian university, Università degli Studi di Trieste (northeast of Italy): http://www.units.it/

ExpiredLink• 14 years ago

More off-topic: I wonder why 'interesting' top-level domains like '.it' or '.at' aren't used more frequently to create 'interesting' domain names.

Edit: you.get.it

dwwoelfel• 14 years ago

They're hard to register and cost more. I registered http://canhekick.it through iwantmyname.com after someone snatched up canhekickit.com. It cost me $30 instead of $10.

josephagoss• 14 years ago

Is there any chance to look at the code (application)? I'd be interested in running this locally as I have a need for generation of regular expressions.

coroxout• 14 years ago

I look forward to trying this once the HN server overload effect has worn off.

This is something I would have found useful a year or two ago, considered writing, and decided it would be impossible to get a usefully generalised regex. I'm glad people cleverer and less defeatist than me had the same idea, since it seems it is possible to get useful results after all :)

csmatt2• 14 years ago

I attempted writing something similar when I was bored at work a year ago. I soon discovered how difficult this problem actually is. It's definitely beyond afternoon hacking. I'd love to get a peek at the secret sauce!

a3_nm2• 14 years ago

There is a paper which explains how it works: http://mllab.inginf.units.it/publications/international-conf...

Note that there are other (non-genetic) approaches to learn regular expressions (some are cited in the above paper).

csmatt2• 14 years ago

Thanks for the link. I've been meaning to get into machine learning and this sounds like a good, tractable problem to start with.

draegtun• 14 years ago

For the reverse of this see HN discussion Given a list of regexes, generate all possible strings that matches all of them - http://news.ycombinator.com/item?id=2579783

tlrobinson3• 14 years ago

This is cool, but it doesn't look like it's doing even trivial optimizations...

    (?:\d\d[\d\d\.\d\.][\d\.](?:(?=([\d\.]+))\1))

"[\d\d\.\d\.]" is equivalent to "[\d\.]", right?

It's also got a useless non-capturing group and lookahead.

merlincorey• 14 years ago

You have apparently useless genes in your genetic code as well.

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.

tlrobinson3• 14 years ago

You're right, I was just pointing out that with some basic optimizations you could get a much cleaner result.

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,}

d0mine• 14 years ago

You could consider it 2 step process:

  - 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

enraged_camel3• 14 years ago

I keep getting "server busy". Why share a link if it won't be able to handle the traffic?

ColinWright4• 14 years ago

So, every time you share a link, you always test it first to see if it can handle the load?

Ah, no, looking at your profile you haven't yet ever shared a link. I can only conclude that you find lots and lots of things that you are eager to share with us, but when you rigorously test them you find that they can't handle the load, so you sadly decline to submit them.

Thanks for the feedback. I'll be sure to keep it in mind.

enraged_camel3• 14 years ago

This is a community for geeks. I believe it is a realistic expectation that one should be wary of sharing with tens of thousands of readers sites that run processor-intensive server-side scripts.

(Nice ad hominem, by the way.)

pathikrit• 14 years ago

Funnily, I had asked this question awhile back on StackOverflow: http://stackoverflow.com/questions/4880402/

jmmcd• 14 years ago

Sumit Gulwani of Microsoft Research has a non-genetic programming approach to this and similar problems, which is interesting to compare: http://dl.acm.org/citation.cfm?doid=2240236.2240260

arekp• 14 years ago

This makes me think. In 2012 people still think that genetic programming, a numerical optimization technique (and not the most efficient one), magically solves random machine learning problems.

drblast• 14 years ago

More efficient techniques, such as?

It would be interesting for me and others here to learn from what you know rather than be left with what you wrote.

bartolialberto• 14 years ago

I am the "boss" of the research group that put the regex generator tool on line (http://machinelearning.inginf.units.it/ "Data and tools"): we are all VERY SORRY for any inconvenience we may have created.

We simply did not expect so much interest in our work. Yesterday we received more than 11000 visits. We are not prepared to handle such traffic.

We are working toward adding a few more CPUs and will notify the status on our Twitter account: http://twitter.com/@MaleLabTs.

We are afraid we will not be able to fully solve the overload problem anytime soon, though. We are a small research group, with scarce resources.

We are also preparing a small faq for addressing several of the interesting points raised in this discussion (e.g., why not executing everything in Javascript ?). We will notify completion via Twitter. Further comments and criticisms are most welcome.

Thanks a lot for your interest and patience.

ColinWright4• 14 years ago

That's a useful response - thanks for taking the time to register and respond.

Apologies for the extreme load caused - when geeks find something cool they tend to share it, and not everyone is ready for that level of interest.

I, for one, look forward to your updates. What would be really great would be for you to prepare some kind of informal overview and put that up as a blog post, making it clear that it's intended to be informal, and is not in any way your formal research results or anything like that. Then post here a link to it. If you engage with this community you'll get a lot of smart people offering thoughts and suggestions from which you can pick and choose.

Great work - thank you.

Automatic Generation of Regular Expressions from Examples

Related Stories