高效的字符串匹配算法
我正在尝试构建一个有效的字符串匹配算法。 这将在高容量环境中执行，因此性能至关重要。
这是我的要求：
- 给定域名，即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，但我担心将条目列表准确地表示为正则表达式。
我的问题：根据上面列出的描述，找到一个字符串forms的字符串是否匹配字符串列表中的任何一个字符串的有效方法是什么？
如果您想要自己滚动，我会将条目存储在树结构中。 看看我对另一个关于拼写检查器的SO问题的回答，看看我的意思。
而不是通过“。”来标记结构。 我只想将每个条目视为一个完整的字符串。 无论如何，任何标记化的实现仍然必须对整个字符集进行字符串匹配，因此您可以一次性完成所有操作。
这与常规拼写检查树之间的唯一区别是：
- 匹配需要反向完成
- 你必须考虑通配符
要解决第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也会失败，因为遍历以"*"以外的字符结束。
我会使用正则表达式，只需确保将表达式编译一次（而不是一次又一次地计算）。
你不需要regexp ..只需反转所有的字符串，摆脱’*’，然后放一个标志来指示部分匹配，直到这一点通过。
不知何故，trie或后缀trie看起来最合适。
如果在编译时知道域列表，您可以查看“。”处的标记化。 并使用多个gperf生成的机器。
链接：google for trie http://marknelson.us/1996/08/01/suffix-trees/
我会使用树结构来存储规则，其中每个树节点都包含一个Dictionary。
构造树使得“com”，“net”等是顶级条目，“example”在下一级别，依此类推。 您需要一个特殊标志来指出该节点是通配符。
要执行查找，请按周期拆分字符串，然后向后迭代，根据输入导航树。
这看起来与您所考虑的类似，但假设规则不会更改每次运行，使用基于字典的缓存树将比数组列表更快。
另外，我不得不打赌这种方法比RegEx更快。
您似乎有一套明确定义的关于您认为有效输入的规则 – 您可以考虑使用手写的LL解析器 。 这样的解析器相对容易编写和优化。 通常你会让解析器输出一个描述输入的树结构 – 我会使用这个树作为匹配例程的输入，该例程使用上面描述的规则执行将树与条目列表匹配的工作。
这是一篇关于递归下降解析器的文章 。
假设规则如你所说：文字或以*开头。
Java的：
public static boolean matches(String candidate, List rules) { for(String rule : rules) { if (rule.startsWith("*")) { rule = rule.substring(2); } if (candidate.endsWith(rule)) { return true; } } return false; }
这会扩展到您拥有的规则数量。
编辑：
在这里要清楚。
当我说“排序规则”时，我的意思是用规则字符创建一棵树。
然后你使用匹配字符串来尝试并遍历树（即如果我有一个xyz字符串，我从x字符开始，看看它是否有一个分支，然后是az子）。
对于“通配符”，我会使用相同的概念，但将其“向后”填充，然后使用匹配候选者的背面进行操作。
如果您有很多规则，我会对规则进行排序。
对于非通配符匹配，您迭代每个字符以缩小可能的规则（即，如果它以“w”开头，那么您使用“w”规则等）
如果它是通配符匹配，则执行完全相同的操作，但是您可以使用“向后规则”列表，并且只需将字符串末尾与规则末尾匹配即可。
我尝试使用最长前缀匹配的尝试组合（用于IP网络的路由）。 如果空间是一个问题， 定向非循环Word图可能比尝试更合适。
我将建议树结构方法的替代方案。 使用Burrows-Wheeler转换创建域列表的压缩索引。 有关该技术的完整说明，请参见http://www.ddj.com/architect/184405504?pgno=1 。
看看RegExLib
不确定你的分裂和迭代的想法，但似乎它不会很慢：
像你说的那样，分割域和反向域。 存储基本上可以是一棵树。 使用哈希表来存储TLD。 关键是，例如，“com”，值将是该TLD下的子域的哈希表，迭代的广告。
鉴于您的要求，我认为您正在考虑从字符串末尾（TLD）到主机名工作。 你可以使用正则表达式，但由于你并没有真正使用正则表达式的任何function，我不明白为什么你想要承担他们的成本。 如果你颠倒了字符串，那么你真的只是在寻找前缀匹配（’* .example.com’变成：’是’moc.elpmaxe’我的输入字符串的开头？），这显然不会更明显不需要像regexp那样笨手笨脚的东西。
您用来存储条目列表的结构很大程度上取决于列表的大小以及更改的频率…对于一个巨大的稳定列表，树/特里可能是最高性能的; 经常变化的列表需要一个易于初始化/更新的结构，等等。 没有更多信息，我不愿意建议任何一种结构。
我想我很想用另一个回答你的问题：你在做什么，你认为你的瓶颈是一些字符串匹配以上和简单的字符串比较？ 肯定还有其他东西列在你的性能分析中更高的位置？
我会首先使用明显的字符串比较测试，这些测试在90％的时间都是正确的，如果它们失败则再回到正则表达式
如果它只是匹配字符串，那么你应该看看trie数据结构和算法。 较早的答案表明，如果您的所有通配符在开头都是单个通配符，则可以使用一些特定的算法。 但是，处理通用通配符的要求意味着，为了快速执行，您将需要生成状态机。
这就是正则表达式库为你做的事情：“预编译”正则表达式==生成状态机; 这允许运行时的实际匹配很快。 如果没有非凡的优化工作，您不可能获得明显更好的性能。
如果你想自己动手，我可以说，专门为多个通配符编写自己的状态机生成器应该具有教育意义。 在这种情况下，您需要了解他们在正则表达式库中使用的算法种类……
研究KMP（Knuth-Morris-Pratt）或BM（Boyer-Moore）算法。 这些允许您比线性时间更快地搜索字符串，但需要进行一些预处理。 其他人已经注意到，丢弃领先的星号当然是至关重要的。
这些信息的一个来源是：
KMP： http ： //www-igm.univ-mlv.fr/~lecroq/string/node8.html
BM： http ： //www-igm.univ-mlv.fr/~lecroq/string/node14.html