是否有提供按模式查找(regex)的数据结构

fgrep工具正是您所说的：将文本与多个正则表达式进行匹配。我的理解是，最初的版本使用了与Aho-Corasick字符串匹配算法非常相似的东西来在一次遍历中搜索多个正则表达式。基本上，它创建了一个DFA并运行它。

我不知道fgrep的.NET实现。如果你找到一个，我当然很想听听。

你可以追踪fgrep的源代码（谷歌有很多源代码），看看它是如何实现的。

或者，您可以让您的程序外壳到fgrep。或者创建一个具有fgrep入口点的C++DLL，您可以从C#程序调用该入口点。

如果您的多个模式是常量字符串（即不是正则表达式），那么您可能会对我的Aho-Corasick算法的C#实现感兴趣。

让我们假设这些正则表达式是真正的正则表达式。然后，每一个都可以转换为非确定性有限自动机，该非确定性有限Automaton可以转换为确定性有限自动机。确定性有限自动机可以在输入长度的O（n）时间内进行评估。

但它并没有解决同时匹配多个regexp的问题。我们可以通过创建一个类似(regexp1|regexp2|...)的正则表达式来实现这一点，并将变成一个NFA/DFA。在自动机的分支中添加一些插入，以跟踪哪一个特定的regexp生成了与输入匹配的路径，您就得到了匹配器，输入字符串的长度仍然为O（n）。

这种技术不支持任何使语言不规则的"regex"特性，例如backreferences。

另一个缺点是产生的DFA可能很大。也可以直接评估NFA，这可能较慢，但具有更好的记忆行为。

---

事实上，在代码中表达这个想法也很容易，而不用担心自动机的东西。只需使用匹配组：

combined_regexp = (regexp1)|(regexp2)|...

在评估时，只需查看哪个组与输入匹配即可。

请记住，在某些情况下，大多数regex实现/库的性能都很差，编译或匹配regexp可能需要指数级的时间。我不确定这在实践中有多大的问题。谷歌的RE2库是专门设计的，不会有这种病态行为，但可能还有其他的。

另一个问题可能是，除非您的regexp实现专门宣传O（n）行为，否则它可能只是依次尝试每种替代方案。在这种情况下，这种方法不会给你带来任何好处。

几年前，我实现了一个基于确定性有限状态机的正则表达式搜索引擎，与Thomas在回答中描述的非常相似。它将正则表达式键和值的列表编译成一个有限状态自动机，该自动机在其终端状态中引用定义类型的对象（例如，RegexTrie在终端状态引用字符串）。

实现可在以下位置获得：https://bitbucket.org/tjnieminen/regexkeytrie

标准搜索是通过维护通过机器的路径列表来执行的。对于搜索文本的每个字符，每个活动路径都会被推进，并且每当达到终端状态时都会记录匹配。为源文本的每个字符添加一个从机器根开始的新路径（这允许子字符串匹配），并从路径列表中删除停止在非终端状态的路径。

无论任务是什么，通常最好自定义处理。例如，如果使用正则表达式替换引擎，则最好在遍历过程中生成编辑后的文本（如转换器），而不是使用返回的匹配项执行查找和替换操作。

我已经将该实现与普通的.Net正则表达式进行了基准测试，在应该进行测试的情况下，它似乎做得更好，即使用一组大型正则表达式和一个要搜索的长文本的组合。

该实现还没有经过彻底的测试，因此可能会留下一些错误，而且使用复杂的正则表达式可能很容易耗尽内存（或者它们可能需要很长时间才能编译）。但是，由于目前还没有类似的可用工具，对于寻找它所提供的性能特征的人来说，这可能是一个有用的起点。