C Library for compressing sequential positive integers

Question

Hi,

I have the very common problem of creating an index for an in-disk array of strings. In short, I need to store the position of each string in the in-disk representation. For example, a very naive solution would be an index array as follows:

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

Which says that the first string is at position 0, the second at position 20, the third at position 500 and the nth at position 103434.

The positions are always non-negative 64 bits integers in sequential order. Although the numbers could vary by any difference, in practice I expect the typical difference to be inside the range from 2^8 to 2^20. I expect this index to be mmap'ed in memory, and the positions will be accessed randomly (assume uniform distribution).

I was thinking about writing my own code for doing some sort of block delta encoding or other more sophisticated encoding, but there are so many different trade-offs between encoding/decoding speed and space that I would rather get a working library as a starting point and maybe even settle for something without any customizations.

Any hints? A c library would be ideal, but a c++ one would also allow me to run some initial benchmarks.

A few more details if you are still following. This will be used to build a library similar to cdb (http://cr.yp.to/cdb/cdbmake.html) on top the library cmph (http://cmph.sf.net). In short, it is for a large disk based read only associative map with a small index in memory.

Since it is a library, I don't have control over input, but the typical use case that I want to optimize have millions of hundreds of values, average value size in the few kilobytes ranges and maximum value at 2^31.

For the record, if I don't find a library ready to use I intend to implement delta encoding in blocks of 64 integers with the initial bytes specifying the block offset so far. The blocks themselves would be indexed with a tree, giving me O(log (n/64)) access time. There are way too many other options and I would prefer to not discuss them. I am really looking forward ready to use code rather than ideas on how to implement the encoding. I will be glad to share with everyone what I did once I have it working.

I appreciate your help and let me know if you have any doubts.

Answer 1

What exactly are you trying to compress? If you are thinking about the total space of index, is it really worth the effort to save the space?

If so one thing you could try is to chop the space into half and store it into two tables. First stores (upper uint, start index, length, pointer to second table) and the second would store (index, lower uint).

For fast searching, indices would be implemented using something like B+ Tree.

Answer 2

You have two conflicting requirements:

1. You want to compress very small items (8 bytes each).
2. You need efficient random access for each item.

The second requirement is very likely to impose a fixed length for each item.

Answer 3

I did something similar years ago for a full-text search engine. In my case, each indexed word generated a record which consisted of a record number (document id) and a word number (it could just as easily have stored word offsets) which needed to be compressed as much as possible. I used a delta-compression technique which took advantage of the fact that there would be a number of occurrences of the same word within a document, so the record number often did not need to be repeated at all. And the word offset delta would often fit within one or two bytes. Here is the code I used.

Since it's in C++, the code may is not going to be useful to you as is, but can be a good starting point for writing compressions routines.

Please excuse the hungarian notation and the magic numbers strewn within the code. Like I said, I wrote this many years ago :-)

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));
}

Answer 4

I use fastbit (Kesheng Wu LBL.GOV), it seems you need something good, fast and NOW, so fastbit is a highly competient improvement on Oracle's BBC (byte aligned bitmap code, berkeleydb). It's easy to setup and very good gernally.

However, given more time, you may want to look at a gray code solution, it seems optimal for your purposes.

Daniel Lemire has a number of libraries for C/++/Java released on code.google, I've read over some of his papers and they are quite nice, several advancements on fastbit and alternative approaches for column re-ordering with permutated grey codes's.

Almost forgot, I also came across Tokyo Cabinet, though I do not think it will be well suited for my current project, I may of considered it more if I had known about it before ;), it has a large degree of interoperability,

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.

As you referred to CDB, the TC benchmark has a TC mode (TC support's several operational constraint's for varying perf) where it surpassed CDB by 10 times for read performance and 2 times for write.

With respect to your delta encoding requirement, I am quite confident in bsdiff and it's ability to out-perform any file.exe content patching system, it may also have some fundimental interfaces for your general needs.

Google's new binary compression application, courgette may be worth checking out, in case you missed the press release, 10x smaller diff's than bsdiff in the one test case I have seen published.

Answer 5

Are you running on Windows? If so, I recommend creating the mmap file using naive solution your originally proposed, and then compressing the file using NTLM compression. Your application code never knows the file is compressed, and the OS does the file compression for you. You might not think this would be very performant or get good compression, but I think you'll be surprised if you try it.