string - 选择合适的数据结构(哈希表与后缀树)来索引非常大的相似字符串集

Question

我有一大组字符串，顺序约为 10^12 左右，我需要选择一个合适的数据结构，以便提供一个字符串，我可以检索和关联整数值，例如 O(log(n))或 O(m) 时间，其中 'n' 是字符串列表的长度，'m' 是每个字符串的长度。

我们可以期望我们的字符串集，每个长度为 'm' 并在大小为 'q' 的某个字母表上编码，几乎涵盖了这个长度的所有可能的字符串。例如，假设我们有 10^12 个长度为 m = 39 的完全唯一的二进制字符串。这意味着我们已经覆盖了这个长度的所有可能的二进制字符串集合的约 54%。

因此，我担心为避免冲突的字符串找到合适的散列函数。有什么好的我可以用吗？索引我的 n 个字符串集需要多长时间？

还是我应该使用后缀树？我们知道 Ukkonen 的算法允许线性时间构造，我的猜测是，鉴于大量相似的字符串，这将节省空间？

Answer 1

鉴于您的字符串数量非常多，您的选择必须集中在以下几点:

1. Are your indexing structures going to fit in memory?

对于 哈希表 答案显然不是。因此访问时间将比 O(1) 慢得多。您仍然只需要一个磁盘访问(整个插入过程将是 O(N))。

对于 b-tree 我做了一些理论计算，假设 b+tree (为了在内部节点中节省更多空间)并且内部节点也被完全占用。通过这种分析，它不适合内存:

通常的磁盘页面大小是 4096 字节。那是一个 b 树节点的大小。

字符串的平均大小为 70 字节(越少越好)。

子节点地址有 4 个字节。

一个内部节点拥有 d 个键并有 d+1 个子地址:
**4096B = 4*(d+1)+70*d <=> d = 4096/75 => d = 54 **

* #内存中的内部节点 -> #将节点留在磁盘中 -> #strings 映射*

0 个内部节点 -> 1 个叶子节点 -> 映射了 53 个字符串
1 个内部节点 -> 使用了 54 个叶子节点(每个节点有 53 个叶子节点)-> 53² 映射的字符串
1+54 个内部节点 -> 54² 叶节点已使用 -> 53³ 个字符串映射
...
...+54⁵ 内部节点 -> 54⁶ 叶节点 = 53⁷ 映射的字符串

53⁷ > 10^12 , but 54⁵*4096 bytes > 1TB of memory

如果您的字符串不是均匀分布的，您可以探索常见的前缀。这样，内部节点可能能够寻址更多子节点，从而节省内存。 BerkeleyDB有那个选项。

2. What kind of access are you going to employ? Large or small number of reads?
If you have large number of reads, are they random or sequential?  

如果您的访问是顺序的，您仍然可以从 btree 中受益，因为您将大量使用缓存节点(不需要磁盘访问)并且叶子是顺序链接的(b+tree)。这对于范围查询也很有用(我认为并非如此)。如果您的访问是完全随机的，那么哈希表会更快，因为它总是只需要一个磁盘访问，而 btree 需要对存储在磁盘中的每一级进行磁盘访问。

如果您要进行少量访问，则最好使用哈希表，因为插入总是更快。

由于您知道字符串的总数，您可以将其指示给哈希表，并且您不会在存储桶缩放操作中浪费时间(这意味着要重新哈希所有元素)。

注:我发现了一些关于你的 ukkonens后缀树。插入是线性的，访问也是顺序的。但是我只发现它与一些 GB 一起使用。以下是一些关于后缀树算法的引用: [ref1] , [ref2]和 [ref3] .

希望这会有所帮助......