regex - 具有非常大的模式集的字符串匹配的高效算法

Question

我正在寻找一种能够找到与特定字符串匹配的所有模式的高效算法。模式集可以非常大(超过 100,000)和动态(随时添加或删除模式)。模式不一定是标准的正则表达式，它们可以是正则表达式的子集或类似于 shell 模式的东西(即: file-*.txt )。 首选正则表达式子集的解决方案(如下所述)。

仅供引用:我对基于 RegExp 列表的蛮力方法不感兴趣。

简单的regexp，我的意思是支持?的正则表达式, * , + , 字符类 [a-z]可能还有逻辑运算符 | .

为了澄清我的需要:我希望找到与 URL 匹配的所有模式:

http://site1.com/12345/topic/news/index.html

响应应该是基于下面设置的模式的这些模式。

http://*.site1.com/*/topic/*
http://*.site1.com/* 
http://*

图案集:

http://*.site1.com/*/topic/*
http://*.site1.com/*/article/*
http://*.site1.com/* 
http://*.site2.com/topic/*
http://*.site2.com/article/*
http://*.site2.com/* 
http://*

Answer 1

这是我们非常成功地使用的方法( implementation here ):

添加图案:

对于任何模式，都存在一个字符串必须包含的一组子字符串，以便有机会与之匹配。称这些元词。例如:

dog*fish -> [dog, fish]
[lfd]og  -> [og]
dog?     -> [dog]

当您向数据结构添加模式时，将其分解为元词并将它们存储在 Aho-Corasick 字符串匹配数据结构中。维护内部数据结构以将元词映射回模式词。

运行查询:

给定一个输入字符串，使用您构建的 Aho-Corasick 数据结构来获取该字符串中包含的所有元词。然后，使用您创建的 map ，测试与这些元词对应的模式。

这很有效，因为虽然字符串匹配相当慢，但您可以非常快速地缩小实际必须匹配的模式数量。我们的 implementation可以在普通笔记本电脑上每秒对 150,000 多个模式执行大约 200,000 次查询。请参阅程序中的基准测试模式以进行测试。