performance - 高效的数据结构来保存带有通配符的字符串

Question

这题几乎和Efficient data structure for word lookup with wildcards相反

假设我们有一个urls

的数据库

http://aaa.com/
http://bbb.com/
http://ccc.com/
....

要查找 url 是否在列表中，我可以进行 binary-search 并在 O(log n) 中获取结果时间，n 列表的大小。

这种结构多年来一直运行良好，但现在我想在数据库条目中使用通配符，例如:

http://*aaa.com/*
http://*bbb.com/*
http://*ccc.com/
....

天真的搜索会导致用 O(n) 时间进行查找的完整扫描。

哪个数据结构可以在 O(n) 的时间内找到？

Answer 1

如果所有的 url 都是预先知道的，那么你可以只构建一个有限自动机，这将解决你的查询问题，时间复杂度为 O(url length)。

这个有限自动机可以构建为正则表达式:

http://(.*aaa\.com/.*|.*bbb\.com/.*|.*ccc\.com/)$

这是一些 python 代码。 re.compile()之后，每次查询都非常快。

import re

urls = re.compile("http://(.*aaa\.com/.*|.*bbb\.com/.*|.*ccc\.com/)$")

print urls.match("http://testaaa.com/") is not None
> True
print urls.match("http://somethingbbb.com/dir") is not None
> True
print urls.match("http://ccc.com/") is not None
> True
print urls.match("http://testccc.com/") is not None
> True
print urls.match("http://testccc.com/ddd") is not None
> False
print urls.match("http://ddd.com/") is not None
> False