Dav*_*avi 12 c database compression encoding data-structures
我有一个非常普遍的问题,就是为磁盘内的字符串数组创建一个索引.简而言之,我需要将每个字符串的位置存储在磁盘表示中.例如,一个非常天真的解决方案是索引数组,如下所示:
uint64 idx [] = {0,20,500,1024,...,103434};
其中第一个字符串位于第0位,第二个字符串位于第20位,第三个位于第500位,第n个位于第103434位.
这些位置总是按顺序排列为非负64位整数.虽然数字可能会有所不同,但实际上我认为典型的差异在2 ^ 8到2 ^ 20的范围内.我希望这个索引在内存中是mmap的,并且将随机访问这些位置(假设均匀分布).
我正在考虑编写自己的代码来进行某种块增量编码或其他更复杂的编码,但在编码/解码速度和空间之间有很多不同的权衡,我宁愿把工作库作为一个起点甚至可能在没有任何自定义的情况下解决问题.
任何提示？一个c库是理想的,但是c ++也可以让我运行一些初步的基准测试.
如果您还在关注,还有一些细节.这将被用来建立类似于CDB库(http://cr.yp.to/cdb/cdbmake.html顶部的库CMPH()http://cmph.sf.net).简而言之,它适用于基于磁盘的大型只读关联映射,内存中的索引很小.
既然是一个图书馆,我没有在输入控件,但我要优化典型的用例有数亿值的,在几KB平均值尺寸范围在2 ^ 31最大值.
为了记录,如果我没有找到准备使用的库,我打算在64个整数的块中实现delta编码,其中初始字节指定到目前为止的块偏移量.块本身将用树索引,给我O(log(n/64))访问时间.有太多其他选择,我宁愿不讨论它们.我真的很期待使用代码而不是如何实现编码的想法.我很乐意与大家分享我工作后的所作所为.
感谢您的帮助,如果您有任何疑问,请告诉我.
我使用fastbit(Kesheng Wu LBL.GOV),看起来你需要一些好的,快速的和现在的,所以fastbit是Oracle BBC(字节对齐的位图代码,berkeleydb)的一个非常有竞争力的改进.这很容易设置,非常好.
但是,如果有更多时间,您可能需要查看格雷码解决方案,它似乎是最适合您的目的.
Daniel Lemire在code.google上发布了许多用于C/++/Java的库,我已经阅读了他的一些论文,他们非常好,有关fastbit的几项改进以及使用置换灰色进行列重新排序的替代方法代码的.
几乎忘了,我也遇到了东京内阁,虽然我觉得它不适合我现在的项目,如果我以前知道它,我可能会考虑更多;),它有很大程度的互操作性,
Tokyo Cabinet是用C语言编写的,并提供为C,Perl,Ruby,Java和Lua的API.Tokyo Cabinet适用于符合C99和POSIX标准的API平台.
正如您所提到的CDB,TC基准测试具有TC模式(TC支持针对变化性能的几个操作约束),其中读取性能超过CDB 10倍,写入超过2倍.
关于delta编码要求,我对bsdiff非常有信心,并且能够超出任何file.exe内容修补系统,它可能还有一些基本接口可满足您的一般需求.
谷歌的新二进制压缩应用程序,西葫芦可能值得一试,如果你错过了新闻稿,在我看过的一个测试用例中,差异比bsdiff小10倍.