用于压缩连续正整数的 C 库

Question

我有一个非常常见的问题，即为磁盘中的字符串数组创建索引。简而言之，我需要将每个字符串的位置存储在磁盘表示中。例如，一个非常天真的解决方案是索引数组，如下所示:

uint64 idx[] = { 0, 20, 500, 1024, ..., 103434 };

表示第一个字符串在位置 0，第二个在位置 20，第三个在位置 500，第 n 个在位置 103434。

位置总是按顺序排列的非负 64 位整数。虽然数字可能会有所不同，但实际上我希望典型的差异在 2^8 到 2^20 的范围内。我希望这个索引在内存中映射，并且位置将被随机访问(假设均匀分布)。

我正在考虑编写自己的代码来执行某种 block 增量编码或其他更复杂的编码，但在编码/解码速度和空间之间存在许多不同的权衡，我宁愿获得一个工作库作为一个起点，甚至可以在没有任何定制的情况下满足于某些东西。

有什么提示吗？一个 c 库是理想的，但一个 c++ 库也可以让我运行一些初始基准测试。

如果您仍在关注，请提供更多详细信息。这将用于在库 cmph ( http://cr.yp.to/cdb/cdbmake.html ) 之上构建类似于 cdb ( http://cmph.sf.net ) 的库。简而言之，它适用于基于大磁盘的只读关联映射，在内存中有一个小索引。

由于它是一个库，我无法控制输入，但我要优化的典型用例有数百万个值，平均值大小在几千字节范围内，最大值在 2^31 .

作为记录，如果我没有找到可以使用的库，我打算在 64 个整数 block 中实现增量编码，其中初始字节指定到目前为止的 block 偏移量。 block 本身将用树索引，给我 O(log (n/64)) 访问时间。有太多其他选择，我不想讨论它们。我真的很期待准备好使用代码而不是关于如何实现编码的想法。一旦我开始工作，我将很高兴与大家分享我所做的事情。

非常感谢您的帮助，如果您有任何疑问，请告诉我。

Answer 1

我使用 fastbit (Kesheng Wu LBL.GOV)，看来你现在需要一些好的、快速的东西，所以 fastbit 是对 Oracle 的 BBC(字节对齐位图代码，berkeleydb)的高度竞争力的改进。它很容易设置并且非常好。

但是，如果有更多时间，您可能需要查看 gray code解决方案，它似乎最适合您的目的。

Daniel Lemire 在 code.google 上发布了许多用于 C/++/Java 的库，我已经阅读了他的一些论文，它们非常好，在 fastbit 和使用置换格雷码的列重新排序的替代方法方面取得了一些进展。

差点忘了，我也遇到了Tokyo Cabinet ，虽然我认为它不太适合我当前的项目，但如果我之前知道它，我可能会更多地考虑它；)，它具有很大程度的互操作性，

Tokyo Cabinet is written in the C language, and provided as API of C, Perl, Ruby, Java, and Lua. Tokyo Cabinet is available on platforms which have API conforming to C99 and POSIX.

正如您提到的 CDB，TC 基准​​测试有一个 TC 模式(TC 支持针对不同性能的多个操作约束)，它在读取性能上超过 CDB 10 倍，在写入性能上超过 CDB 2 倍。

关于您的增量编码要求，我对 bsdiff 很有信心并且它的性能优于任何 file.exe 内容修补系统，它可能还具有一些基本接口(interface)以满足您的一般需求。

Google 的新二进制压缩应用程序，courgette可能值得一试，以防你错过了新闻稿，在我看到的一个测试用例中，diff 比 bsdiff 小 10 倍。