regex - 如何使用正则表达式 (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搜索树将符合要求。 “Tries ”是一篇关于这类事情的非常好的文章，还有Etrie Evolution 中用于替换正则表达式搜索的实现。

要进行整个字符串匹配，您可以添加开始和结束 anchor 状态。如果扫描多行数据，您可以在开头和结尾添加换行符。您还可以删除它为开始不同匹配的部分匹配添加交叉链接的部分。这也允许更快的排除。

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