问题标签 [incremental-search]

P 请让我知道是否需要更改或添加到代码中。这对我正在做的事情有必要吗？

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

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

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

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

帮助制定问题的 Python 框架：

我编写了我的第一个 octave 脚本，它是用于根查找的增量搜索方法的代码，但我遇到了许多我发现难以理解的错误。以下是脚本：

运行时出现以下错误：

下面是增量搜索方法的流程图：