一种有效的大模式集字符串匹配算法
一种有效的大模式集字符串匹配算法
提问于 2013-01-31 12:56:24
我正在寻找一个高效的算法，能够找到所有匹配特定字符串的模式。模式集可以非常大(超过100,000)和动态(任何时候添加或删除的模式)。模式不一定是标准的regexp，它们可以是regexp的子集，也可以类似于shell模式(即：file-*.txt)。正则表达式子集的解决方案是首选的(如下所述).
FYI:我对基于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://*Stack Overflow用户
发布于 2019-04-13 01:48:25
下面是我们非常成功地使用了一种方法(在这里实施)：
添加模式：
对于任何模式，都存在一组字符串必须包含的子字符串，以便有机会与其匹配。把这些元词叫做。例如：
dog*fish -> [dog, fish]
[lfd]og -> [og]
dog? -> [dog]将模式添加到数据结构中时，将其分解为元单词，并将它们存储在符合数据结构的字符串中。维护内部数据结构，将元单词映射回模式词。
运行查询：
给定一个输入字符串，使用您构建的数据结构来获取包含在该字符串中的所有元单词。然后，使用您创建的映射，测试与这些元单词对应的模式。
这很好，因为虽然字符串匹配相当慢，但是您可以缩小实际必须匹配的模式的数量。我们的实现每秒可以针对一组150,000+模式在普通笔记本上执行大约20万次查询。请参阅程序中的台架标记模式来测试这一点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14626339
复制相关文章
相似问题
腾讯云开发者
