algorithm - 存储 URL 列表的有效方法

Question

我需要存储万亿个 URL 列表，其中每个 URL 列表将包含约 50 个 URL。将它们压缩以进行磁盘存储的最节省空间的方法是什么。

我在考虑先删除无用的信息，如“http://”，然后构建一个最小的有限状态自动机并保存它。

另一种选择是构建一个逗号分隔的 URL 字符串，并使用 GZIP 或 BZ2 等常规压缩方式压缩该字符串。

如果我不关心速度，哪种解决方案会产生最佳压缩效果。

Answer 1

考虑到 URL 的数量以及它们中的大多数使用或多或少相同的结构和命名模式这一事实，我会选择使用索引和分词器。首先使用分词器收集尽可能多的单词并将它们保存在索引中。然后，您可以用列表中的索引替换每个标记:

http://www.google.com/search?q=hello+world (42 bytes)== 会给你

http://=> 1万维网。 => 2google.com => 3搜索 => 4你好 => 5世界 => 6

URL 将变为:1,2,3,'/',4,'?','q','=',5,'+',6

鉴于许多 URL 将是一个公共(public)大域的子域，并且其中大多数将使用相同的常用英语单词(想想所有关于我们的页面或职业...)，您可能会结束建立一个不太大的索引(英语中大约有 50000 个常用词，法语中有 70000 个)。

然后您可以压缩索引和标记化的 URL 以获得更多空间。

解析 URL 和构建索引的算法复杂度为 O(n) 和 O(nlogn)。