Persistiendo un trie a un archivo - C

Question

Tengo un trie que estoy usando para hacer algo de procesamiento de cadenas. Tengo un compilador simple que genera trie a partir de algunos datos. Una vez generado, mi trie no cambiará en tiempo de ejecución.

Estoy buscando un enfoque donde puedo persistir el trie en un archivo y cargarlo de manera efectiva. He mirado sqllite para entender cómo persisten b-tree pero su formato de archivo parece un poco avanzado y es posible que no necesite todos esos.

Sería útil si alguien puede proporcionar algunas ideas para persistir y leer el trie. Estoy programación utilizando C

Answer 1

que hice algunas investigaciones y encontró las siguientes pequeñas joyas en línea:

1. trie.h
2. trie.c

un trie de trabajo con la serialización y deserialización. Originalmente fue escrito para Python (hay un triemodule.c correspondiente para vincularlo a Python), pero es C puro; podría extraer ideas o usarlas como lo desee.

actualización:

Parece que los enlaces ya no funcionan. Voy a mantener los originales, pero aquí están los eslabones de la Wayback Machine:

1. trie.h
2. trie.c

Answer 2

Suponiendo que toda la estructura de datos encaja en la memoria, un enfoque más simple es la serialización recursiva . Sqllite trabaja con estructuras de datos que no caben en la memoria, por lo que es probable que intente copiar sus métodos.

Aquí hay un pseudocódigo de ejemplo para leer/escribir un nodo. Funciona leyendo/escribiendo recursivamente los nodos secundarios. No tiene nada específico, y debería funcionar también para otras estructuras de datos de árbol.

void writeNode(Node *node) 
    write node data to file 
    write node.numOfChildren to file 
    for each child: 
     writeNode(child) 

Node *readNode() 
    Node *node = allocateNewNode() 
    read node data from file 
    read node.numOfChildren from file 
    for (i=0; i<node.numOfChildren; i++) 
     Node *child = readNode() 
     node.addChild(child) 

Answer 3

Si todos los nodos son del mismo tamaño, entonces puede simplemente enumerar los nodos (root = 0) y escribir cada uno de ellos a un archivo en su índice. Sin embargo, al escribirlos, tendrás que cambiar sus referencias a otros nodos a los índices de esos nodos. Probablemente también necesitará un valor de NULL. Usted podría utilizar -1 o puede utilizar (root = 1) y (NULL = 0).

Es probable que también sea capaz de comprimir estos nodos en cierta medida por el cambio de sus campos puntero ser tipos más pequeños.

Si los nodos son de diferentes tamaños, entonces es más complicado.