c# - 高效的字符串匹配算法

Question

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

这是我的要求:

• 给定一个域名，即 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)

我考虑过将条目(和域查找)拆分为数组，颠倒顺序，然后遍历数组。虽然准确，但感觉很慢。

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

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

Answer 1

如果您想要自己滚动，我会将条目存储在树结构中。参见 my answer to another SO question关于拼写检查器，看看我的意思。

而不是用“.”标记结构。字符，我会将每个条目视为一个完整的字符串。无论如何，任何标记化的实现仍然必须对完整的字符集进行字符串匹配，因此您最好一次完成所有操作。

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

1. 需要反向匹配
2. 你必须考虑通配符

要解决第 2 点，您只需在测试结束时检查“*”字符。

一个简单的例子:

条目:

*.fark.com
www.cnn.com

树:

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

检查 www.blog.fark.com 将涉及跟踪树直到第一个 "*"。因为遍历以 "*" 结束，所以存在匹配。

检查 www.cern.com 会在 n,n,c,... 的第二个“n”处失败

检查 dev.www.cnn.com 也会失败，因为遍历结束于 "*" 以外的字符。