12

How would one efficiently match one input string against any number of regular expressions?

One scenario where this might be useful is with REST web services. Let's assume that I have come up with a number of URL patterns for a REST web service's public interface:

  • /user/with-id/{userId}
  • /user/with-id/{userId}/profile
  • /user/with-id/{userId}/preferences
  • /users
  • /users/who-signed-up-on/{date}
  • /users/who-signed-up-between/{fromDate}/and/{toDate}
  • …

where {…} are named placeholders (like regular expression capturing groups).

Note: This question is not about whether the above REST interface is well-designed or not. (It probably isn't, but that shouldn't matter in the context of this question.)

It may be assumed that placeholders usually do not appear at the very beginning of a pattern (but they could). It can also be safely assumed that it is impossible for any string to match more than one pattern.

Now the web service receives a request. Of course, one could sequentially match the requested URI against one URL pattern, then against the next one, and so on; but that probably won't scale well for a larger number of patterns that must be checked.

Are there any efficient algorithms for this?

Inputs:

  • An input string
  • A set of "mutually exclusive" regular expressions (ie. no input string may match more than one expression)

Output:

  • The regular expression (if any) that the input string matched against.
stakx - no longer contributing
  • 83,039
  • 20
  • 168
  • 268

5 Answers5

13

The Aho-Corasick algorithm is a very fast algorithm to match an input string against a set of patterns (actually keywords), that are preprocessed and organized in a trie, to speedup matching.

There are variations of the algorithm to support regex patterns (ie. http://code.google.com/p/esmre/ just to name one) that are probably worth a look.

Or, you could split the urls in chunks, organize them in a tree, then split the url to match and walk the tree one chunk at a time. The {userId} can be considered a wildcard, or match some specific format (ie. be an int).

When you reach a leaf, you know which url you matched

Savino Sguera
  • 3,522
  • 21
  • 20
  • is there a C++ implementation of that by any chance? – nurettin Oct 28 '13 at 05:51
  • 1
    http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm has links to a few implementations. I remember http://sourceforge.net/projects/snort/ had an implementation in C somewhere, but that was many years ago, I could be wrong. – Savino Sguera Oct 29 '13 at 09:57
  • 1
    I found google's re2 library can match regexes using Aho-Corasick algorithm – nurettin Oct 29 '13 at 10:31
  • @nurettin Can you please reference where it is said that RE2 uses Aho-Corasick algorithm? I am unable to find such mentions in their repository or elsewhere. – Roland Pihlakas Jan 29 '22 at 10:54
  • 1
    @RolandPihlakas I don't remember why I mentioned Aho-Corasick 9 years ago. I must have been confused. I don't see such an implementation in re2. – nurettin Jan 29 '22 at 11:57
5

The standard solution for matching multiple regular expressions against an input stream is a lexer-generator such as Flex (there are lots of these avalable, typically several for each programming langauge).

These tools take a set of regular expressions associated with "tokens" (think of tokens as just names for whatever a regular expression matches) and generates efficient finite-state automata to match all the regexes at the same time. This is linear time with a very small constant in the size of the input stream; hard to ask for "faster" than this. You feed it a character stream, and it emits the token name of the regex that matches "best" (this handles the case where two regexes can match the same string; see the lexer generator for the definition of this), and advances the stream by what was recognized. So you can apply it again and again to match the input stream for a series of tokens.

Different lexer generators will allow you to capture different bits of the recognized stream in differnt ways, so you can, after recognizing a token, pick out the part you care about (e.g., for a literal string in quotes, you only care about the string content, not the quotes).

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • +1, even though I have one issue with this solution, namely that all patterns must be pre-processed by an *external* tool, which might make changing one's own program's configuration a more complicated process. Of course one could replicate the behaviour of `lex`/`flex` etc. in one's one program, but that might be a bit of overkill. – stakx - no longer contributing Aug 14 '11 at 10:21
  • @stakx: if you want high efficiency, a lexer generator is the answer. If you don't want the rebuild price, yes, you have to replicate this yourself (or pick a language with a library that has it built in, I believe Java's regex does this). For your posed example of RESTful services, I don't see that the build complexities with an external lexer add any real difficulty: it adds just one more step to your build process. – Ira Baxter Aug 14 '11 at 14:38
3

If there is a hierarchy in the url structure, that should be used to maximize performance. Only an url that starts with /user/ can match any of the first three and so on.

I suggest storing the hierarchy to match in a tree corresponding to the url hierarchy, where each node matches a level in the hierarchy. To match an url, test the url against all roots of the tree where only nodes with regexes for "user" and "users" are. Matching url:s are tested against the children of those nodes until a match is found in a leaf node. A succesful match can be returned as the list of nodes from the root to the leaf. Named groups with property values such as {user-id} can be fetched from the nodes of the successful match.

Anders Forsgren
  • 10,827
  • 4
  • 40
  • 77
1

Use named expressions and the OR operator, i.e. "(?P<re1>...)|(?P<re2>...)|...".

pyroscope
  • 4,120
  • 1
  • 18
  • 13
  • 2
    Won't that be the roughly the same performance as testing re1, re2.. sequentially and stopping at the first match? – Anders Forsgren Aug 13 '11 at 10:44
  • @Anders: not necessarily. If the matcher is implemented dumbly, yes, but doing this kind of matching efficiently has had efficent solutions for a long time. See my answer re lexer generators. – Ira Baxter Aug 13 '11 at 15:26
  • @Ira sure, but this suggested answer here does not involve that kind of lexer, only combining all regexes into a single regex with multiple named group if i understand the answer correctly (and how .NET's regexes work) – Anders Forsgren Aug 13 '11 at 15:37
  • 1
    @Anders: that may be how .NET regexes work, but a) OP didn't ask specifically about .NET, so holding it up as a quintessential example doesn't seem very useful, b) there are regex engines (I think Java's) that do this non-dumbly. – Ira Baxter Aug 13 '11 at 15:49
  • (This is not relevant to my question, but I indeed didn't have .NET in mind, but Haskell.) – stakx - no longer contributing Aug 14 '11 at 10:23
1

First I though that I couldn't see any good optimization for this process.

However, if you have a really large number of regexes you might want to partition them (I'm not sure if this is technically partitioning).

What I tell you to do is:

Suppose that you have 20 possible urls that start with user:

/user/with-id/X
/user/with-id/X/preferences # instead of preferences, you could have another 10 possibilities like /friends, /history, etc

Then, you also have 20 possible urls starting with users:

/users/who-signed-up-on
/users/who-signed-up-on-between     #others: /registered-for, /i-might-like, etc

And the list goes on for /products, /companies, etc instead of users.

What you could do in this case is using "multi-level" matching.

First, match the start of the string. You'd be matching for /products, /companies, /users, one at a time and ignoring the rest of the string. This way, you don't have to test all the 100 possibilities.

After you know the url starts with /users, you can match only the possible urls that start with users.

This way, you would reduce a lot of unneeded matches. You won't match the string for all the /procucts possibilities.

Pedro Loureiro
  • 11,436
  • 2
  • 31
  • 37