高效的字符串匹配算法

我正在尝试构建一个有效的字符串匹配算法.这将在高容量环境中执行,因此性能至关重要.

这是我的要求:

给定域名,即www.example.com,确定它是否与条目列表中的"匹配".

参赛作品可以是绝对匹配,即www.example.com.

参赛作品可能包含通配符,即*.example.com.

通配符条目从最定义的级别开始匹配.例如,*.example.com将匹配www.example.com,example.com和sub.www.example.com.

未嵌入通配符条目,即sub.*.example.com将不是条目.

语言/环境:C#(.Net Framework 3.5)

我已经考虑将条目(和域查找)拆分成数组,颠倒顺序,然后迭代数组.虽然准确,但感觉很慢.

我考虑过正则表达式,但我担心将条目列表准确地表示为正则表达式.

我的问题:根据上面列出的描述,找到一个字符串形式的字符串是否匹配字符串列表中的任何一个字符串的有效方法是什么？

如果您想要自己滚动,我会将条目存储在树结构中.请参阅我对另一个关于拼写检查器的SO问题的回答,看看我的意思.

而不是通过"."来标记结构.字符,我只是将每个条目视为一个完整的字符串.无论如何,任何标记化的实现仍然必须对整个字符集进行字符串匹配,因此您也可以一次性完成所有操作.

这与常规拼写检查树之间的唯一区别是:

匹配需要反向完成

你必须考虑通配符

要解决第2点,您只需在测试结束时检查"*"字符.

一个简单的例子:

项:

*.fark.com
www.cnn.com

树:

m -> o -> c -> . -> k -> r -> a -> f -> . -> *
                \
                 -> n -> n -> c -> . -> w -> w -> w

检查www.blog.fark.com将涉及到树的追踪到第一个"*".因为遍历结束于a "*",所以存在匹配.

检查www.cern.com会在n,n,c,......的第二个"n"上失败

检查dev.www.cnn.com也会失败,因为遍历结束于除了之外的字符"*".

我会使用正则表达式,只需确保将表达式编译一次(而不是一次又一次地计算).

你不需要regexp ..只需反转所有的字符串,摆脱'*',然后放一个标志来指示部分匹配,直到这一点通过.

不知何故,trie或后缀trie看起来最合适.

如果在编译时知道域列表,您可以查看"."处的标记化.并使用多个gperf生成的机器.

链接:google for trie http://marknelson.us/1996/08/01/suffix-trees/