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

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

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