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

У меня очень распространенная проблема создания индекса для массива строк в диске. Короче говоря, мне нужно сохранить позицию каждой строки в представлении на диске. Например, очень наивным решением будет массив индексов следующим образом:

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

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

Я использую fastbit ( Kesheng Wu LBL.GOV), вам кажется, что вам нужно что-то хорошее, быстрое и СЕЙЧАС, поэтому fastbit – это высококонкурентное усовершенствование на BBC 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, кабриолет, возможно, стоит проверить, если вы пропустили пресс-релиз, 10x меньше diff, чем bsdiff в одном тестовом случае, который я видел опубликованным.

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

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

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

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

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

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

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

Так как он находится на 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% накладные расходы. Если общая длина строкового файла меньше 4 ГБ, вы можете использовать 32-разрядные индексы и нести накладные расходы на 1,5%. Эти цифры подсказывают мне, что если сжатие имеет значение, вам лучше сжимать строки, а не индексы . Для этой проблемы вариация на LZ77 выглядит по порядку.

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

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

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

РЕДАКТИРОВАТЬ

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

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

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