多正则表达式匹配 (Multiple Regular Expression Matching) 中的
|
前一段时间，在将多正则表达式匹配工具用于数十万任意的正则表达式时，以前一直担心的问题终于出现了：NFA 转化 DFA 时的指数爆炸，那样的 DFA 根本创建不出来，因为那些正则表达式之间有不可预料的各种交集！ 这个问题对我打击很大，我甚至顿时觉得多正则表达式匹配工具完全是个废柴，最多，是个玩具！但是，只有挑战，才能激励人的斗志，挖掘人的潜能。我想起了曾经对之不屑一顾的动态 DFA 匹配算法，之前我在研究 RE2 时知道，RE2 在动态 DFA 的内存用量达到限定时，会抛弃已经创建整个动态 DFA，因为 DFA 的状态图比较复杂，节点之间互相引用，无法象普通的 Cache 一样部分的进行 Swap ，直觉上对它就没有好印象。 但是碰到组合爆炸这个魔咒，只有尝试一下，就先用 RE2 中的 set 试一下，先从那数十万正则表达式中任选一万个，re2 执行倒是很快，但立马就提示 DFA Out Of Memory 了，然后我尝试将 re2 的内存设到 8G，还是不行，浪费若干脑细胞，最后才惊奇地发现，Re2 的内存限制用的是 int 来表示的，而 int 的事实标准是32 bit，最大只能是 2G-1！设成 2G-1之后，re2 运行正常，性能还不错。 于是我开始加码，将所有正则表达式都扔进去，果然，re2 崩了！ 虽然如此，但是至少表明，动态 DFA 解决该问题是可行的，我开始实现我的计划。一切都很顺利： 之前我实现其他算法时（r1303），扩展了自动机的字符集，而没有在自动机的状态上打专用 Tag，这个决定真是明智之举，在这里又用上了：
如果一切都照抄 re2 的实现，那不过是无聊的体力劳动。我的动态 DFA 实现，完全建立在我之前的各种自动机算法之上，有了这个根基，我的实现相比 re2，有很多优势：
事实证明了这些：专门用于实现动态 DFA 的代码也就 500 行左右，包含了算法的所有细节：
最后的测试表明，我的算法比 RE2 要快 4~7 倍，在达到这个性能的同时，内存用量还要小 5~8 倍，并且，对于让 re2 崩掉的那几十万个正则表达式，运行完全正常，同时，还能捕获括号(submatch)。
使用：在
多正则表达式匹配工具中，命令行参数 -D 表示生成的自动机匹配时用动态 DFA。
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |