NFA 的 Python 正则表达式

Question

我目前正在使用 python 的 re 模块来搜索和捕获组。我列出了一些正则表达式，我必须编译这些正则表达式并将其与导致性能问题的大型数据集 进行匹配。

示例:

REGEXES = [
    '^New York(?P<grp1>\d+/\d+): (?P<grp2>.+)$',
    '^Ohio (?P<grp1>\d+/\d+/\d+): (?P<grp2>.+)$',
    '(?P<year>\d{4}-\d{1,2}-\d{1,2})$',
    '^(?P<year>\d{1,2}/\d{1,2}/\d{2,4})$',
    '^(?P<title>.+?)[- ]+E(?P<epi>\d+)$'
    .
    .
    .
    .
]

注意:正则表达式不会相似

COMPILED_REGEXES = [re.compile(r, flags=re.I) for r in REGEXES]

def find_match(string):
    for regex in COMPILED_REGEXES:
        match = regex.search(string)
        if not match:
            continue
        return match

有解决办法吗？这个想法是为了避免通过编译的正则表达式迭代来获得匹配。

Answer 1

您的任何正则表达式是否会破坏 DFA 兼容性？在您的示例中看起来不像。您可以使用 Python wrapper围绕 C/C++ DFA 实现，如 re2 ，这是 re 的替代品. re2也将退回到使用 re如果正则表达式与 re2 不兼容syntax , 因此它将优化所有可能的情况，并且不会在不兼容的情况下失败。

请注意 re2 是否支持(?P<name>regex)捕获语法，但它不支持 (?P=<name>)反向引用语法。

try:
    import re2 as re
    re.set_fallback_notification(re.FALLBACK_WARNING)
except ImportError:
    # latest version was for Python 2.6
else:
    import re

如果你有带有反向引用的正则表达式，你仍然可以使用 re2有一些特殊注意事项:您需要将正则表达式中的反向引用替换为 .*? , 您可能会发现错误的匹配项，您可以使用 re 过滤掉这些匹配项.在现实世界的数据中，错误匹配可能并不常见。

这是一个说明性的例子:

import re
try:
    import re2
    re2.set_fallback_notification(re2.FALLBACK_WARNING)
except ImportError:
    # latest version was for Python 2.6

REGEXES = [
    '^New York(?P<grp1>\d+/\d+): (?P<grp2>.+)$',
    '^Ohio (?P<grp1>\d+/\d+/\d+): (?P<grp2>.+)$',
    '(?P<year>\d{4}-\d{1,2}-\d{1,2})$',
    '^(?P<year>\d{1,2}/\d{1,2}/\d{2,4})$',
    '^(?P<title>.+?)[- ]+E(?P<epi>\d+)$',
]

COMPILED_REGEXES = [re.compile(r, flags=re.I) for r in REGEXES]
# replace all backrefs with .*? for re2 compatibility
# is there other unsupported syntax in REGEXES?
COMPILED_REGEXES_DFA = [re2.compile(re2.sub(r'\\d|\\g\\d|\\g\<\d+\>|\\g\<\w+\>', '.*?', r), flags=re2.I) for r in REGEXES]

def find_match(string):
    for regex, regex_dfa in zip(COMPILED_REGEXES, COMPILED_REGEXES_DFA):
        match_dfa = regex_dfa.search(string)
        if not match_dfa:
            continue
        match = regex.search(string)
        # most likely branch comes first for better branch prediction
        if match:
            return match

如果这还不够快，您可以采用多种技术将 DFA 匹配提供给 re在处理它们时，而不是将它们存储在文件或内存中，并在它们全部收集完毕后将它们移交。

您还可以将所有正则表达式组合成一个交替组的大型 DFA 正则表达式 (r1)|(r2)|(r3)| ... |(rN)并在生成的匹配对象上遍历您的组匹配，以尝试仅匹配相应的原始正则表达式。匹配结果对象将具有与 OP 的原始解决方案相同的状态。

# rename group names in regexeps to avoid name collisions
REGEXES_PREFIXED = [re2.sub(r'\(\?P\<(\w+)\>', r'(P<re{}_\1>'.format(idx), r) for idx, r in enumerate(REGEXES)]
# wrap and fold regexps (?P<hit0>pattern)| ... |(?P<hitN>pattern)
REGEX_BIG = ''
for idx, r in enumerate(REGEXES_PREFIXED):
    REGEX_BIG += '(?P<hit{}>{})|'.format(idx, r)
else:
    REGEX_BIG = REGEX_BIG[0:-1]
regex_dfa_big = re2.compile(REGEX_BIG, flags = re2.I)

def find_match(string):
    match_dfa = regex_dfa_big.search(string)
    if match_dfa:
        # only interested in hit# match groups
        hits = [n for n, _ in match_dfa.groupdict().iteritems() if re2.match(r'hit\d+', n)]
        # check for false positives
        for idx in [int(h.replace('hit', '')) for h in hits]
            match = COMPILED_REGEXES[idx].search(string)
            if match:
                return match

你也可以看看pyre这是同一个 C++ 库更好维护的包装器，但不是 re 的替代品.还有一个 Python Wrapper对于RuRe ，这是我所知道的最快的正则表达式引擎。