Almacenar / recuperar una estructura de datos

He implementado un árbol de sufijos en Python para realizar búsquedas de texto completo, y está funcionando muy bien. Pero hay un problema: el texto indexado puede ser muy grande, por lo que no podremos tener toda la estructura en la memoria RAM.

introduzca la descripción de la imagen aquí

IMAGEN: Sufijo árbol para la palabra BANANAS (en mi caso, imagine un árbol 100000 veces más grande).

Entonces, investigando un poco al respecto, encontré el módulo pickle , un excelente módulo de Python para “cargar” y “descargar” objetos de / en archivos, y ¿adivinen qué? Funciona maravillosamente con mi estructura de datos.

Entonces, acortando la larga historia: ¿Cuál sería la mejor estrategia para almacenar y recuperar esta estructura en / desde el disco? Quiero decir, una solución podría ser almacenar cada nodo en un archivo y cargarlo desde el disco cuando sea necesario, pero esta no es la mejor forma de pensar (demasiados accesos de disco).


    Nota: Aunque he etiquetado esta pregunta como python , el lenguaje de progtwigción no es la parte importante de la pregunta, la estrategia de almacenamiento / recuperación del disco es realmente el punto principal.

    Si pickle ya está funcionando para usted, es posible que desee echar un vistazo a ZODB, que agrega algunas funciones a la parte superior de pickle . Mirando la documentación, vi este párrafo que trata de abordar los problemas de tamaño que tiene:

    La base de datos mueve objetos libremente entre la memoria y el almacenamiento. Si un objeto no se ha utilizado por un tiempo, puede liberarse y cargarse su contenido desde el almacenamiento la próxima vez que se use.

    Una forma efectiva de administrar una estructura como esta es usar un archivo asignado en memoria . En el archivo, en lugar de almacenar referencias para los punteros de nodo, almacena las compensaciones en el archivo. Aún puede utilizar pickle para serializar los datos del nodo a una secuencia adecuada para almacenar en el disco, pero querrá evitar almacenar referencias ya que el módulo pickle querrá incrustar todo su árbol de una vez (como lo ha visto).

    Usando el módulo mmap , puede asignar el archivo al espacio de direcciones y leerlo como si fuera una gran secuencia de bytes. El sistema operativo se encarga de leer realmente desde el archivo y administrar los buffers de archivos y todos los detalles.

    Puede almacenar el primer nodo al inicio del archivo y tener compensaciones que apunten al siguiente nodo (s). Leer el siguiente nodo es solo una cuestión de leer el desplazamiento correcto en el archivo.

    La ventaja de los archivos asignados en memoria es que no se cargan en la memoria de una sola vez, sino que solo se leen desde el disco cuando es necesario. He hecho esto (en un sistema operativo de 64 bits) con un archivo de 30 GB en una máquina con solo 4 GB de RAM instalada, y funcionó bien.

    ¿Qué hay de almacenarlo en sqlite ?

    SQLite:

    • Tiene soporte para hasta 2 terabytes de datos,
    • soporta consultas SQL,
    • es un excelente reemplazo para almacenar datos en la aplicación,
    • puede soportar ~ 100k visitas por día (si se usa para aplicaciones web promedio),

    Por lo tanto, puede ser bueno echar un vistazo más de cerca a esta solución, ya que ha demostrado ser la manera eficiente de almacenar datos dentro de las aplicaciones.

    Tal vez podría combinar cPickle y una bsddb datos bsddb que le permita almacenar sus nodos encurtidos en un objeto similar a un bsddb que se almacenará en el sistema de archivos; por lo tanto, podría cargar la base de datos más tarde y obtener los nodos que necesita con un rendimiento realmente bueno.

    De una manera muy sencilla:

     import bsddb import cPickle db = bsddb.btopen('/tmp/nodes.db', 'c') def store_node(node, key, db): db[key] = cPickle.dumps(node) def get_node(key, db): return cPickle.loads(db[key]) 

    Intente un árbol de sufijo comprimido en su lugar.

    La idea principal es que, en lugar de tener muchos nodos de 1 carácter, puede compactarlos en 1 nodo de varios caracteres y así guardar nodos adicionales.

    Este enlace aquí ( http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml ) dice que puede transformar un árbol de sufijos de 160MB en un árbol de sufijos comprimidos de 33MB. Toda una ganancia.

    Estos árboles comprimidos se utilizan para la concordancia de subcadenas genéticas en cadenas grandes. Solía ​​quedarme sin memoria con un árbol de sufijos, pero después de comprimirlo, el error de falta de memoria desapareció.

    Me gustaría poder encontrar un artículo sin pagar que explique mejor la implementación. ( http://dl.acm.org/citation.cfm?id=1768593 )