5

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

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

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

如果树包含以下节点：

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

1 回答 1

9

一个Aho-Corasick搜索树将符合要求。“ Tries ” 是一篇关于这类事情的非常好的文章，以及Evolution 中用于替换正则表达式搜索的Etrie实现。

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

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

于 2009-02-25T19:03:30.687 回答