Menu
Is it possible for a computer to "learn" a regular expression by user-provided examples?
To clarify:
Is it possible? Are there algorithms, keywords, etc. which I can Google for?
EDIT: Thank you for the answers, but I'm not interested in tools which provide this feature. I'm looking for theoretical information, like papers, tutorials, source code, names of algorithms, so I can create something for myself.
962
Short for regular expression, a regex is a string of text that lets you create patterns that help match, locate, and manage text. Perl is a great example of a programming language that utilizes regular expressions.
Regular expressions are very useful to programmers and can be used for a variety of tasks: Searching for strings, e.g. the word 'needle' in a large document about haystacks. Implementing a 'find and replace' function that locates a group of characters and replaces them with another group.
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation.
Yes, it is possible, we can generate regexes from examples (text -> desired extractions). This is a working online tool which does the job: http://regex.inginf.units.it/
Regex Generator++ online tool generates a regex from provided examples using a GP search algorithm. The GP algorithm is driven by a multiobjective fitness which leads to higher performance and simpler solution structure (Occam's Razor). This tool is a demostrative application by the Machine Lerning Lab, Trieste Univeristy (Università degli studi di Trieste). Please look at the video tutorial here.
This is a research project so you can read about used algorithms here.
Behold! :-)
Finding a meaningful regex/solution from examples is possible if and only if the provided examples describe the problem well. Consider these examples that describe an extraction task, we are looking for particular item codes; the examples are text/extraction pairs:
"The product code is 467-345A" -> "467-345A" "The item 789-345B is broken" -> "789-345B" An (human) guy, looking at the examples, may say: "the item codes are things like \d++-345[AB]"
When the item code is more permissive but we have not provided other examples, we have not proofs to understand the problem well. When applying the human generated solution \d++-345[AB] to the following text, it fails:
"On the back of the item there is a code: 966-347Z" You have to provide other examples, in order to better describe what is a match and what is not a desired match: --i.e:
"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z" The phone number is not a product id, this may be an important proof.
168
The book An Introduction to Computational Learning Theory contains an algorithm for learning a finite automaton. As every regular language is equivalent to a finite automaton, it is possible to learn some regular expressions by a program. Kearns and Valiant show some cases where it is not possible to learn a finite automaton. A related problem is learning hidden Markov Models, which are probabilistic automata that can describe a character sequence. Note that most modern "regular expressions" used in programming languages are actually stronger than regular languages, and therefore sometimes harder to learn.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
