问一种有效的大模式集字符串匹配算法

EN

下面是我们非常成功地使用了一种方法(在这里实施)：

添加模式：

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

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

将模式添加到数据结构中时，将其分解为元单词，并将它们存储在符合数据结构的字符串中。维护内部数据结构，将元单词映射回模式词。

运行查询：

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

这很好，因为虽然字符串匹配相当慢，但是您可以缩小实际必须匹配的模式的数量。我们的实现每秒可以针对一组150,000+模式在普通笔记本上执行大约20万次查询。请参阅程序中的台架标记模式来测试这一点。

脑海中浮现的一种方法是创建模式的树结构。

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

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

所以首先把所有的图案都拿出来，然后创造出它们的树。搜索所有根，以确定哪些分支和节点需要分析。

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

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

您可以在判断一个模式是否确实包含另一个模式方面变得更加复杂，但这将使您开始工作。

为了更好地确定这个问题：

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

我相信你需要能够解析正则表达式..。为了理解如何实现这一点，本文似乎是一个很好的起点：解析具有递归下降的正则表达式

如果URL集合变化不快，那么您确实应该使用regex引擎来编译它的模式。Java提供了其中之一，但是如果您想知道哪一种模式匹配，则可能并不令人满意。

一种广泛使用的机制来进行这一和确定哪一个匹配，是各种雷克萨斯生成器，例如，FLEX和类似的工具。他们接受相当于每个"lexeme“的正则表达式，并构建一个完整的FSA来识别其中的任何一个，这是非常高效的执行。

您可以在设置更改时调用Flex。如果速度太慢，那么获取一个开源版本的Flex并集成到您的引擎中；它内部构建FSA，这样您就可以直接使用它。(一些工程可能需要)。但是，如果你真的有一个高性能匹配问题，一些工作做得好不会打扰你。

如果URL集合的变化速度超过FLEX生成FSAs (奇数)的速度，那么您就有了一个真正的问题。在这种情况下，您可以通过从左到右扫描"regex“并将您看到的字符/谓词集成到现有的识别树中来构建在线识别树。然后，匹配包括沿着识别树走下，执行各种测试；如果您到达一片叶子，则有匹配，否则就没有匹配。如果做得对，这可能就像灵活生成的自动化一样快，但很可能要大得多。