为索引大量相似字符串，选择合适的数据结构（哈希表 vs 后缀树）

Question

我有一组大约10^12个字符串，需要选择适当的数据结构，以便在提供一个字符串的情况下，可以在类似于O(log(n))或O(m)时间内检索并关联整数值，其中'n'是字符串列表的长度，'m'是每个字符串的长度。

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

因此，我担心查找适当的哈希函数来避免碰撞。我能用什么好的哈希函数吗？索引我的n个字符串需要多长时间？

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

- Bob

---

你期望的最大“m”是多少？在大小为“q”的字母表中，每个元素是一个字符还是一组字符？如果是一组字符，每个字母表元素的最大大小是多少？ - Leaurus

@Leaurus 我期望的最大'm'是在40到100之间。字母表中的每个元素都是一个字符（例如，q = 6意味着字符是1到6的整数）。 - Bob

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 **

* #在内存中的内部节点 -> 在磁盘中的叶子节点 -> 映射的字符串数量*

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+树）。这对于范围查询也非常有用（我认为这不是情况）。如果您的访问完全随机，则 hashtable 更快，因为它始终只需要一个磁盘访问，而 btree 需要每个存储在磁盘中的级别都需要一个磁盘访问。

• 如果您要进行少量访问，则由于插入速度始终更快，建议使用 hashtable。

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

注意：我找到了关于你的ukkonens后缀树的一些信息。插入是线性的，访问也是顺序的。然而，我只发现它被用于一些GB级别的数据。这里有一些关于后缀树算法的参考资料：[ref1], [ref2] 和 [ref3]。

希望这能在某种程度上有所帮助...

- Leaurus

Answer 2

哈希表在键稀疏的情况下非常有用，但是当键密集时，没有必要进行哈希；可以使用键（字符串）本身作为索引。为了支持简单的成员查询，可以使用位向量。如果您的数据是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个整数的数组，其中一些插槽为空。尽管每个整数只有一个字节，但这不太可能适合内存，因为即使每个整数只有一个字节，它也会占用1TB。在这种情况下，可以将它们按顺序存储在磁盘文件中。

您可能会发现查找关于位向量/位数组的信息很有帮助：http://en.wikipedia.org/wiki/Bit_array 维基百科链接讨论了压缩，这可能是适用的。

- user1951747

Answer 3

...

你好，鲍勃：

长话短说：经典的HASH+BTREE方法强大而且超快。

无论是存储1000万个还是100亿个字符串在上述结构中，都没有关系——您始终具有非常低的最大查找阈值。

好吧，您需要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％，同时具有类似的碰撞。

- Georgi