6

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

仅供参考：我对基于 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://*
4

3 回答 3

3

这是我们非常成功地使用的一种方法（在此处实现）：

添加模式：

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

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

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

运行查询：

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

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

于 2019-04-13T01:48:25.490 回答
2

想到的一种方法是创建模式的树结构。

示例：http://*将包含所有模式（如上所列）。 http://*.site1.com/*将包含所有site1.com的。这可以显着减少需要检查的模式数量。

此外，您可以确定哪些模式是互斥的，以进一步修剪您搜索的列表。

所以首先取出所有的模式并从中创建树。搜索所有根以确定需要分析哪些分支和节点。

通过确定哪些分支是互斥的来改进算法，这样一旦你在给定的分支上找到命中，你就会知道哪些分支/节点不需要访问。

要开始，您可能会很懒惰，您的第一遍可能是对模式进行排序并执行简单的下一个模式是否包含此模式类型逻辑以确定“this”是否包含在下一个中。前任：if( "http://*.site1.com/*".startsWith("http://*") == true )

您可以更复杂地确定一种模式是否确实包含另一种模式，但这会让您开始。

为了更好地确定问题：

“这个模式包含那个模式吗？”

我相信你需要能够解析正则表达式......这篇文章看起来是一个很好的起点来了解如何实现这一点：Parsing regular expressions with recursive descent

于 2013-01-31T13:40:06.053 回答
0

如果这组 URL 的变化不是很快，你真的应该使用一个正则表达式引擎来编译它的模式。Java 提供了其中之一，但如果您想知道哪种模式匹配，它可能并不令人满意。

用于执行此操作并确定哪个匹配的广泛使用的机制是各种词法分析器生成器，例如 FLEX 和类似工具。他们接受每个“词位”的正则表达式，并构建一个集成的 FSA 来识别其中任何一个执行效率极高的词。

当你的集合改变时，你可以调用 Flex。如果速度太慢，请获取 Flex 的开源版本并集成到您的引擎中；它在内部构建 FSA，因此您可以直接使用它。（一些工程可能是必要的）。但是如果你真的有一个高性能匹配问题，一些工作做好它不会打扰你。

如果 URL 集的更改速度快于 FLEX 生成 FSA（奇数）的速度，那么您就遇到了真正的问题。在这种情况下，您可以通过从左到右扫描“正则表达式”并将您看到的字符/谓词集成到现有的区分树中来构建在线区分树。然后匹配包括沿着鉴别树走，执行各种测试；如果你到达一片叶子，你有一个匹配，否则没有。如果处理得当，这可能与 FLEX 生成的自动化一样快，但可能要大得多。

于 2013-02-01T15:49:28.403 回答