匹配从吨模式的字符串

Question

我想制作一个URL匹配系统。它将以这种方式工作：

数据库将包含许多模式。像这样的模式的一些元数据：

pattern1, keyword 
pattern2, keyword 
... 
... 

我有一个输入URL。如htttp：//example.com/blabla/111/2222/detail.htm

系统将获取输入和输出输入URL的最匹配模式的关键字。每秒会有超过20,000个请求。

我们需要设计的是模式和数据库模型。我已经花了2周时间在这个系统中。

我在考虑匹配树中的URL。

树中的所有节点都能够做2种输出：哪个节点应该继续匹配URL，或节点知道哪个关键字应该应用到URL。

每个节点都将连接一个回调（存储在db中的脚本）。所以不同的节点会有不同的行为。

但我们拥有的东西是吨模式。我想我需要有一个工具来将模式转换为“节点”。或者至少可以使用数据库中的模式构建具有现有节点的树。

我还在想树生成。但应该有更好的方法。

任何想法都会非常有帮助。谢谢！！！

Answer 1

你需要一个工业强度的字符串匹配算法：http://en.wikipedia.org/wiki/String_searching_algorithm。我认为数据库支持的方法不会奏效，因为它听起来像需要模式匹配，而不是精确的前缀匹配。

但是，如果您使用的是前缀匹配（从头开始的最长匹配），那么您可以使用前缀trie，即trie。如果我是你，我会使用数据库作为持久存储，但保留我的匹配内存中的匹配trie。

Answer 2

首先，请阅读本文：

Regular Expression Matching Can Be Simple And Fast

在正则表达式的符号，你所拥有的是一个简单的 “交替”：

pattern1|pattern2|pattern3|... 

...有你想要的附加约束要知道哪个模式匹配。我相信增加“汤普森NFA”来提供这些细节将是直截了当的。 （想法：在内部，在每个模式的末尾放置一个独特的魔法标记以唯一标识模式，魔术标记将匹配空字符串...因此，当您的匹配引擎命中一个时，它立即知道哪个模式匹配。）

这会给你引擎的正则表达式的全部力量。即使你不想从那篇论文中调整NFA实现，在正则表达式中也有大量的理论和实践工作。所以我肯定会从大的交替正则表达式开始，并从那里开始工作。

为了获得更好的速度，你可以尝试使用正则表达式优化器（类似于Perl的Regexp::Optimizer），然后再将大的交替regexp转换为NFA。

或者你可能想从一个通用的正则表达式引擎（如PCRE）开始，看看它是否足够快。