3

这是我的问题（我正在用 C 编程）：

我有一些包含 DNA 序列的巨大文本文件（每个文件大约有 6500 万行，大小约为 4~5 GB）。在这些文件中有很多重复项（还不知道有多少，但应该有数百万个），我想在输出中返回一个只有不同值的文件。每个字符串都有一个相关的质量值，所以如果我有 5 个具有不同质量值的相等字符串，我将保留最好的一个并丢弃其他 4 个。

尽可能减少内存需求并提高速度效率是至关重要的。我的想法是使用哈希函数创建一个 JudyHS 数组，以便将字符串 DNA 序列（长 76 个字母，有 7 个可能的字符）转换为整数，以减少内存使用量（4 或 8 个字节，而不是 76 个字节数以百万计的条目应该是一个相当大的成就）。这样我就可以使用整数作为索引并只存储该索引的最佳质量值。问题是我找不到一个 UNIVOCALLY 定义这么长的字符串并产生一个可以存储在整数甚至 long long 内的值的哈希函数！

我对哈希函数的第一个想法类似于 Java 中的默认字符串哈希函数：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[ n-1]，但我可以获得最大值 8,52*10^59.. 太大了。做同样的事情并将其存储在双重中怎么样？计算会变得慢很多吗？请注意，我想要一种统一定义字符串的方法，避免冲突（或者至少它们应该非常罕见，因为我必须在每次冲突时访问磁盘，这是一个相当昂贵的操作......）

4

2 回答 2

3

您有 7^76 个可能的 DNA 序列，并希望将它们映射到 2^32 个散列而不发生冲突？不可能。

您至少需要 log2(7^76) = 214 位才能做到这一点，大约 27 个字节。

我可以忍受一些碰撞，我建议坚持使用 CRC32 或 md5，而不是再次发明一个新轮子。

于 2011-05-03T14:35:33.150 回答
1

获得N个元素的无冲突散列函数的“简单”方法是使用良好的混合函数（例如加密散列函数）并截断大小，以便散列结果至少存在于大小为N 2。在这里，你有 6500 万行——这适合 26 位（2 26接近 6500 万），所以 52 位“应该足够了”。

您可以尝试使用快速加密散列函数，甚至是“损坏”的散列函数，因为这不是与安全相关的问题。MD4、MD5、SHA-1...然后将结果截断为第一个（或最后一个）64 位，并将其存储为 64 位整数类型。您的 6500 万行之间很有可能不会发生任何冲突；如果你得到一些，它们将非常罕见。

对于哈希函数的优化 C 实现，查找sphlib。使用提供的sph_dec64le()函数将 8 位序列“解码”为 64 位无符号整数值。

于 2011-05-03T15:10:09.447 回答