大型模式集的字符串匹配的高效算法

Question

我正在寻找一种高效的算法，能够找到与特定字符串匹配的所有模式。模式集可能非常大（超过100,000个），并且可能是动态的（随时添加或删除的模式）。模式不一定是标准的regexp，它们可以是regexp的子集或类似于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://*

Answer 1

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

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

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

因此，首先采用所有模式并从中创建树木。搜索所有根以确定需要分析哪些分支和节点。

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

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

您可以更加熟练地确定一种模式是否确实包含另一种模式，但这将帮助您入门。

为了更好地确定问题：

“这个图案里有那个图案吗？”

我相信您需要能够解析正则表达式...这篇文章看起来是一个很好的起点，可以了解如何实现这一点：用递归下降解析正则表达式