给出以下正则表达式:
- alice@[a-z]+\.[a-z]+
- [a-z]+@[a-z]+\.[a-z]+
- .*
字符串alice@myprovider.com显然会匹配所有三个正则表达式.在我正在开发的应用程序中,我们只对"最具体"的匹配感兴趣.在这种情况下,这显然是第一个.
不幸的是,似乎没有办法做到这一点.我们正在使用PCRE,但我找不到这样做的方法,在互联网上搜索也没有成效.
一种可能的方法是保持正则表达式按降序特异性排序,然后简单地进行第一次匹配.当然接下来的问题是如何对正则表达式数组进行排序.不能向最终用户提供责任以确保对阵列进行排序.所以我希望你们能在这里帮助我......
谢谢 !!
保罗
以下是我根据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匹配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")
这里有一个完整的可用版本.
我的直觉告诉我，这不仅是一个难题，无论是在计算成本还是实现难度方面，而且在任何现实情况下都可能无法解决。考虑以下两个正则表达式来接受字符串alice@myprovider.com
爱丽丝@[az]+\.[az]+
[az]+@myprovider.com
其中哪一项更具体？