有效地查询一个字符串与多个正则表达式

Question

假设我有10,000个正则表达式和一个字符串,我想知道字符串是否与其中任何一个匹配并获得所有匹配.执行此操作的简单方法是仅针对所有正则表达式逐个查询字符串.有更快,更有效的方法吗？

编辑:我尝试用DFA替换它(lex)这里的问题是它只会给你一个单一的模式.如果我有一个字符串"hello"和模式"[H | h] ello"和".{0,20} ello",DFA只会匹配其中一个,但我希望它们都能击中.

Answer 1

我过去遇到过类似的问题.我使用了类似于akdom建议的解决方案.

我很幸运,我的正则表达式通常有一些必须出现在它匹配的每个字符串中的子字符串.我能够使用简单的解析器提取这些子串,并使用Aho-Corasick算法在FSA中对它们进行索引.然后使用索引快速消除所有与给定字符串不匹配的正则表达式,只留下几个正则表达式来检查.

我在LGPL下发布了Python/C模块的代码.请参阅Google代码托管上的esmre.

Answer 2

我们必须在我曾经工作过的产品上做到这一点.答案是将所有正则表达式编译成确定性有限状态机(也称为确定性有限自动机或DFA).然后,可以在字符串上逐个字符地遍历DFA,并且只要其中一个表达式匹配,就会触发"匹配"事件.

它的优点是运行速度快(每个字符仅比较一次),如果添加更多表达式,则不会变慢.

缺点是它需要一个巨大的自动机数据表,并且有许多类型的正则表达式不受支持(例如,反向引用).

我们使用的那个是当时我们公司的C++模板螺母手工编码的,所以不幸的是我没有任何FOSS解决方案指向你.但是如果你使用" DFA " 谷歌正则表达式或正则表达式,你会找到能指向正确方向的东西.

Answer 3

这是词法分析器的工作方式.

正则表达式被转换为单个非确定性自动机(NFA),并且可能在确定性自动机(DFA)中进行转换.

生成的自动机将尝试立即匹配所有正则表达式,并将在其中一个上成功.

有许多工具可以帮助你,它们被称为"词法生成器",并且有一些解决方案适用于大多数语言.

你没有说你使用的是哪种语言.对于C程序员,我建议看一下re2c工具.当然,传统的(f)lex总是一种选择.

Answer 4

Martin Sulzmann在这个领域做了很多工作.他有一个HackageDB项目,在这里简单解释,使用偏导数似乎是为此量身定做的.

使用的语言是Haskell,因此如果需要的话,将非常难以翻译成非函数式语言(我认为翻译到许多其他FP语言仍然会非常困难).

代码不是基于转换为一系列自动机然后组合它们,而是基于对正则表达式本身的符号操作.

此外,代码非常具有实验性,Martin不再是教授,而是"有收益的工作"(1),因此可能不感兴趣/无法提供任何帮助或意见.

1. 这是一个笑话 - 我喜欢教授,聪明的人尝试工作越少,我获得报酬的机会就越大!

Answer 5

10,000 regexen呃？ Eric Wendelin关于层次结构的建议似乎是一个好主意.你有没有想过将这些regexen的巨大程度降低到像树状结构这样的东西？

举一个简单的例子:所有需要数字的regexen都可以从一个正则表达式检查分支,所有regexen不需要一个另一个分支.通过这种方式,您可以将实际比较的数量减少到沿树的路径,而不是在10,000中进行每次比较.

这将需要分解提供给类型的regexen,每个类型都有一个共享测试,如果失败则会排除它们.通过这种方式,理论上可以显着减少实际比较的次数.

如果你必须在运行时这样做,你可以解析你给定的正则表达式并将它们"归档"为预定义的类型(最容易做)或当时生成的比较类型(不那么容易).

您将"hello"与"[H | h] ello"和".{0,20} ello"进行比较的示例将无法真正得到此解决方案的帮助.这可能有用的一个简单情况是:如果你有1000个测试,如果"ello"存在于字符串中的某个位置并且你的测试字符串是"goodbye",那么它只会返回true.你只需要对"ello"进行一次测试,并且知道需要它的1000次测试将不起作用,因此,你不必这样做.

Answer 6

如果您正在考虑"10,000 regexes",那么您需要改变您的流程.如果不出意外,请考虑"10,000个匹配的目标字符串".然后寻找用于处理"目标字符串的船载"情况的非正则表达式方法,如Aho-Corasick机器.坦率地说,似乎有些东西在使用过程中要比使用哪台机器早得多,因为10,000个目标字符串听起来更像是数据库查找而不是字符串匹配.

Answer 7

阿霍-科拉西克就是我的答案。

我有 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长度约为2000 条，与连续运行100,000相比，速度快了 315 倍！。2.09 ms631 msre.search()

Answer 8

你需要有一些方法来确定一个给定的正则表达式是否与另一个正相关.创建各种各样的正则表达式"层次结构",允许您确定某个分支的所有正则表达式都不匹配

Answer 9

您可以将它们组合成 20 个一组。

(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)

只要每个正则表达式都有零个（或至少相同数量的）捕获组，您就可以查看捕获的内容以查看匹配的模式。

如果 regex1 匹配，捕获组 1 将具有匹配的文本。如果没有，那就是undefined/ None/ null/...