如何调整搜索树以处理有限的正则表达式?
给定文件名,我需要找到与该文件名匹配的所有节点。节点可能包含通常的文件名 glob(* 和 ?)。由于这是一棵搜索树,因此速度至关重要。
我应该补充一点,速度最重要的情况是排除比赛的平均时间。在大多数情况下,匹配会失败。
如果树包含以下节点:
foo, bar, foo*, *bar, foo?bar
最佳答案
安 Aho-Corasick搜索树将符合要求。 “Tries ”是一篇关于这类事情的非常好的文章,还有Etrie Evolution 中用于替换正则表达式搜索的实现。
要进行整个字符串匹配,您可以添加开始和结束 anchor 状态。如果扫描多行数据,您可以在开头和结尾添加换行符。您还可以删除它为开始不同匹配的部分匹配添加交叉链接的部分。这也允许更快的排除。
另一种用于检查字符串集中成员身份的算法是 CritBit .这没有正则表达式,但它很简单并且测试完整的字符串。
关于regex - 如何使用正则表达式 (glob) 搜索文件树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/587288/