如何使用正则表达式（glob）搜索文件树
如何调整搜索树来处理有限的正则表达式？
给定一个文件名，我需要找到与该文件名匹配的所有节点。 节点可能包含常用的文件名 glob（* 和 ?）。 由于这是一棵搜索树，因此速度至关重要。
我应该补充一点，速度最重要的情况是排除一场比赛的平均时间。 大多数情况下匹配都会失败。
如果树包含以下节点：
foo, bar, foo*, *bar, foo?bar
- 搜索“foo”将返回节点 1 和 3。
- 搜索“bar”将返回节点 2 和 4。
- 搜索“fob”将不返回任何节点。
- 搜索“fooxbar”将返回节点 5。
- 搜索“foobar”将返回节点 3 和 4。
How do I adapt a search tree to handle limited regular expressions?
Given a file name, I need to find all nodes matching that file name. Nodes may contain usual file name globs (* and ?). Since this is a search tree, speed is of the essence.
I should add that the most important case for speed is the average time to rule out a match. In most cases matching will fail.
If the tree contained the following nodes:
foo, bar, foo*, *bar, foo?bar
- Searching for "foo" would return nodes 1 and 3.
- Searching for "bar" would return nodes 2 and 4.
- Searching for "fob" would return no nodes.
- Searching for "fooxbar" would return node 5.
- Searching for "foobar" would return nodes 3 and 4.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Aho-Corasick 搜索树就可以满足要求。 “尝试”是一篇关于此类的非常好的文章事物和 Etrie 实现来替代正则表达式搜索。
要进行整个字符串匹配，您可以添加开始和结束锚点状态。 如果扫描多行数据，您可以在开头和结尾添加换行符。 您还可以删除为部分匹配添加交叉链接以开始不同匹配的部分。 这也允许更快的排除。
检查字符串集中成员资格的另一种算法是 CritBit。 它没有正则表达式，但它很简单并且测试完整的字符串。
An Aho-Corasick search tree would fit the bill. "Tries" is a very good article about this sort of thing and the Etrie implementation used in Evolution to replace regex searching.
To do the whole string matching, you can add beginning and ending anchor states. If scanning multi-line data, you could add the newline to the begin and end. You could also remove the part where it adds the cross linking for the partial matching starting a different match. This also allows faster exclusion.
Another algorithm for checking for membership in a string set is CritBit. This doesn't have Regex, but it is simple and tests complete strings.