我有一大组字符串,顺序约为 10^12 左右,我需要选择一个合适的数据结构,以便提供一个字符串,我可以检索和关联整数值,例如 O(log(n))或 O(m) 时间,其中 'n' 是字符串列表的长度,'m' 是每个字符串的长度。
我们可以期望我们的字符串集,每个长度为 'm' 并在大小为 'q' 的某个字母表上编码,几乎涵盖了这个长度的所有可能的字符串。例如,假设我们有 10^12 个长度为 m = 39 的完全唯一的二进制字符串。这意味着我们已经覆盖了这个长度的所有可能的二进制字符串集合的约 54%。
因此,我担心为避免冲突的字符串找到合适的散列函数。有什么好的我可以用吗?索引我的 n 个字符串集需要多长时间?
还是我应该使用后缀树?我们知道 Ukkonen 的算法允许线性时间构造,我的猜测是,鉴于大量相似的字符串,这将节省空间?
最佳答案
鉴于您的字符串数量非常多,您的选择必须集中在以下几点:
1. Are your indexing structures going to fit in memory?
对于 哈希表 答案显然不是。因此访问时间将比 O(1) 慢得多。您仍然只需要一个磁盘访问(整个插入过程将是 O(N))。
对于 b-tree 我做了一些理论计算,假设 b+tree (为了在内部节点中节省更多空间)并且内部节点也被完全占用。通过这种分析,它不适合内存:
**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?
注:我发现了一些关于你的 ukkonens后缀树。插入是线性的,访问也是顺序的。但是我只发现它与一些 GB 一起使用。以下是一些关于后缀树算法的引用:[ref1] , [ref2]和 [ref3] .
希望这会有所帮助......
关于string - 选择合适的数据结构(哈希表与后缀树)来索引非常大的相似字符串集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13004248/