我有一个非常常见的问题,即为磁盘中的字符串数组创建索引。简而言之,我需要将每个字符串的位置存储在磁盘内表示中。例如,一个非常简单的解决方案是索引数组,如下所示:
uint64 idx[] = { 0, 20, 500, 1024, ..., 103434 };
这表示第一个字符串位于位置 0,第二个字符串位于位置 20,第三个字符串位于位置 500,第 n 个字符串位于位置 103434。
这些位置始终是按顺序排列的非负 64 位整数。尽管数字可能因差异而有所不同,但实际上我预计典型差异在 2^8 到 2^20 的范围内。我希望这个索引在内存中进行映射,并且位置将被随机访问(假设均匀分布)。
我正在考虑编写自己的代码来进行某种块增量编码或其他更复杂的编码,但是编码/解码速度和空间之间有很多不同的权衡,我宁愿得到一个工作库作为起点甚至可能满足于没有任何定制的东西。
有什么提示吗? C 库是理想的选择,但 C++ 库也可以让我运行一些初始基准测试。
如果您仍在关注,请提供更多详细信息。这将用于构建类似于 cdb 的库(http://cr.yp.to/cdb/cdbmake.html http://cr.yp.to/cdb/cdbmake.html)在图书馆 cmmph 顶部(http://cmph.sf.net http://cmph.sf.net)。简而言之,它适用于基于大型磁盘的只读关联映射,在内存中具有较小的索引。
由于它是一个库,所以我无法控制输入,但我想要优化的典型用例有数百万个值,平均值大小在几千字节范围内,最大值为 2^31。
作为记录,如果我没有找到可供使用的库,我打算在 64 个整数块中实现增量编码,初始字节指定到目前为止的块偏移量。这些块本身将使用树进行索引,从而为我提供 O(log (n/64)) 访问时间。还有太多其他选择,我不想讨论它们。我真的很期待准备好使用代码,而不是如何实现编码的想法。一旦我开始工作,我将很高兴与大家分享我所做的事情。
感谢您的帮助,如果您有任何疑问,请告诉我。