4

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

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

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

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

4

3 回答 3

1

鉴于您的字符串数量非常多，您的选择必须关注以下几点：

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

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

对于b-tree，我做了一些理论计算，假设b+tree（以节省内部节点的更多空间）并且内部节点被完全占用。通过这种分析，它不适合内存：

  • 通常的磁盘页面大小为 4096 字节。那是一个 b-tree 节点的大小。
  • 字符串的平均大小为 70 字节（越少越好）。
  • 子节点地址有 4 个字节。
  • 一个内部节点拥有 d 个键并有 d+1 个子地址：
    **4096B = 4*(d+1)+70*d <=> d = 4096/75 => d = 54 **

* #internal nodes in memory -> #leaves nodes in disk -> #strings mapped*

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 需要对存储在磁盘中的每个级别进行磁盘访问。

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

  • 由于您知道字符串的总数，因此您可以将其指示给哈希表，并且您不会在桶规模操作中浪费时间（这意味着要重新散列所有元素）。

注意：我发现了一些关于你的ukkonens后缀树的信息。插入是线性的，访问也是顺序的。但是我只发现它与一些 GB 一起使用。以下是关于后缀树算法的一些参考资料：[ref1]、[ref2]和[ref3]。

希望这会有所帮助...

于 2012-10-24T01:18:06.643 回答
1

哈希表在key稀疏的时候很有用，但是key密集的时候就不需要哈希了；您可以使用键（字符串）本身进行索引。为了支持简单的成员资格查询，您可以使用位向量。如果您的数据是 39 位二进制字符串，您将有一个长度为 2^39 的位向量。1 表示字符串存在，0 表示不存在。位向量不会太大，因为它只有 2^39 位 = 2^31 字节 = 2 GB。

要从 q 字母表中的字符串变为整数，您可以将其视为以 q 为底的数字。例如，如果 q=4 且字符串为 3011，则求整数为 3*4^3 + 0*4^2 + 1*4^1 + 1*4^0，等于 197。

关联的整数值会占用大量空间。您可以将它们存储在由字符串索引的数组中；所以在你的例子中，你会有一个 2^39 整数的数组，其中一些插槽是空的。但是，这不太可能适合内存，因为即使每个整数只有一个字节，它也会消耗 TB。在这种情况下，您可以将它们按顺序存储在磁盘文件中。

您可能会发现查找有关位向量/位数组的信息很有帮助：http ://en.wikipedia.org/wiki/Bit_array

维基百科链接讨论了可能适用的压缩。

于 2013-07-25T02:18:07.700 回答
0

...

嗨，鲍勃，

长答案短：经典的 HASH+BTREE 方法强大且超快。

在上述结构中存储 1000 万或 100 亿个字符串都没有关系——你总是有一个非常低的 MAX 搜索阈值。

好吧，你需要 10^12 = 1,000,000,000,000 - 但这是 1 万亿，这让我感到惊讶 - 甚至我的重字符串语料库也在 10 亿的范围内。

只需检查我在 C 中的实现：http: //www.sanmayce.com/#Section13Level

因此，我担心为避免冲突的字符串找到合适的散列函数。有什么好的我可以用吗？

C中最快的哈希表查找函数在这里：

http://www.sanmayce.com/Fastest_Hash/index.html#KT_torture3

它比强大的 CRC32 8slice 变体（Castagnoli 和 Koopman 的）快 300-500%，同时具有类似的碰撞。

于 2012-10-22T15:43:37.657 回答