1

我们有一个包含部分 url（字符串）的大型数据库，例如：

  • “example1.com”

  • “example2.com/test.js”

  • “/foo.js”

我们的软件侦听 HTTP 请求并尝试在 HTTP 请求的完整 url 中找到我们数据库的部分 url 之一。

所以我们得到了完整的 url（即：http ://www.example.com/blah.js?foo=bar "）并试图匹配我们数据库的部分模式之一。

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

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

  • 遍历部分 url（字符串）的整个数据库并使用indexOf（在 javascript 中）查看完整 url 是否包含每个部分字符串。

更新：

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

4

2 回答 2

1

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

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

然后散列所有组合，将它们存储在一个数组中，并尝试在另一个包含数据库中所有部分字符串的散列的数组中找到它们中的任何一个。

笔记：

如果你想匹配 url 中的任何字符串，就像它ample在example.com存储方面变得有点复杂，因为 url 中字符串的所有随机组合都是组合公式

wheren是 urlk的长度，是要查找的字符串的长度。根据这个 SO question，url 的最大合理长度是 2000 个字符。并假设您要匹配随机字符串，您的随机字符串k从 1 到 2000 不等，这将导致从 url 生成大量哈希 -n over k每个k从 1 到 2000 的总和。或更准确地说 - 2000！/ (k!*(2000-k)!)不同的哈希值

于 2013-08-14T11:58:03.427 回答
0

你可以做几件事：

  • 不要在客户端处理 URL。JavaScript 会很慢，特别是如果你有很多这样的 URL。您可以创建一个 REST API 并传入 URL 以作为查询参数进行匹配，即domain.com/api/?url=.... 将繁重的工作和内存使用放在服务器端也会减少您的带宽。
  • 将 URL 引导到 RAM 中，并且不要每次都从数据库中读取。在这种情况下，像memcached这样的东西可以完美地工作。
  • 一旦进入 ram，HashTable结构将工作得最好，因为您正在进行简单的匹配。无论你做什么，都要避免字符串比较。

如果您遵循这些建议，您将获得显着的加速。希望这可以帮助。

于 2013-08-13T21:17:27.207 回答