7 ms·
Generate Regex from Examples
- captn3m0 11y agoI've been looking for tools that would help me do this. Are there any interesting datasets that you have converted to regexes with this? Zipcodes would be something I'd like to see available as regexes.
- aaronem 11y agoI can't load the site, so I'm not sure exactly what it's offering, but I'm also not sure what you mean by a regex for zipcodes. Surely it'd be simpler, quicker, and more maintainable just to match /(\d{5})/ and filter out invalid codes after the fact? (Edit: If you want the full ZIP+4 where it's given, you can add (\-\d{4})? as a term in the regex, and you can validate them the same way. USPS also offers an API for validating address information; it's been some years since I used it, and I recall it being somewhat recondite in the fashion of most .gov APIs, but it's there and it works.) Edit again: OK, the site loaded. It looks like a tool for generating regexes via machine learning techniques to match highly complex targets. From a purely technical perspective, that sounds really neat -- but from a maintainability perspective, it sounds like even more of a nightmare than complex regexes usually are.
- atomwaffel 11y agoThe GeoNames Country Information table has a "Postal Code Regex" column that you might find interesting: http://download.geonames.org/export/dump/countryInfo.txt http://download.geonames.org/export/dump/countryInfo.txt
- aaronem 11y agoSome of those regexes are terrifying. Granted that I'm not sure there is any better alternative for extracting structured address information from an unstructured source, but...
- malditojavi 11y agoLooks promising if the title matches what it does - but page does not load.
- dewey 11y agoArchived site, seems to be down right now: https://archive.is/J8MIR https://archive.is/J8MIR
- Retr0spectrum 11y agoWhat regex does it generate for the inputs shown on that page?
- riffraff 11y agoThe scholarly articles behind this: Automatic Generation of Regular Expressions from Examples with Genetic Programming[0] Automatic String Replace by Examples [1] [0] http://machinelearning.inginf.units.it/publications/international-conference-publications/automaticgenerationofregularexpressionsfromexampleswithgeneticprogramming http://machinelearning.inginf.units.it/publications/internat... [1] http://machinelearning.inginf.units.it/publications/international-conference-publications/automaticstringreplacebyexamples http://machinelearning.inginf.units.it/publications/internat...
- thomasahle 11y agoA nice discussion on the hardness of finding regular expressions from examples: http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/ http://cstheory.blogoverflow.com/2011/08/on-learning-regular... . One interesting point: A good such system could easily break RSA.
- mimmuz 11y agohi guys, thank you for your interest in our system of automatic generation of regex. we are experiencing some trouble with connectivity due to the... unexpected popularity :) we are working to solve this, but we are a very small research group with limited resources. meanwhile, if you are interested in the details of our algorithm take a look at the source code hosted here: https://github.com/MaLeLabTs/RegexGenerator https://github.com/MaLeLabTs/RegexGenerator
- chavo-b 11y agowhy the resulting regex contains ++ instead of only one + ? such regexs are wrong!
- logn 11y ago"Possessive quantifiers are a way to prevent the regex engine from trying all permutations. This is primarily useful for performance reasons. You can also use possessive quantifiers to eliminate certain matches." http://www.regular-expressions.info/possessive.html http://www.regular-expressions.info/possessive.html
- chavo-b 11y agook, tnx, now it makes sense
- quinta 11y agocrossposted here: https://news.ycombinator.com/item?id=4682545 https://news.ycombinator.com/item?id=4682545
- ExpiredLink 11y ago... 1006 days ago.
- ftarlao 11y ago... in order to be fair we have recently updated the engine and webinterface; the new application is a big step forward, the same URL but a totally different thing. The older tool is here, http://regex.inginf.units.it/extract/ http://regex.inginf.units.it/extract/
- amelius 11y agoI can't test it right now (site down), but I assume that if I give it the examples 1, 2, 23, 512, 461, 781, it will come up with the regular expression ([0-9]+). However, it could also have come up with the rule ([0-8]*). So how does it know which one to choose? Can one also submit counter-examples?
- mimmuz 11y agothe system tries to generalize, so probably it choose something like \d+ (it is shorter)
- nothrabannosir 11y agoDepending on unicode settings, \d != [0-9]. See: http://stackoverflow.com/a/6479605/4359699 http://stackoverflow.com/a/6479605/4359699
- deleted 11y ago[deleted]
- SnaKeZ 11y agoI tried your dataset (exported in JSON): http://pastebin.com/7XU2UfEd http://pastebin.com/7XU2UfEd The result is: \d
- mimmuz 11y agoSome negative examples can help (it is designed to perform a text extraction)
- jlarocco 11y agoThis can't really work 100% without exhaustively giving every string accepted by the regex, or giving every string not accepted by the regex. Regular expressions are essentially a shorthand for doing that. Since it's impossible to do accurately, it has to use some "common sense" via genetic programming or whatever. In your example, it probably sees that people rarely want [1-8]{1,3}, but that it's a subset of \d+ and goes with that instead.
- kordless 11y agoSounds like the Universal Field Extractor: https://splunkbase.splunk.com/app/494/ https://splunkbase.splunk.com/app/494/
- brudgers 11y agoGiven example strings: {a, b, c, d} The most restrictive regular expression is: a | b | c | d The most permissive regular expression is: * If the system produces anything in between I cannot predict the output without knowing a set of rules that are more complicated than the regular expression that the system of rules produces. TANSTAAFL.
- mimmuz 11y agothe system requires also negative examples
- brudgers 11y agoNegative examples do not change the most restrictive regular language. It remains the union of the accepted strings. Negative examples constrain the most permissive interpretation to the regular language defined: 1a. Let NegativeExamples be the most restrictive regular expression [as above] using the negative examples as input. or 1b. Let NegativeExamples be the most permissive regular expression [as above] using the negative exmaples as input. 2. Let U be the regular language defined by the kleene star. The negative examples define the regular language: U - NegativeExamples And depending on the choice of 1a or 1b, you get a regular language slightly more restricted than the kleene star or the empty language. Regular expressions are a compact way of precisely describing an enumeration of permutations. The only way to get equal precision via enumeration is to fully enumerate all the permutations. Once a parser gets into the picture, then the input strings have to have semantics that the parser can use and a hidden set of parser rules for interpreting those semantics.
- mimmuz 11y agoI do not understand the point. Really. My limit... Or you misunderstood the purpose of the automatic regex generator.
- brudgers 11y ago[skipping wikipedia links] Formally, regular expressions describe finite automata. A finite automata is a state machine that accepts a language. Hence, a regular expression defines a language [and in particular a regular language]. Regular languages have closure properties, which is to say that under certain operations two regular languages produce another regular language, and therefore certain operations on regular expressions can produce another regular expression. The regular expression generator takes some input and produce a regular expression. There are two possible scenarios: 1. Treat the input as one or more regular languages and perform only closed operations. 2. Treat the input as some other type of language, e.g. a context free language and parse the input according to the rules of that language to produce a regular expression. The first option means that we can determine the output of the regular expression generator by knowing only one rule: is does it generate regular expressions starting by adding to the empty language or by difference from the kleene star. But there is still ambiguity that requires we have knowledge about the internal workings of the expression generator. The second option means that in order to determine what output a given input will produce we have to know about a potentially unlimited number of rules (and these rules may change dynamically based on the input)[1]. What this means is that no regular expression generator is generally useful as a black box. Ambiguity assures it, and ambiguity is intrinsic because the regular expression generator must treat the input as within a more complex language (e.g. context free) and force it into the simpler class of regular languages. As my analysis shows, the way in which the regular expression generator interprets the input is arbitrary. If you're really interested in the topic, Jeff Ulman (who with Alfred Aho wrote the book on automata) teaches a course on automata via Coursera. Rumor (well actually an email) has it that he is teaching it again this fall. A person could do worse than learning about automata from a person down a Stanford hallway from Donald Knuth's office. Even cooler is that Jeff Ullman shows up in class to discuss questions (which is probably why the course only comes around once a year). https://www.coursera.org/course/automata https://www.coursera.org/course/automata Just because lunches cannot be free doesn't mean they can't be cheap. [1] Moreover, via the Halting Problem we cannot be certain that the regular expression generator will produce any output at all.