regex - 增量正则表达式匹配

Question

问题：程序需要从输入的字符流中读取，并将输入与预定义的正则表达式模式列表进行匹配。程序应在找到匹配后立即报告（如果有多个则报告全部），或者在没有匹配的情况下消耗整个流后报告失败。输入可能不会一次全部出现，因此每当程序调用read输入流时，都可以读取零个、一个或多个字符。

简单的解决方案是缓冲到目前为止已读取的所有字符，并尝试将其与整组正则表达式模式匹配。但这不是很有效。正则表达式匹配本质上是有状态的，所以应该有一种方法不缓冲输入。理想情况下，有一个使用类似于 Aho-Corasick 的技术进行纯字符串匹配的一次性解决方案。我搜索了现有的库，但没有找到能够进行这种增量正则表达式匹配的库。哪些库或算法可以提供帮助（首选 C、C++、Python 或 Perl 库）？

一种现有的解决方案通过or -ing 小的正则表达式模式形成一个巨大的正则表达式模式。但我不确定这是否比迭代小的正则表达式模式更快。这不是增量匹配：每个匹配都需要整个缓冲输入。

不重复：Java 中的增量模式 (RegEx) 匹配？那里接受的答案显示了一个方向，但没有具体的解决方案。其他用户报告了合并 FSA 导致的非常大的内存占用，但该答案没有提到如何优化以使其实用。

---

帮助制定问题的 Python 框架：

regex_list = [ r'0+', r'1+', r'2+', r'3+' ]
class Matcher:
    def match(self):
        ...
        buffer += sys.stdin.read()
        ...
        return ([ matched_regex, ... ], matched_token)
matcher = Matcher()
while True:
    matched_regex_list, token = matcher.match()

标签： regexincremental-search