Kri*_*aun 5 regex tree search glob
任何人都知道如何调整搜索树来处理有限的正则表达式？给定文件名,任务是查找与该文件名匹配的所有节点.节点可能包含通常的文件名globs(*和？).显然,由于这是一个搜索树,速度至关重要.
编辑:我应该补充一点,速度最重要的情况是排除比赛的平均时间.也就是说,在大多数情况下,匹配将失败.
例如:假设树包含以下节点:
foo,bar,foo*,*bar,foo？bar
搜索foo将返回节点1和3.搜索bar将返回节点2和4.搜索fob将不返回任何节点.搜索fooxbar将返回节点5.搜索foobar将返回节点3和4.
一个aho-corasick搜索树符合要求.阿霍Corasick关于这类事情的一个非常好的文章尝试次数,以及在演进用来代替正则表达式搜索执行Etrie
编辑:要进行整个字符串匹配,可以添加开始和结束锚状态,如果扫描多行数据,则可以添加换行开始和结束.您还可以删除添加交叉链接的部分,以便开始不同匹配的部分匹配,这也允许更快的排除.
检查字符串集中成员资格的另一种算法是CritBit.这没有Regex,但它很简单并且测试完整的字符串.