c - 确定正则表达式的特异性

Question

给定以下正则表达式:

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

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

谢谢!!

保罗

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 > 将不匹配 a。

DISJOINT 表示 a 的匹配项都不会匹配 b。

EQUAL 表示 a 的所有匹配项将匹配 b 并且 b 的所有匹配项将匹配 一个。

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

完整的可用版本是 here .