正则表达式（glob）搜索树

Question

任何人都知道如何适应搜索树来处理有限的正则表达式？任务是，根据文件名，找到与该文件名匹配的所有节点。节点可能包含通常的文件名称（*和？）。显然，由于这是一个搜索树，速度是关键。

编辑：我应该补充一点，速度最重要的情况是排除比赛的平均时间。也就是说，在大多数情况下，匹配将失败。

个例子：假设树包含以下节点：

FOO，酒吧，FOO *，*酒吧，酒吧富

搜索富将返回节点1和3 搜索栏？将返回节点2和4. 搜索FOB将不返回任何节点。 正在搜索fooxbar将返回节点5. 搜索foobar会返回节点3和4.

Answer 1

aho-corasick搜索树将符合法案。 Aho-Corasick关于这样的事情Tries一篇很好的文章，并在进化用来代替正则表达式搜索Etrie

编辑的实现：做全字符串匹配，可以添加开始和结束锚状态，如果扫描多行数据，你可以添加新行开始和结束。您也可以删除添加交叉链接的部分，从而开始不同的匹配，这也允许更快的排除。

另一种用于检查字符串集中成员资格的算法是CritBit。这不具有正则表达式，但它很简单，并测试完整的字符串。