Tengo el problema muy común de crear un índice para una matriz de cadenas en el disco. En resumen, necesito almacenar la posición de cada cadena en la representación en el disco. Por ejemplo, una solución muy ingenua sería una matriz de índice de la siguiente manera:

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

Lo que dice que la primera cadena está en la posición 0, la segunda en la posición 20, la tercera en la posición 500 y la enésima posición 103434.

Las posiciones son siempre enteros no negativos de 64 bits en orden secuencial. Aunque los números pueden variar por cualquier diferencia, en la práctica espero que la diferencia típica esté dentro del rango de 2 ^ 8 a 2 ^ 20. Espero que este índice se sitúe en la memoria y se acceda al azar a las posiciones (suponiendo una distribución uniforme).

Estaba pensando en escribir mi propio código para realizar algún tipo de codificación de bloque delta u otra codificación más sofisticada, pero hay tantas concesiones diferentes entre la velocidad de codificación / decodificación y el espacio que preferiría tener una biblioteca de trabajo como punto de partida. y tal vez incluso conformarse con algo sin ninguna personalización.

¿Alguna pista? Una biblioteca en C sería ideal, pero una en C ++ también me permitiría ejecutar algunos puntos de referencia iniciales.

Unos cuantos detalles más si todavía estás siguiendo. Esto se usará para construir una biblioteca similar a cdb (http://cr.yp.to/cdb/cdbmake.html) en la parte superior de la biblioteca cmph (http://cmph.sf.net). En resumen, es para un gran mapa asociativo de solo lectura basado en un pequeño índice en la memoria.

Dado que es una biblioteca, no tengo control sobre la entrada, pero el caso de uso típico que quiero optimizar tiene millones de cientos de valores, tamaño de valor promedio en los rangos de pocos kilobytes y valor máximo en 2 ^ 31.

Para el registro, si no encuentro una biblioteca lista para usar, pretendo implementar la codificación delta en bloques de 64 enteros con los bytes iniciales que especifican el desplazamiento del bloque hasta el momento. Los bloques en sí se indexarían con un árbol, lo que me da tiempo de acceso O (log (n / 64)). Hay demasiadas otras opciones y preferiría no discutirlas. Realmente estoy deseando que esté listo para usar código en lugar de ideas sobre cómo implementar la codificación. Estaré encantado de compartir con todos lo que hice una vez que esté funcionando.

Aprecio tu ayuda y hazme saber si tienes alguna duda.