确定正则表达式的特异性

Question

给定以下正则表达式：

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

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

谢谢！

保罗

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

测试

每个测试采用 2 个字符串（a 和 b）并尝试确定它们之间的相关性。如果测试无法确定关系，则返回 None。

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

SUBSET 表示 b 是 a 的超集。

INTERSECT 表示 a 的某些匹配将与 b 匹配，但某些不会，而 b 的某些匹配将匹配' t 匹配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")

完整的可用版本位于此处< /a>.

Answer 2

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

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

其中哪一项更具体？

Answer 3

这有点像黑客，但它可以为近 10 年前提出的这个问题提供实用的解决方案。

正如@torak 所指出的，定义一个正则表达式比另一个正则表达式更具体意味着什么是很困难的。

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

例如，字符串 [电子邮件受保护]与正则表达式 /alice@myprovider\.com/ 匹配，但如果您对字符串进行任何更改，它将不匹配。所以这个正则表达式非常不稳定。但正则表达式 /.*/ 非常稳定，因为您可以对字符串进行任何更改，它仍然匹配。

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

为了实现此稳定性测试，我们需要定义如何选择对与正则表达式匹配的字符串进行较小的更改。这是另一堆蠕虫。例如，我们可以选择将字符串的每个字符更改为随机字符，并针对正则表达式或任何其他可能的选择进行测试。为简单起见，我建议一次从字符串中删除一个字符，然后进行测试。

因此，如果匹配的字符串长度为 N 个字符，则我们需要进行 N 个测试。让我们看一下从字符串中一次删除一个字符 [email protected]< /a>，匹配下表中的所有正则表达式。它有 12 个字符长，因此有 12 个测试。在下表中，

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

              /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

得分最低的正则表达式最具体。当然，一般来说，可能有多个正则表达式具有相同的分数，这反映了这样一个事实：存在通过任何合理的测量特异性的方式来衡量的正则表达式彼此是一样具体的。尽管它也可能对正则表达式产生相同的分数，但人们很容易认为它们彼此不那么具体（如果您能想到一个例子，请发表评论）。

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

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

我们可以认为第二个更具体，因为它限制了更多字符，并且上述测试将同意该观点。

正如我所说，我们选择对匹配多个正则表达式的字符串进行微小更改的方式是一罐蠕虫，上述方法产生的答案可能取决于该选择。但正如我所说，这是一个很容易实现的黑客 - 它并不严格。

当然，如果匹配的字符串为空，该方法就会中断。测试的有用性会随着字符串长度的增加而增加。对于非常短的字符串，它更有可能为特异性明显不同的正则表达式产生相同的分数。

Answer 4

我正在考虑 PHP 项目路由解析器的类似问题。在阅读了这里的其他答案和评论，并考虑了所涉及的成本之后，我可能会完全走向另一个方向。

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

它并不完美，但只需删除 [] 组，它就会更接近。在问题中的第一个示例中，它将列出以下内容：

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

对此，删除任何 []-组的内容后：

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

另一个答案中的第二个示例也是如此，[]-组完全删除并按长度排序，这：

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

将排序为：

[email protected]
alice@+\.+ 

如果我选择使用它，至少对我来说这是一个足够好的解决方案。缺点是在排序之前删除所有 [] 组并将排序应用于未修改的正则表达式列表的开销，但是嘿 - 你无法获得所有内容。