C Library для сжатия последовательных положительных целых чисел

Ответ 1

Я использую fastbit (Kesheng Wu LBL.GOV), кажется, вам нужно что-то хорошее, быстрое и СЕЙЧАС, так что fastbit - это высококонкурентное совершенствование Oracle BBC (байт выровненный растровый код, berkeleydb). Он прост в настройке и очень хорош.

Однако, учитывая больше времени, вы можете взглянуть на серый код, это кажется оптимальным для ваших целей.

Daniel Lemire имеет ряд библиотек для C/++/Java, выпущенных на code.google, я прочитал некоторые из его и они довольно приятны, несколько улучшений на быстрых и альтернативных подходах для переупорядочения столбцов с перестановочными серыми кодами.

Почти забыл, я также наткнулся на Tokyo Cabinet, хотя я не думаю, что он будет хорошо подходить для моего текущего проекта, я могу считал это больше, если бы я знал об этом раньше;), он имеет большую степень совместимости,

Токийский кабинет написан на C язык и предоставляется как API C, Perl, Ruby, Java и Lua. Токио Кабинет доступен на платформах которые имеют API, соответствующий C99 и POSIX.

Как вы говорили о CDB, в тесте TC есть режим TC (TC поддерживает несколько операционных ограничений для разных перформансов), где он превзошел CDB в 10 раз для чтения и 2 раза для записи.

Что касается требования к дельта-кодированию, я уверен в bsdiff и имеет возможность выходить из любого файла file.exe система патчей, она также может иметь некоторые фундаментальные интерфейсы для ваших общих потребностей.

Новое приложение для двоичного сжатия Google, courgette может стоить проверить, если вы пропустили пресс-релиз, размер 10x меньше, чем bsdiff в одном тестовом примере, который я видел, опубликован.

Ответ 2

Что именно вы пытаетесь сжать? Если вы думаете об общей площади индекса, действительно ли стоит сохранить пространство?

Если бы вы могли попытаться сделать так, чтобы вырезать пространство пополам и сохранить его на две таблицы. Первые магазины (верхний uint, начальный индекс, длина, указатель на вторую таблицу), а второй будут хранить (индекс, нижний uint).

Для быстрого поиска индексы будут реализованы с помощью B + Tree.

Ответ 3

У вас есть два противоречивых требования:

• Вы хотите сжать очень маленькие предметы (по 8 байт).
• Вам нужен эффективный случайный доступ для каждого элемента.

Второе требование, скорее всего, наложит фиксированную длину для каждого элемента.

Ответ 4

Вы опустили критическую информацию о количестве строк, которые вы собираетесь индексировать.

Но, учитывая, что вы говорите, что минимальная длина индексированной строки равна 256, сохранение индексов, поскольку 64% приходится на 3% накладные расходы. Если общая длина строкового файла меньше 4 ГБ, вы можете использовать 32-разрядные индексы и нести накладные расходы на 1,5%. Эти цифры подсказывают мне, что если сжатие имеет значение, вам лучше сжать строки, а не индексы. Для этой проблемы вариант на LZ77 выглядит по порядку.

Если вы хотите попробовать дикую идею, поместите каждую строку в отдельный файл, потяните их все в zip файл и посмотрите, как вы можете сделать с zziplib. Это, вероятно, не будет большим, но с вашей стороны почти нулевая работа.

Дополнительные данные по этой проблеме будут приветствоваться:

• Число строк
• Средняя длина строки
• Максимальная длина строки
• Средняя длина строк
• Степень сжатия файла строк с помощью gzip
• Разрешено ли вам изменять порядок строк для улучшения сжатия.

ИЗМЕНИТЬ

Комментарий и пересмотренный вопрос делают проблему намного яснее. Мне нравится ваша идея группировки, и я бы попробовал простую дельта-кодировку, группировал дельта и использовал код переменной длины внутри каждой группы. Я бы не просил 64 в качестве размера группы. Я думаю, вы, вероятно, захотите определить это эмпирически.

Вы запросили существующие библиотеки. Для группировки и дельта-кодирования я сомневаюсь, что вы найдете много. Для целочисленных кодов переменной длины я не вижу много возможностей для библиотек C, но вы можете найти кодировки переменной длины в Perl и Python. Есть тонна бумаг и некоторые патенты на эту тему, и я подозреваю, что вы собираетесь завершить свой собственный. Но есть несколько простых кодов, и вы можете дать UTF-8 try — он может кодировать целые числа без знака до 32 бит, и вы можете захватить код C из Plan 9, и я уверен, что многие другие источники.

Ответ 5

Я сделал что-то подобное много лет назад для полнотекстовой поисковой системы. В моем случае каждое проиндексированное слово сгенерировало запись, состоящую из номера записи (идентификатора документа) и номера слова (он мог бы так же легко сохранить смещения слов), которые необходимо было максимально сжато. Я использовал метод дельта-сжатия, который воспользовался тем фактом, что в документе было бы количество вхождений одного и того же слова, поэтому номер записи часто не нужно было повторять вообще. Дельта треугольника слова часто вписывается в один или два байта. Вот код, который я использовал.

Так как это в С++, код может не оказаться полезным для вас как есть, но может быть хорошей отправной точкой для написания процедур сжатия.

Прошу извинить венгерскую нотацию и магические числа, разбросанные внутри кода. Как я уже сказал, я писал это много лет назад: -)

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

Ответ 6

Вы работаете в Windows? Если это так, я рекомендую создать файл mmap с использованием наивного решения, изначально предложенного вами, а затем сжимать файл с помощью сжатия NTLM. Ваш код приложения никогда не знает, что файл сжат, а ОС выполняет сжатие файлов для вас. Вы могли бы не подумать, что это будет очень результативно или получить хорошее сжатие, но я думаю, вы будете удивлены, если попробуете.