C库用于压缩顺序正整数

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

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

其中第一个字符串位于第0位,第二个字符串位于第20位,第三个位于第500位,第n个位于第103434位。

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

我正在考虑编写自己的代码来进行某种块增量编码或其他更复杂的编码,但是在编码/解码速度和空间之间有很多不同的权衡,我宁愿把工作库作为一个起点。甚至可能在没有任何自定义的情况下解决问题。

任何提示? 一个c库是理想的,但是c ++也可以让我运行一些初步的基准测试。

如果您还在关注,还有一些细节。 这将用于在库cmph( http://cmph.sf.net )上构建类似于cdb( http://cr.yp.to/cdb/cdbmake.html )的库。 简而言之,它适用于基于大型磁盘的只读关联映射,内存中的索引很小。

由于它是一个库,我无法控制输入,但我想要优化的典型用例有数百万个值,平均值大小在几千字节范围内,最大值在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标准的A​​PI平台。

正如您所提到的CDB,TC基准测试具有TC模式(TC支持对变化性能的几个操作约束),其中读取性能超过CDB 10倍,写入超过2倍。

关于你的delta编码要求,我对bsdiff非常有信心,并且它能够超越任何file.exe内容修补系统,它也可能有一些基本接口满足你的一般需求。

谷歌的新二进制压缩应用程序, 西葫芦可能值得一试,如果你错过了新闻稿,在我看过的一个测试用例中,差异比bsdiff小10倍。

您有两个相互矛盾的要求:

  1. 您想要压缩非常小的项目(每个8个字节)。
  2. 您需要为每个项目提供高效的随机访问。

第二个要求很可能对每个项目施加固定长度。

你究竟要压缩什么? 如果您正在考虑索引的总空间,那么节省空间真的值得吗?

如果是这样,你可以尝试的是将空间切成两半并将其存储在两个表中。 第一个存储(上部uint,起始索引,长度,指向第二个表的指针),第二个存储(索引,下部uint)。

对于快速搜索,索引将使用诸如B + Tree之类的东西来实现。

几年前我做了类似的全文搜索引擎。 在我的例子中,每个索引单词生成一个记录,该记录由记录号(文档ID)和字号(它可以很容易地存储字偏移)组成,需要尽可能地进行压缩。 我使用了一种增量压缩技术,它利用了文档中会出现多个相同单词的事实,因此记录号通常根本不需要重复。 而偏移增量字通常适合一个或两个字节。 这是我使用的代码。

因为它是用C ++编写的,所以代码可能不会对你有用,但它可以成为编写压缩例程的一个很好的起点。

请原谅匈牙利符号和代码中散布的神奇数字。 就像我说的,我多年前写过这篇文章:-)

IndexCompressor.h

// // index compressor class // #pragma once #include "File.h" const int IC_BUFFER_SIZE = 8192; // // index compressor // class IndexCompressor { private : File *m_pFile; WA_DWORD m_dwRecNo; WA_DWORD m_dwWordNo; WA_DWORD m_dwRecordCount; WA_DWORD m_dwHitCount; WA_BYTE m_byBuffer[IC_BUFFER_SIZE]; WA_DWORD m_dwBytes; bool m_bDebugDump; void FlushBuffer(void); public : IndexCompressor(void) { m_pFile = 0; m_bDebugDump = false; } ~IndexCompressor(void) {} void Attach(File& File) { m_pFile = &File; } void Begin(void); void Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo); void End(void); WA_DWORD GetRecordCount(void) { return m_dwRecordCount; } WA_DWORD GetHitCount(void) { return m_dwHitCount; } void DebugDump(void) { m_bDebugDump = true; } }; 

IndexCompressor.cpp

 // // index compressor class // #include "stdafx.h" #include "IndexCompressor.h" void IndexCompressor::FlushBuffer(void) { ASSERT(m_pFile != 0); if (m_dwBytes > 0) { m_pFile->Write(m_byBuffer, m_dwBytes); m_dwBytes = 0; } } void IndexCompressor::Begin(void) { ASSERT(m_pFile != 0); m_dwRecNo = m_dwWordNo = m_dwRecordCount = m_dwHitCount = 0; m_dwBytes = 0; } void IndexCompressor::Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo) { ASSERT(m_pFile != 0); WA_BYTE buffer[16]; int nbytes = 1; ASSERT(dwRecNo >= m_dwRecNo); if (dwRecNo != m_dwRecNo) m_dwWordNo = 0; if (m_dwRecordCount == 0 || dwRecNo != m_dwRecNo) ++m_dwRecordCount; ++m_dwHitCount; WA_DWORD dwRecNoDelta = dwRecNo - m_dwRecNo; WA_DWORD dwWordNoDelta = dwWordNo - m_dwWordNo; if (m_bDebugDump) { TRACE("%8X[%8X] %8X[%8X] : ", dwRecNo, dwRecNoDelta, dwWordNo, dwWordNoDelta); } // 1WWWWWWW if (dwRecNoDelta == 0 && dwWordNoDelta < 128) { buffer[0] = 0x80 | WA_BYTE(dwWordNoDelta); } // 01WWWWWW WWWWWWWW else if (dwRecNoDelta == 0 && dwWordNoDelta < 16384) { buffer[0] = 0x40 | WA_BYTE(dwWordNoDelta >> 8); buffer[1] = WA_BYTE(dwWordNoDelta & 0x00ff); nbytes += sizeof(WA_BYTE); } // 001RRRRR WWWWWWWW WWWWWWWW else if (dwRecNoDelta < 32 && dwWordNoDelta < 65536) { buffer[0] = 0x20 | WA_BYTE(dwRecNoDelta); WA_WORD *p = (WA_WORD *) (buffer+1); *p = WA_WORD(dwWordNoDelta); nbytes += sizeof(WA_WORD); } else { // 0001rrww buffer[0] = 0x10; // encode recno if (dwRecNoDelta < 256) { buffer[nbytes] = WA_BYTE(dwRecNoDelta); nbytes += sizeof(WA_BYTE); } else if (dwRecNoDelta < 65536) { buffer[0] |= 0x04; WA_WORD *p = (WA_WORD *) (buffer+nbytes); *p = WA_WORD(dwRecNoDelta); nbytes += sizeof(WA_WORD); } else { buffer[0] |= 0x08; WA_DWORD *p = (WA_DWORD *) (buffer+nbytes); *p = dwRecNoDelta; nbytes += sizeof(WA_DWORD); } // encode wordno if (dwWordNoDelta < 256) { buffer[nbytes] = WA_BYTE(dwWordNoDelta); nbytes += sizeof(WA_BYTE); } else if (dwWordNoDelta < 65536) { buffer[0] |= 0x01; WA_WORD *p = (WA_WORD *) (buffer+nbytes); *p = WA_WORD(dwWordNoDelta); nbytes += sizeof(WA_WORD); } else { buffer[0] |= 0x02; WA_DWORD *p = (WA_DWORD *) (buffer+nbytes); *p = dwWordNoDelta; nbytes += sizeof(WA_DWORD); } } // update current setting m_dwRecNo = dwRecNo; m_dwWordNo = dwWordNo; // add compressed data to buffer ASSERT(buffer[0] != 0); ASSERT(nbytes > 0 && nbytes < 10); if (m_dwBytes + nbytes > IC_BUFFER_SIZE) FlushBuffer(); CopyMemory(m_byBuffer + m_dwBytes, buffer, nbytes); m_dwBytes += nbytes; if (m_bDebugDump) { for (int i = 0; i < nbytes; ++i) TRACE("%02X ", buffer[i]); TRACE("\n"); } } void IndexCompressor::End(void) { FlushBuffer(); m_pFile->Write(WA_BYTE(0)); } 

您已经省略了有关要编制索引的字符串数的关键信息。

但鉴于您说您希望索引字符串的最小长度为256,将索引存储为64%会产生最多 3%的开销。 如果字符串文件的总长度小于4GB,则可以使用32位索引并产生1.5%的开销。 这些数字告诉我,如果压缩很重要, 你最好压缩字符串,而不是压缩 。 对于那个问题,LZ77的变化似乎是有序的。

如果你想尝试一个疯狂的想法,把每个字符串放在一个单独的文件中,将它们全部拉进一个zip文件,看看如何使用zziplib 。 这可能不会很好,但你的工作几乎为零。

有关该问题的更多数据将受到欢迎:

  • 字符串数量
  • 字符串的平均长度
  • 字符串的最大长度
  • 字符串的中间长度
  • 字符串文件使用gzip压缩的程度
  • 是否允许您更改字符串的顺序以改进压缩

编辑

评论和修订问题使问题更加清晰。 我喜欢你的分组想法,我会尝试一个简单的delta编码,对增量进行分组,并在每个组中使用可变长度的代码。 我不会在64组作为组大小 – 我想你可能想要根据经验确定。

您要求使用现有库。 对于分组和delta编码,我怀疑你会发现很多。 对于可变长度的整数代码,我没有看到C库的方式,但你可以在Perl和Python中找到可变长度的编码。 关于这个主题有大量的论文和一些专利,我怀疑你最终不得不自己动手。 但是有一些简单的代码,你可以尝试UTF-8 – 它可以编码最多32位的无符号整数,你可以从Plan 9中获取C代码,我相信很多其他来源。

你在Windows上运行吗? 如果是这样,我建议使用您最初提出的天真解决方案创建mmap文件,然后使用NTLM压缩压缩文件。 您的应用程序代码永远不会知道文件是否已压缩,并且操作系统会为您执行文件压缩。 你可能不认为这会非常高效或获得良好的压缩效果,但我认为如果你尝试它会让你感到惊讶。