logo标签列表

顺序正整数压缩的C语言库

cdatabasedata-structuresencodingcompression
12
我有一个常见的问题，需要为字符串数组创建索引。简单来说，我需要存储每个字符串在磁盘上的位置。例如，一个非常简单的解决方案是使用以下索引数组：

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）的库，基于cmph（http://cmph.sf.net）库。简而言之，它是用于具有小内存索引的大型磁盘基础只读关联映射。
由于它是一个库，我无法控制输入，但我想要优化的典型用例有数百万个值，平均值大小在几千字节范围内，最大值为2^31。
记录一下，如果我找不到可用的库，我打算实现64个整数块的增量编码，其中初始字节指定到目前为止的块偏移量。块本身将使用树进行索引，给我O(log(n/64))的访问时间。有太多其他选项，我宁愿不讨论它们。我真的很期待能够使用现成的代码，而不是关于如何实现编码的想法。一旦我使其工作，我会很乐意与每个人分享我的经验。
感谢您的帮助，请让我知道是否有任何疑问。
访问要求是什么？随机的？顺序的？仅从头到尾？索引值大小是多少（32、48、64位）？ 索引值是否预计完全随机（平坦分布），或者可能存在一些内部关系可以使用？ - chmike
另一个问题...看这个例子似乎索引值是按递增顺序排列的。那么delta值是多少？ - chmike
访问应该是随机的。假设均匀分布。索引条目是64位整数。它们的增量遵循它们所指向的值的大小相同的分布：几千字节。 - Davi
你会在磁盘上使用与内存中相同的数据结构吗？ - Thorbjørn Ravn Andersen
索引应该在内存中（mmap'ed），而数据（字符串）将存储在磁盘中。如果有关注点，请考虑一切都是小端。 - Davi
6个回答
6
我使用fastbit（Kesheng Wu LBL.GOV），它似乎是您需要的快速且高效的改进版本，比Oracle的BBC（字节对齐位图编码，BerkeleyDB）更好。它易于设置且通常非常出色。
然而，如果有更多时间，您可能会考虑格雷码解决方案，它似乎是您的最佳选择。
Daniel Lemire发布了许多C / C ++ / Java库，可以在code.google上找到，我已经阅读了他的一些论文，它们非常好，具有比fastbit更先进的技术和使用灰色编码进行列重新排序的替代方法。
几乎忘记了，我还发现了东京柜子，虽然我认为它不适合我的当前项目，但如果我之前知道它，我可能会更加考虑它。它具有很大的互操作性。

Tokyo Cabinet是用C语言编写的，提供C、Perl、Ruby、Java和Lua的API。Tokyo Cabinet可在符合C99和POSIX的API的平台上使用。

关于你提到的CDB，TC基准测试有一个TC模式（TC支持多种操作约束以获得不同的性能），其中读取性能超过CDB 10倍，写入性能超过CDB 2倍。

关于您的增量编码要求，我非常有信心bsdiff，它的能力可以胜任任何文件.exe内容打补丁系统，它还可能具有一些基本接口，适用于您的一般需求。

谷歌的新二进制压缩应用程序courgette也值得一试，如果您错过了新闻发布会，那么比我看到的任何一种测试情况下的bsdiff小10倍的差异。

1
嗨，RandomNickName42，感谢你的指引。看起来这是一个非常有前途的候选者。为了记录，我也在这里找到了一个类似的库：http://code.google.com/p/lemurbitmapindex/我会尝试使用两个库。 - Davi
1
看起来这个东西是受专利保护的。http://www.freepatentsonline.com/6831575.html。可能是个问题。 - chmike
https://codeforge.lbl.gov/projects/fastbit/ 是 fastbit 的开发站点，采用 LGPL 许可证。我猜不是采用 BSD 或 MS-PL 许可证可能会有一些问题，但是 LGPL 中的 L 有一定的安慰作用。 ;) - RandomNickName42
1
嗨，RandomNickName42，感谢您的编辑。我正在开发一个只读竞争者来竞争TokyoCabinet。 - Davi
0

多年前，我为一个全文搜索引擎做过类似的事情。在我的情况下，每个索引词都生成了一条记录，其中包括记录号（文档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));
}
0

你到底想要压缩什么？如果你考虑的是索引的总空间，那么节省这些空间真的值得吗？

如果是的话，你可以尝试将空间分成两半，并将其存储在两个表中。第一个表存储（上 uint、起始索引、长度、指向第二个表的指针），第二个表存储（索引、下 uint）。

为了快速搜索，索引将使用类似于 B+ 树 的东西来实现。

0

你有两个相互冲突的需求：

  1. 你想要压缩非常小的项目（每个项目8字节）。
  2. 你需要对每个项目进行高效的随机访问。

第二个需求很可能会对每个项目强制规定一个固定长度。

虽然我将在这个数据中进行随机访问，但它不一定需要是O(1)。例如，将数字压缩到每个包含64个值的块中，并保留一个树来查找要解压缩的块，可能会给我带来显着的压缩和足够快的访问速度。正如我所说，问题更多地是要找到一个具有现成编码算法（如delta-encoding、elias-gamma和可能的块片段）的库来使用。请参见问题https://dev59.com/BnRB5IYBdhLWcg3wv5xA，特别是simmon的评论以获得另一个解释。 - Davi
我明白。虽然这是可能的，但考虑到项目的小规模，在内存中维护树本身相对昂贵。 - Mehrdad Afshari
0

您遗漏了关于您打算索引的字符串数量的重要信息。

但是，考虑到您说您期望索引的最小长度为256，将索引存储为64％会产生最多3％的开销。 如果字符串文件的总长度小于4GB，则可以使用32位索引并产生1.5％的开销。 这些数字让我认为，如果压缩很重要，您最好压缩字符串而不是索引。 对于这个问题，LZ77的变体似乎是合适的。

如果您想尝试一个疯狂的想法，请将每个字符串放在单独的文件中，将它们全部放入zip文件中，并查看您可以使用zziplib做些什么。 这可能不是很理想，但您几乎不需要付出任何努力。

欢迎提供更多关于该问题的数据:

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

编辑

评论和修改后的问题使问题更加清晰。我喜欢您分组的想法，并尝试简单的增量编码，对增量进行分组，并在每个组内使用可变长度编码。我不会将64作为组大小固定下来 - 我认为您可能需要根据经验确定。

您询问现有的库。 对于分组和增量编码，我怀疑您会找到很多。 对于可变长度整数编码，我没有看到太多C库，但是您可以在Perl和Python中找到可变长度编码。 关于这个主题有大量论文和一些专利，我怀疑您最终将不得不自己开发。 但是有一些简单的代码可用，并且您可以尝试使用UTF-8 - 它可以对32位无符号整数进行编码，并且您可以从Plan 9和许多其他来源获取C代码。

你好Norman，字符串的数量大约在数亿级别，平均长度为10k。最大长度为2^31。完整的字符串集（值）无法放入内存，也无法重新排序。更实际的是，我正在使用它来构建一个库，所以我对输入没有真正的控制。这些数字代表我过去看到的用例（网页）。 - Davi
哟！好的，你的编辑让问题更加清晰了。如果你找到一个现成的解决方案，我会非常印象深刻的。我已经在我的答案中添加了一些链接。 - Norman Ramsey
0

你是在Windows上运行吗？如果是的话，我建议使用最初提出的naive解决方案创建mmap文件，然后使用NTLM压缩压缩该文件。你的应用程序代码不会知道文件被压缩了，操作系统会为你完成文件压缩。你可能认为这不会有很好的性能表现或获得良好的压缩效果，但如果你尝试一下，你会感到惊讶。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接