regex - 针对多个正则表达式有效地查询一个字符串

Question

假设我有 10,000 个正则表达式和一个字符串，我想找出字符串是否与其中任何一个匹配并获取所有匹配项。最简单的方法是针对所有正则表达式逐一查询字符串。有没有更快、更有效的方法呢？

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

score 12 · Accepted Answer

我们必须在我曾经做过的产品上这样做。答案是将所有正则表达式一起编译成确定性有限状态机（也称为确定性有限自动机或DFA）。然后，DFA 可以逐个字符地遍历您的字符串，并在其中一个表达式匹配时触发“匹配”事件。

优点是它运行速度快（每个字符只比较一次）并且如果添加更多表达式也不会变慢。

缺点是它需要一个庞大的自动机数据表，并且有许多类型的正则表达式不受支持（例如，反向引用）。

我们使用的那个是当时我们公司的一个 C++ 模板 nut 手工编码的，所以很遗憾，我没有任何 FOSS 解决方案可以为您指明方向。但是，如果您使用“ DFA ”搜索正则表达式或正则表达式，您会发现可以为您指明正确方向的内容。

score 12 · Accepted Answer

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

正则表达式被转换为单个非确定性自动机 (NFA)，并可能转换为确定性自动机 (DFA)。

生成的自动机将尝试一次匹配所有正则表达式，并在其中一个上成功。

有很多工具可以在这里为您提供帮助，它们被称为“词法分析器生成器”，并且有适用于大多数语言的解决方案。

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

score 12 · Accepted Answer

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

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

我将 LGPL 下的代码作为 Python/C 模块发布。请参阅Google 代码托管上的 esmre。

score 10 · Accepted Answer

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

使用的语言是 Haskell，因此如果需要的话，将很难翻译成非功能性语言（我认为翻译成许多其他 FP 语言仍然非常困难）。

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

此外，该代码非常具有实验性，Martin 不再是教授，而是从事“有酬工作”(1)，因此可能不感兴趣/无法提供任何帮助或输入。

这是个笑话——我喜欢教授，聪明的人越少努力工作，我获得报酬的机会就越大！

score 8 · Accepted Answer

10,000 正则表达式是吗？ Eric Wendelin 的层次结构建议似乎是个好主意。你有没有想过将这些正则表达式的庞大减少为类似于树结构的东西？

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

这将需要将提供的正则表达式分解为流派，每个流派都有一个共享测试，如果失败则将它们排除在外。通过这种方式，理论上您可以显着减少实际比较的次数。

如果您必须在运行时执行此操作，您可以解析给定的正则表达式并将它们“归档”为预定义的流派（最容易做到）或当时生成的比较流派（不太容易做到）。

此解决方案不会真正帮助您将“hello”与“[H|h]ello”和“.{0,20}ello”进行比较的示例。一个可能有用的简单情况是：如果您有 1000 个测试，只有在字符串中某处存在“ello”并且您的测试字符串是“goodbye”时才会返回 true；您只需要对“ello”进行一次测试，并且知道需要它的 1000 次测试将不起作用，因此，您不必进行这些测试。

score 6 · Accepted Answer

您需要有某种方法来确定给定的正则表达式与另一个正则表达式相比是否“附加”。创建各种正则表达式“层次结构”，允许您确定某个分支的所有正则表达式都不匹配

score 6 · Accepted Answer

如果您正在考虑“10,000 个正则表达式”，您需要改变您的流程。如果不出意外，请考虑“要匹配的 10,000 个目标字符串”。然后寻找为处理“大量目标字符串”情况而构建的非正则表达式方法，例如 Aho-Corasick 机器。不过，坦率地说，在使用哪台机器之前，似乎在这个过程中出现了一些问题，因为 10,000 个目标字符串听起来更像是数据库查找，而不是字符串匹配。

score 5 · Accepted Answer

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

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

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

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

score 4 · Accepted Answer

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 倍快！.

score 3 · Accepted Answer

如果您使用的是真正的正则表达式（与形式语言理论中的正则语言相对应的表达式，而不是一些类似 Perl 的非正则表达式），那么您很幸运，因为正则语言在联合下是封闭的。在大多数正则表达式语言中，管道 (|) 是联合。所以你应该能够构造一个字符串（代表你想要的正则表达式），如下所示：

(r1)|(r2)|(r3)|...|(r10000)

其中括号用于分组，而不是匹配。与此正则表达式匹配的任何内容都至少与您的原始正则表达式之一匹配。

score 2 · Accepted Answer

我会说这是一个真正的解析器的工作。中点可能是Parsing Expression Grammar (PEG)。它是模式匹配的高级抽象，一个特点是您可以定义整个语法而不是单个模式。有一些高性能实现通过将语法编译成字节码并在专门的 VM 中运行来工作。

免责声明：我唯一知道的是LPEG，一个Lua库，并且（对我来说）掌握基本概念并不容易。

score 2 · Accepted Answer

如果您只需要知道哪些正则表达式匹配，我建议您使用 Intel 的 Hyperscan。它是为此目的而建造的。如果您需要采取的行动更复杂，您也可以使用 ragel。虽然它产生一个单一的 DFA 并可能导致许多状态，因此是一个非常大的可执行程序。Hyperscan 采用混合 NFA/DFA/自定义方法进行匹配，可以很好地处理大量表达式。

score 1 · Accepted Answer

我几乎建议编写一个“由内而外”的正则表达式引擎——“目标”是正则表达式，“术语”是字符串。

但是，您迭代尝试每一个的解决方案似乎要容易得多。

score 1 · Accepted Answer

您可以将正则表达式编译成混合 DFA/ Bucchi 自动机，其中每次 BA 进入接受状态时，您都会标记哪个正则表达式规则“命中”。

Bucchi 对此有点矫枉过正，但修改 DFA 的工作方式可以解决问题。

score 0 · Accepted Answer

0

尝试将它们组合成一个大的正则表达式？

于 2008-10-10T20:48:29.120 回答

score 0 · Accepted Answer

我认为简短的回答是，是的，有一种方法可以做到这一点，并且它是计算机科学所熟知的，我不记得它是什么。

简短的回答是，您可能会发现您的正则表达式解释器在 |'d 一起时已经有效地处理了所有这些，或者您可能会找到一个这样做的。如果没有，是时候谷歌搜索字符串匹配和搜索算法了。

score 0 · Accepted Answer

我将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块中的代码。

他们的正则表达式非常有限，而是首选机器语言，您示例中的大括号仅适用于更通用的语言。

score -1 · Accepted Answer

最快的方法似乎是这样的（代码是 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;
}

哦，你的意思是最快的代码？那时我不知道......

regex - 针对多个正则表达式有效地查询一个字符串

18 回答 18

Related

Reference