使用通配符保存字符串的有效数据结构

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)时间内得到结果，即列表的大小。

这个结构多年来一直运行良好，但现在我希望数据库条目中有通配符，例如：

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

而朴素的搜索将导致一个完整的扫描与O(n)时间的发现。

哪种数据结构可以在小于O(n)的地方找到？

Answer 1

如果所有的url都事先知道，那么您只需构建一个有限的自动机，这将解决您的问题，查询的O(url长度)。

这个有限自动机可以作为regexp构建：

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