Create regex from samples algorithm

AFAIK no one have implemented an algorithm that takes a set of strings and substrings and gives back one or more regular expressions that would match the given substrings inside the strings. So, for instance, if I'd give my algorithm this two samples:

string1 = "fwef 1234 asdfd"
substring1 = "1234"

string2 = "asdf456fsdf"
substring2 = "456"

The algorithm would give me the regular expression "[0-9]*" back. I know it could give m开发者_如何学JAVAore than one regex or even no possible regex back and you might find 1000 reasons why such algorithm would be close to impossible to implement to perfection. But what's the closest thing?

I don't really care about regex itself also. Basically what I want is an algorithm that takes samples as the ones above and then finds a pattern in them that can be used to easily find the "kind" of text I want to find in a string without having to write any regex or code manually.

I don't have proof but I suspect no such discrete algorithm with a finite output could exist since you are asking for the creation of a regular language which could be "large" in respect to the input size.

With that, I suggest you peek at txt2re which can break down sample texts one-by-one and help you build regexes.

FlashFill a new feature of MS Excel 2013 would do exactly the task you want, but it does not give you the regular expression. It's a NP-complete problem and an open question for practical purposes. If you're interested in how to synthesise string manipulation from multiple examples, Go Flash Fill official website and read a few papers. They have pseudo-code and demo. movies as well.

There are many such algorithm in fact. This is a research area called "Grammatical inference".

I know RPNI, for example. (you could also look on the probabilistic branch, alergia, MDI, DEES). These algorithms generate DSA (Deterministic State Automata). In fact you absolutely don't need to enter the strings in your example. Only substrings.

There are also some algorithms to generate directly Non deterministic automata.

Of course, get the regular expression from an Non Deterministic Automata is easy.

The main ideas are simple:

Generate a PTSA (Prefix Tree State Automata) from your sample.

Then, you have to try to "merge" some states. From these merge, will emerge loops (i.e. * in the regular expression). All the difficulty being to choose the right rule to merge.

Here you go:

re = '|'.join(substrings)

If you want anything more general, your algorithm is going to have to make educated guesses about what type of strings are acceptable as matches, and it's trivial to demonstrate that no procedure can account for all possible sets of possible inputs without simply enumerating them all. For instance, consider some of these scenarios:

• Match all prime numbers
• Match hexadecimal strings, but no strings containing 'f' are in the sample set
• Match the same string repeated twice
• Match any even-length string

The root problem is that your question is incompletely specified. If you have a more specific requirement, that might be solvable, depending on what it is.