确定正则表达式的特异性

Question

考虑以下正则表达式：

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

字符串[e-mail]显然符合所有三个正则表达式。在我正在开发的应用程序中，我们只对“最具体”的匹配感兴趣。在这种情况下，显然是第一个。
不幸的是似乎没有办法做到这一点。我们正在使用PCRE，我没有找到一种方法来做到这一点，而在互联网上的搜索也没有什么结果。
一个可能的方法是按特定性的降序对正则表达式进行排序，然后简单地取第一个匹配项。当然，接下来的问题是如何对正则表达式数组进行排序。将责任交给最终用户来确保数组已排序不是一个选项。
所以我希望你们在这里能帮帮我...

谢谢！！

保罗

- Paul Praet

---

对我来说第一个并不显然是“最具体”的。你对“最具体”的定义是什么，给出一个算法就完成了一半。但在我看来像Flex这样做的简单方法是：当有多个完全匹配的表达式时，选择数据中定义的第一个。 - Martin York

Answer 1

以下是我基于Donald Miner的研究论文开发的解决此问题的方案，使用Python实现，用于应用于MAC地址的规则。

基本上，最具体的匹配来自不是任何其他匹配模式的超集的模式。针对特定问题域，您可以创建一系列测试（函数），比较两个RE并返回哪个是超集，或者它们是否正交。这使您可以构建匹配树。对于特定的输入字符串，您浏览根模式并查找任何匹配项。然后浏览其子模式。如果在任何时候正交模式匹配，则会引发错误。

设置

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()

测试

每个测试都需要两个字符串（a和b），并尝试确定它们之间的关系。如果测试无法确定关系，则返回None。

SUPERSET表示a是b的超集。所有与b匹配的内容都将与a匹配。

SUBSET表示b是a的超集。

INTERSECT表示a的某些匹配项将与b匹配，但某些匹配项不会，而b的某些匹配项也不会与a匹配。

DISJOINT表示没有任何a的匹配项会与b匹配。

EQUAL表示所有a的匹配项都将与b匹配，并且所有b的匹配项都将与a匹配。

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

图表

  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)

用法

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")

完整可用版本在这里。

- Perkins

---

在作者的网站上瞎逛，我发现了这个：它不是GPL许可的，所以在未事先联系他的情况下不要使用它。http://maple.cs.umbc.edu/~don/projects/ugrad-ht/regexfind.py - Perkins

指定的URL无效。 - Tharindu Kumara

我并不感到惊讶。几年前我曾与作者交谈过，他说可以在署名或不署名的情况下重用他的作品。我会考虑编辑答案。 - Perkins

Answer 2

我的直觉告诉我，这不仅是一个计算成本和实现难度都很高的问题，而且在任何现实情况下可能都无法解决。考虑以下两个正则表达式来接受字符串[e-mail]

    alice@[a-z]+\.[a-z]+ 
    [a-z][e-mail]

其中哪一个更具体？

- torak

---

哪一个有更多的字符常量？或者你可以自动构建一个正则表达式，它是两个正则表达式的交集。也就是说，如果RE（a）定义了语言L1，而RE（b）定义了语言L2，则构建一个正则表达式RE（a，b），该正则表达式定义了一个INTERSECTION（L1，L2）的语言。 - Avi

Answer 3

这是一个有些取巧的方法，但它可以提供一个实际的解决方案，来回答近10年前提出的这个问题。

正如@torak所指出的那样，定义一个正则表达式比另一个更具体是有困难的。

我的建议是看看与匹配字符串相比，正则表达式的稳定性如何。研究稳定性的常规方法是对输入进行微小的更改，并查看是否仍然得到相同的结果。

例如，字符串“[e-mail]”与正则表达式“/alice@myprovider\.com/”匹配，但如果您对字符串进行任何更改，它将不匹配。因此，这个正则表达式非常不稳定。但是正则表达式“/.*/”非常稳定，因为您可以对字符串进行任何更改，它仍然匹配。

因此，在寻找最具体的正则表达式时，我们正在寻找相对于匹配它的字符串而言最不稳定的正则表达式。

为了测试稳定性，我们需要定义如何选择与正则表达式匹配的字符串的微小更改。这是另一个麻烦事。例如，我们可以选择将字符串的每个字符更改为某些随机字符，并将其与正则表达式进行测试，或者进行任意数量的其他可能选择。为简单起见，我建议逐个删除字符串中的一个字符，并进行测试。

因此，如果匹配的字符串长度为N个字符，则我们需要进行N次测试。让我们从字符串“[e-mail]”中逐个删除一个字符进行测试，该字符串与下表中的所有正则表达式都匹配。它有12个字符，因此有12个测试。在下表中，

- 0表示正则表达式不匹配（不稳定）， - 1表示匹配（稳定）。

              /alice@[a-z]+\.[a-z]+/    /[a-z]+@[a-z]+\.[a-z]+/     /.*/
  
[e-mail]           0                           1                  1
[e-mail]           0                           1                  1
[e-mail]           0                           1                  1
[e-mail]           0                           1                  1
[e-mail]           0                           1                  1
alicefoo.com           0                           0                  1
[e-mail]           1                           1                  1
[e-mail]           1                           1                  1
[e-mail]           1                           1                  1
alice@foocom           0                           0                  1 
[e-mail]           1                           1                  1
[e-mail]           1                           1                  1
                      ---                         ---                ---  
total score:           5                          10                 12

得分最低的正则表达式是最具体的。当然，通常情况下，可能会有多个得分相同的正则表达式，这反映了存在一些正则表达式，无论如何衡量其特定性，它们都是同样具体的事实。虽然对于那些可以轻松争辩不如彼此具体的正则表达式，它也可能产生相同的得分（如果您能想到一个例子，请发表评论）。

但回到@torak提出的问题，哪一个更具体：

alice@[a-z]+\.[a-z]+ 
[a-z][e-mail]

我们可以争论第二个正则表达式更具体，因为它对更多字符进行了限制，上述测试也会支持这个观点。

就像我说的那样，我们选择对与多个正则表达式匹配的字符串进行微小更改的方式是一个棘手的问题，上述方法得出的答案可能取决于该选择。但正如我所说，这是一个容易实现的技巧 - 它不是严格的。

当匹配的字符串为空时，该方法当然会失效。随着字符串长度的增加，测试的有用性将增加。对于非常短的字符串，很可能会产生相等的得分，而这些字符串在其特异性方面明显不同的正则表达式。

- Matt Wallis

Answer 4

我正在考虑一个与 PHP 项目路由解析器类似的问题。在阅读了其他答案和评论，并考虑到涉及的成本后，我可能会采取完全不同的方向。

然而，一种解决方案是简单地按字符串长度对正则表达式列表进行排序。

这并不完美，但只需删除 []-groups，它就会更接近完美。在问题的第一个示例中，它将是这个列表：

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

在此基础上，删除任何[]组的内容：

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

同样的事情也适用于另一个答案中的第二个示例，其中[]组被完全删除并按长度排序，如下所示：

alice@[a-z]+\.[a-z]+ 
[a-z][e-mail]

将会被排序为：

[e-mail]
alice@+\.+ 

对我来说，这是一个足够好的解决方案，如果我选择使用它。缺点是在排序和应用未修改的正则表达式列表之前删除所有[]组的开销，但是嘿 - 你不能得到一切。

- Christoffer Bubach