Regular expression generator/reducer?

0 votes
asked Jul 7, 2010 by joe

I was posed an interesting question from a colleague for an operational pain point we currently have, and am curious if there's anything out there (utility/library/algorithm) that might help automate this.

Say you have a list of literal values (in our cases, they are URLs). What we want to do is, based on this list, come up with a single regex that matches all of those literal items.

So, if my list is:

http://www.example.com
http://www.example.com/subdir
http://foo.example.com

The simplest answer is

^(http://www.example.com|http://www.example.com/subdir|http://foo.example.com)$

but this gets large for lots of data, and we have a length limit we're trying to stay under.

Currently we manually write the regexes but this doesn't scale very well nor is it a great use of anyone's time. Is there a more automated way of decomposing the source data to come up with a length-optimal regex that matches all of the source values?

7 Answers

0 votes
answered Jan 8, 2010 by mak

Taking the cue from the other two answers, is all you need to match is only the strings supplied, you probably better off doing a straight string match (slow) or constructing a simple FSM that matches those strings(fast).

A regex actually creates a FSM and then matches your input against it, so if the inputs are from a set of previously known set, it is possible and often easier to make the FSM yourself instead of trying to auto-generate a regex.

Aho-Corasick has already been suggested. It is fast, but can be tricky to implement. How about putting all the strings in a Trie and then querying on that instead (since you are matching entire strings, not searching for substrings)?

0 votes
answered Jul 7, 2010 by carl-smotricz

I think it would make sense to take a step back and think about what you're doing, and why.

To match all those URLs, only those URLs and no other, you don't need a regexp; you can probably get acceptable performance from doing exact string comparisons over each item in your list of URLs.

If you do need regexps, then what are the variable differences you're trying to accomodate? I.e. which part of the input must match verbatim, and where is there wiggle room?

If you really do want to use a regexp to match a fixed list of strings, perhaps for performance reasons, then it should be simple enough to write a method that glues all your input strings together as alternatives, as in your example. The state machine doing regexp matching behind the scenes is quite clever and will not run more slowly if your match alternatives have common (and thus possibly redundant) substrings.

0 votes
answered Jul 8, 2010 by mau

If you want to compare against all the strings in a set and only against those, use a trie, or compressed trie, or even better a directed acyclic word graph. The latter should be particularly efficient for URLs IMO.

You would have to abandon regexps though.

0 votes
answered Jul 1, 2011 by zwol

The Emacs utility function regexp-opt (source code) does not do exactly what you want (it only works on fixed strings), but it might be a useful starting point.

0 votes
answered Jul 8, 2012 by eric

An automatic generator for regular expression is available here. The tool has a web interface and uses Genetic Programming to generate regexes from a set of few examples: you can choose between a syntax ready for Java or JavaScript regex engines. It has been developed by our research group and has been presented at GECCO 2012 conference.

0 votes
answered Jul 22, 2012 by esl

Today I was searching that. I didn't found it, so I create a tool: kemio.com.ar/tools/lst-trie-re.php

You put a list on the right side, submit it, and get the regexp on the left one.

I tried with a 6Kb list of words, and produced a regexp of 4Kb (that I put on a JS file) like: var re=new RegExp(/..../,"mib");

Don't abuse of it, please.

0 votes
answered Sep 15, 2017 by serv-inc

An easy way to do this is to use Python's hachoir_regex module:

urls = ['http://www.example.com','http://www.example.com/subdir','http://foo.example.com']
as_regex = [hachoir_regex.parse(url) for url in urls]
reduce(lambda x, y: x | y, as_regex)

creates the simplified regular expression

http://(www.example.com(|/subdir)|foo.example.com)

The code first creates a simple regex type for each URL, then concatenates these with | in the reduce step.

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...