11

Given the following regular expressions:

 - alice@[a-z]+\.[a-z]+
 - [a-z]+@[a-z]+\.[a-z]+
 - .*

The string [email protected] will obviously match all three regular expressions. In the application I am developing, we are only interested in the 'most specific' match. In this case this is obviously the first one.
Unfortunately there seems no way to do this. We are using PCRE and I did not find a way to do this and a search on the Internet was also not fruitful.
A possible way would be to keep the regular expressions sorted on descending specificity and then simply take the first match. Of course then the next question would be how to sort the array of regular expressions. It is not an option to give the responsability to the end-user to ensure that the array is sorted. So I hope you guys could help me out here...

Thanks !!

Paul

1
  • 1
    It's not obvious to me that the first one is most specific. What is your definition of most specific define an algorithm for that and you will be half way there. But it seems to me the easy way of doing it (like Flex) is you have multiple expressions that match exactly then choose the first one defined in your data. Aug 31, 2010 at 18:51

4 Answers 4

5

The following is the solution to this problem I developed based on Donald Miner's research paper, implemented in Python, for rules applied to MAC addresses.

Basically, the most specific match is from the pattern that is not a superset of any other matching pattern. For a particular problem domain, you create a series of tests (functions) which compare two REs and return which is the superset, or if they are orthogonal. This lets you build a tree of matches. For a particular input string, you go through the root patterns and find any matches. Then go through their subpatterns. If at any point, orthogonal patterns match, an error is raised.

Setup

import re

class RegexElement:
    def __init__(self, string,index):
        self.string=string
        self.supersets = []
        self.subsets = []
        self.disjoints = []
        self.intersects = []
        self.maybes = []
        self.precompilation = {}
        self.compiled = re.compile(string,re.IGNORECASE)
        self.index = index

SUPERSET  = object()
SUBSET    = object()
INTERSECT = object()
DISJOINT  = object()
EQUAL     = object()

The Tests

Each test takes 2 strings (a and b) and tries to determine how they are related. If the test cannot determine the relation, None is returned.

SUPERSET means a is a superset of b. All matches of b will match a.

SUBSET means b is a superset of a.

INTERSECT means some matches of a will match b, but some won't and some matches of b won't match a.

DISJOINT means no matches of a will match b.

EQUAL means all matches of a will match b and all matches of b will match a.

    def equal_test(a, b):  
        if a == b: return EQUAL

The graph

  class SubsetGraph(object):
    def __init__(self, tests):
        self.regexps = []
        self.tests = tests
        self._dirty = True
        self._roots = None

    @property
    def roots(self):
        if self._dirty:
            r = self._roots = [i for i in self.regexps if not i.supersets]
            return r
        return self._roots

    def add_regex(self, new_regex):
        roots = self.roots
        new_re = RegexElement(new_regex)
        for element in roots:
            self.process(new_re, element)
        self.regexps.append(new_re)

    def process(self, new_re, element):
        relationship = self.compare(new_re, element)
        if relationship:
            getattr(self, 'add_' + relationship)(new_re, element)

    def add_SUPERSET(self, new_re, element):
        for i in element.subsets:
            i.supersets.add(new_re)
            new_re.subsets.add(i)

        element.supersets.add(new_re)
        new_re.subsets.add(element)

    def add_SUBSET(self, new_re, element):
        for i in element.subsets:
            self.process(new_re, i)

        element.subsets.add(new_re)
        new_re.supersets.add(element)

    def add_DISJOINT(self, new_re, element):
        for i in element.subsets:
            i.disjoints.add(new_re)
            new_re.disjoints.add(i)

        new_re.disjoints.add(element)
        element.disjoints.add(new_re)

    def add_INTERSECT(self, new_re, element):
        for i in element.subsets:
            self.process(new_re, i)

        new_re.intersects.add(element)
        element.intersects.add(new_re)

    def add_EQUAL(self, new_re, element):
        new_re.supersets = element.supersets.copy()
        new_re.subsets = element.subsets.copy()
        new_re.disjoints = element.disjoints.copy()
        new_re.intersects = element.intersects.copy()

    def compare(self, a, b):
        for test in self.tests:
            result = test(a.string, b.string)
            if result:
                return result

    def match(self, text, strict=True):
        matches = set()
        self._match(text, self.roots, matches)
        out = []
        for e in matches:
            for s in e.subsets:
                if s in matches:
                    break
            else:
                out.append(e)
        if strict and len(out) > 1:
            for i in out:
                print(i.string)
            raise Exception("Multiple equally specific matches found for " + text)
        return out

    def _match(self, text, elements, matches):
        new_elements = []
        for element in elements:
            m = element.compiled.match(text)
            if m:
                matches.add(element)
                new_elements.extend(element.subsets)
        if new_elements:
            self._match(text, new_elements, matches)

Usage

graph = SubsetGraph([equal_test, test_2, test_3, ...])
graph.add_regex("00:11:22:..:..:..")
graph.add_regex("..(:..){5,5}"
graph.match("00:de:ad:be:ef:00")

A complete usable version is here.

3
  • Poking around at the author's site I found this: It's not GPLed, so don't go using it without contacting him first. maple.cs.umbc.edu/~don/projects/ugrad-ht/regexfind.py
    – Perkins
    Jul 14, 2011 at 18:49
  • specified urls are not valid Jan 18, 2017 at 6:13
  • I'm not surprised. I did talk to the author (years ago now) and he said it's fine to reuse his work with or without attribution. I'll see about editing the answer.
    – Perkins
    Jul 23, 2018 at 20:56
4

My gut instinct says that not only is this a hard problem, both in terms of computational cost and implementation difficulty, but it may be unsolvable in any realistic fashion. Consider the two following regular expressions to accept the string [email protected]

    alice@[a-z]+\.[a-z]+ 
    [a-z][email protected]

Which one of these is more specific?

1
  • The one with more character constants? Or maybe you could automatically build a regular expression that was the intersection of both of them. That is, if RE (a) defines language L1 and RE (b) defines language L2, build a regular expression RE (a, b) which defines a language INTERSECTION(L1, L2).
    – Avi
    Aug 31, 2010 at 18:39
2

This is a bit of a hack, but it could provide a practical solution to this question asked nearly 10 years ago.

As pointed out by @torak, there are difficulties in defining what it means for one regular expression to be more specific than another.

My suggestion is to look at how stable the regular expression is with respect to a string that matches it. The usual way to investigate stability is to make minor changes to the inputs, and see if you still get the same result.

For example, the string [email protected] matches the regex /alice@myprovider\.com/, but if you make any change to the string, it will not match. So this regex is very unstable. But the regex /.*/ is very stable, because you can make any change to the string, and it still matches.

So, in looking for the most specific regex, we are looking for the least stable one with respect to a string that matches it.

In order to implement this test for stability, we need to define how we choose a minor change to the string that matches the regex. This is another can of worms. We could for example, choose to change each character of the string to something random and test that against the regex, or any number of other possible choices. For simplicity, I suggest deleting one character at a time from the string, and testing that.

So, if the string that matches is N characters long, we have N tests to make. Lets's look at deleting one character at a time from the string [email protected], which matches all of the regular expressions in the table below. It's 12 characters long, so there are 12 tests. In the table below,

  • 0 means the regex does not match (unstable),
  • 1 means it matches (stable)
              /alice@[a-z]+\.[a-z]+/    /[a-z]+@[a-z]+\.[a-z]+/     /.*/
  
[email protected]           0                           1                  1
[email protected]           0                           1                  1
[email protected]           0                           1                  1
[email protected]           0                           1                  1
[email protected]           0                           1                  1
alicefoo.com           0                           0                  1
[email protected]           1                           1                  1
[email protected]           1                           1                  1
[email protected]           1                           1                  1
alice@foocom           0                           0                  1 
[email protected]           1                           1                  1
[email protected]           1                           1                  1
                      ---                         ---                ---  
total score:           5                          10                 12

The regex with the lowest score is the most specific. Of course, in general, there may be more than one regex with the same score, which reflects the fact there are regular expressions which by any reasonable way of measuring specificity are as specific as one another. Although it may also yield the same score for regular expressions that one can easily argue are not as specific as each other (if you can think of an example, please comment).

But coming back to the question asked by @torak, which of these is more specific:

alice@[a-z]+\.[a-z]+ 
[a-z][email protected]

We could argue that the second is more specific because it constrains more characters, and the above test will agree with that view.

As I said, the way we choose to make minor changes to the string that matches more than one regex is a can of worms, and the answer that the above method yields may depend on that choice. But as I said, this is an easily implementable hack - it is not rigourous.

And, of course the method breaks if the string that matches is empty. The usefulness if the test will increase as the length of the string increases. With very short strings, it is more likely produce equal scores for regular expressions that are clearly different in their specificity.

0

I'm thinking of a similar problem for a PHP projects route parser. After reading the other answers and comments here, and also thinking about the cost involved I might go in another direction altogether.

A solution however, would be to simply sort the regular expression list in order of it's string length.

It's not perfect, but simply by removing the []-groups it would be much closer. On the first example in the question it would this list:

- alice@[a-z]+\.[a-z]+
- [a-z]+@[a-z]+\.[a-z]+
- .*

To this, after removing content of any []-group:

- alice@+\.+
- +@+\.+
- .*

Same thing goes for the second example in another answer, with the []-groups completely removed and sorted by length, this:

alice@[a-z]+\.[a-z]+ 
[a-z][email protected]

Would become sorted as:

[email protected]
alice@+\.+ 

This is a good enough solution at least for me, if I choose to use it. Downside would be the overhead of removing all groups of [] before sorting and applying the sort on the unmodified list of regexes, but hey - you can't get everything.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.