Вопрос по data-structures, c, database, encoding, compression – C Библиотека для сжатия последовательных натуральных чисел

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)). Есть слишком много других вариантов, и я бы предпочел не обсуждать их. Я действительно с нетерпением жду готового использования кода, а не идей о том, как реализовать кодировку. Я буду рад поделиться со всеми, что я сделал, как только у меня это работает.

Я ценю вашу помощь и дайте мне знать, если у вас есть какие-либо сомнения.

Вы бы использовали ту же структуру данных на диске, что и в памяти? Thorbjørn Ravn Andersen
Предполагается, что индекс находится в памяти (mmap & ed), в то время как данные (строки) будут жить на диске. Считайте, что все в порядке байтов, если это вызывает озабоченность. Davi
Что такое требование доступа? Случайный? Последовательный? Только первый и последний? Каков размер значения индекса (32, 48, 64 бита)? Ожидается ли, что значения индекса будут абсолютно случайными (плоское распределение) или могут быть какие-то внутренние отношения, которые мы могли бы использовать? chmike
Другой вопрос ... Глядя на пример, кажется, что значения индекса расположены в порядке возрастания. Какое это значение дельты? chmike
Доступ должен быть случайным. Предположим, равномерное распределение. Записи индекса представляют собой 64-битные целые числа. Их дельта соответствует тому же распределению размера значений, на которые они указывают: несколько килобайт. Davi

Ваш Ответ

6   ответов
0

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

Поскольку он написан на 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));
}
6

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

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

У Даниэля Лемира есть несколько библиотек для C / ++ / Java, выпущенных наcode.googleЯ перечитал некоторые из его работ, и они довольно хороши, несколько улучшений в фастбите и альтернативных подходах к переупорядочению столбцов с переставленными серыми кодами.

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

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.

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

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

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

codeforge.lbl.gov/projects/fastbit это сайт разработчика для fastbit, LGPL, я думаю, что не BSD или MS-PL могут быть некоторые проблемы, но L в LGPL является некоторой проблемой. ;)
Привет RandomNickName42, спасибо за редактирование. Я в точности разрабатываю только для конкурентов TokyoCabinet. Davi
Похоже, это запатентовано.freepatentsonline.com/6831575.html, Может иметь значение
Привет RandomNickName42, спасибо за указатель. Похоже, очень перспективный кандидат. Для записи я также нашел подобную библиотеку здесь:code.google.com/p/lemurbitmapindex  Я дам обеим попыткам. Davi
0

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

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

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

0

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

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

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

Я понимаю. Этоis возможно, но поддержание дерева в самой памяти относительно дорого, учитываяsmall size предметов.
Хотя я буду осуществлять произвольный доступ к этим данным, он не обязательно должен быть O (1). Например, сжатие чисел в блоках, содержащих по 64 значения каждый, и сохранение дерева, чтобы найти, какой блок распаковывать, может дать мне значительное сжатие и достаточно быстрый доступ. Как я уже сказал, вопрос скорее в том, чтобы найти библиотеку с легкодоступными алгоритмами кодирования, такими как дельта-кодирование, elias-gamma и, вероятно, блок-блок для игры. Смотри вопросstackoverflow.com/questions/523733/compress-sorted-integers и, в частности, комментарий Симмона для другого объяснения. Davi
0

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

Но, учитывая, что вы говорите, что ожидаетеminimum длина индексированной строки должна быть 256, при этом индексы сохраняются как 64%at most 3% накладных расходов. Если общая длина строкового файла меньше 4 ГБ, вы можете использовать 32-битные индексы и получить 1,5% накладных расходов. Эти цифры говорят мне, что если сжатие имеет значение,you're better off compressing the strings, not the indices, Для этой проблемы вариация на LZ77 кажется в порядке.

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

Хотелось бы получить больше информации о проблеме:

  • Number of strings
  • Average length of a string
  • Maximum length of a string
  • Median length of strings
  • Degree to which the strings file compresses with gzip
  • Whether you are allowed to change the order of strings to improve compression

EDIT

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

Вы просили существующие библиотеки. Для группирования и дельта-кодирования я сомневаюсь, что вы найдете много. Что касается целочисленных кодов переменной длины, я не вижу особого смысла в библиотеках C, но вы можете найти кодировки переменной длины вPerl а такжепитон, Существует множество статей и несколько патентов на эту тему, и я подозреваю, что вам придется свернуть свою собственную. Но есть несколько простых кодов, и вы можете попробовать UTF-8 - он может кодировать целые числа без знака длиной до 32 бит, и вы можете получить код C изПлан & # xA0; 9 и я уверен во многих других источниках.

Йоу! Хорошо, ваше редактирование делает проблему намного яснее. Если вы найдете решение с полки, я буду очень впечатлен. Я добавил пару ссылок к своему ответу.
Привет Норман, Количество строк порядка сотен миллионов, а средняя длина будет 10k. Максимальная длина 2 ^ 31. Полный набор строк (значений) не помещается в памяти и не может быть переупорядочен. Что касается практики, я использую это для создания библиотеки, поэтому я не могу контролировать ввод. Эти цифры представляют варианты использования, которые я видел в прошлом (веб-страницы). Davi
0

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

Похожие вопросы