假设我有 10,000 个正则表达式和一个字符串,我想找出字符串是否与其中任何一个匹配并获取所有匹配项。最简单的方法是针对所有正则表达式逐一查询字符串。有没有更快、更有效的方法呢?
编辑:我尝试用 DFA (lex) 代替它这里的问题是它只会给你一个单一的模式。如果我有一个字符串“hello”和模式“[H|h]ello”和“.{0,20}ello”,DFA 只会匹配其中一个,但我希望它们都命中。
我们必须在我曾经做过的产品上这样做。答案是将所有正则表达式一起编译成确定性有限状态机(也称为确定性有限自动机或DFA)。然后,DFA 可以逐个字符地遍历您的字符串,并在其中一个表达式匹配时触发“匹配”事件。
优点是它运行速度快(每个字符只比较一次)并且如果添加更多表达式也不会变慢。
缺点是它需要一个庞大的自动机数据表,并且有许多类型的正则表达式不受支持(例如,反向引用)。
我们使用的那个是当时我们公司的一个 C++ 模板 nut 手工编码的,所以很遗憾,我没有任何 FOSS 解决方案可以为您指明方向。但是,如果您使用“ DFA ”搜索正则表达式或正则表达式,您会发现可以为您指明正确方向的内容。
我过去遇到过类似的问题。我使用了类似于akdom 建议的解决方案。
我很幸运,因为我的正则表达式通常有一些子字符串必须出现在它匹配的每个字符串中。我能够使用简单的解析器提取这些子字符串,并使用 Aho-Corasick 算法在 FSA 中对它们进行索引。然后使用该索引快速消除所有与给定字符串不匹配的正则表达式,只留下几个正则表达式进行检查。
我将 LGPL 下的代码作为 Python/C 模块发布。请参阅Google 代码托管上的 esmre。
Martin Sulzmann在这个领域做了很多工作。他在这里简要解释了一个 HackageDB 项目,该项目使用偏导数似乎是为此量身定制的。
使用的语言是 Haskell,因此如果需要的话,将很难翻译成非功能性语言(我认为翻译成许多其他 FP 语言仍然非常困难)。
该代码不是基于转换为一系列自动机然后组合它们,而是基于对正则表达式本身的符号操作。
此外,该代码非常具有实验性,Martin 不再是教授,而是从事“有酬工作”(1),因此可能不感兴趣/无法提供任何帮助或输入。
10,000 正则表达式是吗? Eric Wendelin 的层次结构建议似乎是个好主意。你有没有想过将这些正则表达式的庞大减少为类似于树结构的东西?
举个简单的例子:所有需要一个数字的正则表达式都可以从一个正则表达式分支出来,所有的正则表达式都不需要另一个分支。以这种方式,您可以将实际比较的数量减少到沿树的路径,而不是在 10,000 中进行每个比较。
这将需要将提供的正则表达式分解为流派,每个流派都有一个共享测试,如果失败则将它们排除在外。通过这种方式,理论上您可以显着减少实际比较的次数。
如果您必须在运行时执行此操作,您可以解析给定的正则表达式并将它们“归档”为预定义的流派(最容易做到)或当时生成的比较流派(不太容易做到)。
此解决方案不会真正帮助您将“hello”与“[H|h]ello”和“.{0,20}ello”进行比较的示例。一个可能有用的简单情况是:如果您有 1000 个测试,只有在字符串中某处存在“ello”并且您的测试字符串是“goodbye”时才会返回 true;您只需要对“ello”进行一次测试,并且知道需要它的 1000 次测试将不起作用,因此,您不必进行这些测试。
您需要有某种方法来确定给定的正则表达式与另一个正则表达式相比是否“附加”。创建各种正则表达式“层次结构”,允许您确定某个分支的所有正则表达式都不匹配
如果您正在考虑“10,000 个正则表达式”,您需要改变您的流程。如果不出意外,请考虑“要匹配的 10,000 个目标字符串”。然后寻找为处理“大量目标字符串”情况而构建的非正则表达式方法,例如 Aho-Corasick 机器。不过,坦率地说,在使用哪台机器之前,似乎在这个过程中出现了一些问题,因为 10,000 个目标字符串听起来更像是数据库查找,而不是字符串匹配。
您可以将它们组合成大约 20 个一组。
(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)
只要每个正则表达式都有零个(或至少相同数量的)捕获组,您就可以查看捕获的内容以查看哪些模式匹配。
如果 regex1 匹配,则捕获组 1 将具有匹配的文本。如果没有,那就是undefined
/// ...None
null
Aho-Corasick是我的答案。
我有 2000 个类别的事物,每个类别都有要匹配的模式列表。字符串长度平均约为 100,000 个字符。
主要警告: 要匹配的模式都是语言模式,而不是正则表达式模式,例如'cat'
vs 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 条轨迹,_string
长度约为100,000
让我2.09 ms
比631 ms
连续re.search()
315 倍快!.
如果您使用的是真正的正则表达式(与形式语言理论中的正则语言相对应的表达式,而不是一些类似 Perl 的非正则表达式),那么您很幸运,因为正则语言在联合下是封闭的。在大多数正则表达式语言中,管道 (|) 是联合。所以你应该能够构造一个字符串(代表你想要的正则表达式),如下所示:
(r1)|(r2)|(r3)|...|(r10000)
其中括号用于分组,而不是匹配。与此正则表达式匹配的任何内容都至少与您的原始正则表达式之一匹配。
我会说这是一个真正的解析器的工作。中点可能是Parsing Expression Grammar (PEG)。它是模式匹配的高级抽象,一个特点是您可以定义整个语法而不是单个模式。有一些高性能实现通过将语法编译成字节码并在专门的 VM 中运行来工作。
如果您只需要知道哪些正则表达式匹配,我建议您使用 Intel 的 Hyperscan。它是为此目的而建造的。如果您需要采取的行动更复杂,您也可以使用 ragel。虽然它产生一个单一的 DFA 并可能导致许多状态,因此是一个非常大的可执行程序。Hyperscan 采用混合 NFA/DFA/自定义方法进行匹配,可以很好地处理大量表达式。
我几乎建议编写一个“由内而外”的正则表达式引擎——“目标”是正则表达式,“术语”是字符串。
但是,您迭代尝试每一个的解决方案似乎要容易得多。
您可以将正则表达式编译成混合 DFA/ Bucchi 自动机,其中每次 BA 进入接受状态时,您都会标记哪个正则表达式规则“命中”。
Bucchi 对此有点矫枉过正,但修改 DFA 的工作方式可以解决问题。
尝试将它们组合成一个大的正则表达式?
我认为简短的回答是,是的,有一种方法可以做到这一点,并且它是计算机科学所熟知的,我不记得它是什么。
简短的回答是,您可能会发现您的正则表达式解释器在 |'d 一起时已经有效地处理了所有这些,或者您可能会找到一个这样做的。如果没有,是时候谷歌搜索字符串匹配和搜索算法了。
我将Ragel与离开动作一起使用:
action hello {...}
action ello {...}
action ello2 {...}
main := /[Hh]ello/ % hello |
/.+ello/ % ello |
any{0,20} "ello" % ello2 ;
字符串“hello”将调用块中的代码action hello
,然后是action ello
块中的代码,最后是action ello2
块中的代码。
他们的正则表达式非常有限,而是首选机器语言,您示例中的大括号仅适用于更通用的语言。
最快的方法似乎是这样的(代码是 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;
}
哦,你的意思是最快的代码?那时我不知道......