有效地查询一个string与多个正则expression式
比方说，我有10,000个正则expression式和一个string，我想知道是否string匹配任何一个，并获得所有的匹配。 做这件事的简单方法是只针对所有正则expression式查询string。 有没有更快，更有效的方法来做到这一点？
编辑：我试图用DFA（lex）代替它这里的问题是，它只会给你一个单一的模式。 如果我有一个string“hello”和模式“[H | h] ello”和“。{0,20} ello”，DFA将只匹配其中一个，但我希望他们两个打。
Martin Sulzmann在这个领域做了很多工作。 他有一个HackageDB项目 在这里解释很less使用偏导数似乎是为此量身定做的。
所使用的语言是Haskell，因此如果这是一种非function性语言，我很难将其转换为非function语言（我认为翻译成许多其他语言的语言仍然很难）。
该代码不是基于转换为一系列的自动机，然后将它们相结合，而是基于对正则expression式本身的符号操作。
此外，代码非常具有实验性，Martin不再是教授，而是处于“有收益的工作”（1），因此可能不感兴趣/无法提供任何帮助或意见。
- 这是一个笑话 – 我喜欢教授，聪明的人越less尝试工作越有机会获得报酬！
我们必须在我曾经工作的产品上做这个。 答案是把所有的正则expression式一起编译成确定性有限状态机 （也称为确定性有限自动机或DFA ）。 DFA然后可以在string中逐个字符地走，并且只要其中一个expression式匹配就会触发“匹配”事件。
优点是运行速度快（每个字符仅比较一次），如果添加更多expression式，速度不会变慢。
缺点是它需要一个巨大的自动机数据表，并且有许多types的正则expression式不被支持（例如，反向引用）。
我们所使用的是当时我们公司的一个C ++模板螺母手工编写的，所以很遗憾我没有任何FOSS解决scheme指向你。 但是，如果你是谷歌正则expression式或正则expression式与“ DFA ”，你会发现的东西，将指向你在正确的方向。
我过去遇到过类似的问题。 我使用了类似于akdombuild议的解决scheme。
我很幸运，我的正则expression式通常有一些子string必须出现在每个匹配的string中。 我能够使用简单的parsing器提取这些子string，并使用Aho-Corasickalgorithm在FSA中对其进行索引。 然后使用该索引来快速消除所有正则expression式，这些正则expression式并不匹配给定的string，只留下一些正则expression式来检查。
我作为Python / C模块发布了LGPL下的代码。 请参阅Google代码托pipe上的esmre 。
这是词法分析器的工作方式。
正则expression式转换为单一的非确定性自动机（NFA），并可能在确定性自动机（DFA）中转换。
由此产生的自动机将尝试一次匹配所有的正则expression式，并将在其中一个正确的expression式。
有很多工具可以帮助你，他们被称为“词法发生器”，并有解决scheme，与大多数的语言工作。
你不会说你正在使用哪种语言。 对于C程序员，我build议看看re2c工具。 传统的（f）lex总是一个select。
10000正则expression式？ 埃里克·温德林（Eric Wendelin）提出的层级结构似乎是一个好主意。 你有没有想过把这些正则expression式的巨大性降低到像树结构一样？
作为一个简单的例子：所有需要一个数字的正则expression式可以分解一个正则expression式来检查这样的情况，所有正则expression式不需要向下一个分支。 以这种方式，您可以将实际比较的数量减less到沿着树的path，而不是进行10,000次的每一次比较。
这需要分解提供给stream派的正则expression式，每种stream派都有一个共同的testing，如果失败，将会排除这些testing。 通过这种方式，理论上可以显着减less实际比较的次数。
如果您在运行时必须这样做，则可以通过给定的正则expression式进行parsing，并将它们“归档”为预定义的stream派（最容易做到）或在那一刻生成的比较stream派（并不容易）。
你的比较“hello”到“[H | h] ello”和“。{0,20} ello”的例子将不会被这个解决scheme真正的帮助。 一个简单的例子是：如果你有1000个testing，只有在string的某处存在“ello”而你的testingstring是“再见”，才会返回true。 你只需要对“ello”进行一个testing，并知道1000个testing需要的testing将不起作用，正因为如此，你不必这样做。
你需要有一些方法来确定一个给定的正则expression式是否与另一个正相关。 创buildsorting的正则expression式“层次结构”，可以确定某个分支的所有正则expression式都不匹配
如果你用“10,000个正则expression式”来思考，你需要改变你的stream程。 如果没有别的，就用“10,000个匹配的目标string”来思考。 然后寻找非正则expression式的方法来处理“目标string”的情况，如Aho-Corasick机器。 坦率地说，尽pipe在这个过程中，似乎有些东西比起使用哪台机器更早了，因为10,000个目标string听起来更像是一个数据库查询而不是string匹配。
你可以把它们分成20组。
(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?) 只要每个正则expression式都有零个（或至less相同数量的）捕获组，您可以查看捕获哪些模式匹配的内容。
如果regex1匹配，捕获组1将具有匹配的文本。 如果没有，那将是undefined / None / null / …
如果你正在使用真正的正则expression式（那些与正式语言理论中的正则语言相对应的正则expression式，而不是一些类似于Perl的非常规的东西），那么你很幸运，因为正规语言在联合之下是封闭的。 在大多数正则expression式语言中，pipe（|）是union。 所以你应该能够构造一个string（表示你想要的正则expression式），如下所示：
(r1)|(r2)|(r3)|...|(r10000)
括号用于分组，不匹配。 任何匹配这个正则expression式的东西至less匹配一个原始的正则expression式。
我想说，这是一个真正的parsing器的工作。 中点可能是parsingexpression语法（PEG） 。 它是模式匹配的更高层抽象，其中一个特点是可以定义整个语法而不是单个模式。 有一些高性能的实现可以通过将语法编译成字节码并在专用的虚拟机中运行来实现。
免责声明：我所知道的唯一一个是LPEG ，是Lua的一个图书馆，掌握基本概念并不容易（对我来说）。
Aho-Corasick是我的答案。
我有2000个类别的东西，每个都有模式列表匹配。 string长度平均大约100,000个字符。
主警告：匹配的模式是所有语言模式，而不是正则expression式模式，例如'cat'与“ r'\w+' 。
我正在使用Python ，所以使用https://pypi.python.org/pypi/pyahocorasick/ 。
import ahocorasick A = ahocorasick.Automaton() patterns = [ [['cat','dog'],'mammals'], [['bass','tuna','trout'],'fish'], [['toad','crocodile'],'amphibians'], ] for row in patterns: vals = row[0] for val in vals: A.add_word(val, (row[1], val)) A.make_automaton() _string = 'tom loves lions tigers cats and bass' def test(): vals = [] for item in A.iter(_string): vals.append(item) return vals
在我的2000类别上运行%timeit test() ，每个类别约2-3条logging， _string长度约为100,000 ，我的速度2.09 ms比631 ms 速度提高了315％。 。
我几乎build议写一个“从内到外”的正则expression式引擎 – 其中“目标”是正则expression式，“term”是string。
然而，似乎你迭代尝试每一个的解决scheme将变得更加容易。
你可以将正则expression式编译成一个混合的DFA / Bucchi自动机 ，每当BA进入一个接受状态时，你就会标记哪个正则expression式规则“打”。
Bucchi对此有点矫枉过正，但是修改DFA的工作方式可能会有所斩获。
尝试将它们组合成一个大的正则expression式？
我认为简单的回答是，是的，有一种方法可以做到这一点，这是计算机科学所熟知的，我不记得它是什么。
简单的答案是，你可能会发现你的正则expression式解释器已经有效地处理了所有这些，或者你可能会find一个正确的解释器。 如果没有，是时候你谷歌string匹配和searchalgorithm。
最快的方式做到这一点似乎是这样的（代码是C＃）：
public static List<Regex> FindAllMatches(string s, List<Regex> regexes) { List<Regex> matches = new List<Regex>(); foreach (Regex r in regexes) { if (r.IsMatch(string)) { matches.Add(r); } } return matches; }
哦，你的意思是最快的代码 ？ 我不知道然后….
