如何使用正则表达式（glob）搜索文件树

Question

如何调整搜索树以处理有限的正则表达式？

给出文件名，我需要找到所有与该文件名匹配的节点。节点可能包含通常的文件名glob（*和？）。由于这是一个搜索树，因此速度至关重要。

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

如果树包含以下节点：

foo, bar, foo*, *bar, foo?bar 

• 搜索“ foo”将返回节点1和3。
• 搜索“ bar”将返回节点2和4。
• 搜索“ fob”将不返回任何节点。
• 搜索“ fooxbar”将返回节点5。
• 搜索“ foobar”将返回节点3和4。

Answer 1

一棵aho-corasick搜索树很合适。 Aho-Corasick关于这种事情Tries的很好的文章，以及Evolution用来代替正则表达式搜索的实现Etrie

编辑：要进行整个字符串匹配，可以添加开始和结束锚点状态，如果扫描多行数据，则可以将换行符添加到开始和结束。您也可以删除为部分匹配添加交叉链接的部分，从而开始不同的匹配，这也可以加快排除速度。

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