javascript - 用于存储部分 url 的数据结构，其中搜索速度优先

Question

我们有一个包含部分网址(字符串)的大型数据库，例如:

• “example1.com”

• “example2.com/test.js”

• “/foo.js”

我们的软件监听 HTTP 请求，并尝试在 HTTP 请求的完整 URL 中查找数据库的部分 URL。

因此，我们获得完整的网址(即:http://www.example.com/blah.js?foo=bar“)并尝试匹配我们数据库的部分模式之一。

如果我们只关心搜索速度，那么存储部分 URL 数据库的最佳数据结构是什么？

<小时/>

现在，这就是我们所做的:

• 迭代整个数据库的部分 URL(字符串)并使用 indexOf (在 JavaScript 中)查看完整 url 是否包含每个部分字符串。

更新:

该软件是 Firefox 的扩展，在 Firefox 上用 Javascript 编写 Addon SDK .

Answer 1

假设您的部分字符串只是域名和/或页面名称，您可以尝试从 URL 末尾开始生成所有可能的组合:

 http://www.example.com/blah.js?foo=bar
 blaj.js
 example.com/blah.js
 www.example.com/blah.js

然后对所有组合进行哈希处理，将它们存储在一个数组中，并尝试在另一个包含数据库中所有部分字符串的哈希值的数组中查找其中的任何一个。

注意:

如果您想匹配网址中的任何字符串，例如 example.com 中的 ample，那么它在存储方面就变得有点复杂，因为都是随机的 combinations url 中的字符串数量为

其中 n 是 url 的长度，k 是要查找的字符串的长度。根据this SO question url 的最大合理长度为 2000 个字符。假设您想要匹配随机字符串，则 k 的范围为 1 到 2000，这将导致从 url 生成大量哈希值 - n 与 k 的总和 对于从 1 到 2000 的每个 k。 或者更准确地说 - 2000! / (k!*(2000-k)!)不同的哈希值