Ниже приведено решение этой проблемы, которое я разработал на основе исследовательской работы Дональда Майнера, реализованной в 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) и пытается определить, как они связаны. Если тест не может определить отношение, ничего не возвращается.
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)
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")
Полная используемая версия: здесь .