Persistenza di un trie in un file - C

Question

Ho un trie che sto usando per fare un po 'di elaborazione delle stringhe. Ho un semplice compilatore che genera trie da alcuni dati. Una volta generato, il mio trie non cambierà in fase di esecuzione.

Sto cercando un approccio in cui posso mantenere il trie in un file e caricarlo in modo efficace. Ho visto sqllite per capire come stanno persistendo b-tree ma il loro formato di file sembra leggermente avanzato e potrei non aver bisogno di tutti questi.

Sarebbe utile se qualcuno può fornire alcune idee per persistere e leggere il trie. Sto programmazione con C.

Answer 1

ho fatto qualche ricerca e ho trovato on-line i seguenti piccole gemme:

1. trie.h
2. trie.c

Un trie lavorare con serializzazione e deserializzazione. È stato originariamente scritto per l'uso in Python (c'è un corrispondente triemodule.c per legarlo a Python), ma è puro C; potresti estrarlo per idee o usarlo come desideri.

Aggiornamento:

Sembra i link non sono più di lavoro. Terrò gli originali, ma qui ci sono i link nella macchina Wayback:

1. trie.h
2. trie.c

Answer 2

Assumendo l'intera struttura dei dati si inserisce in memoria, un approccio ricorsivo serializzazione è più semplice . Sqllite funziona con strutture dati che non si adattano alla memoria, quindi è probabilmente eccessivo provare a copiare i loro metodi.

Ecco uno pseudocodice di esempio per la lettura/scrittura di un nodo. Funziona leggendo/scrivendo in modo ricorsivo i nodi figli. Non ha nulla di specifico, e dovrebbe funzionare anche per altre strutture di dati ad albero.

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

Se tutti i nodi sono della stessa dimensione allora si può solo enumerare i nodi (root = 0) e scrivere ciascuno di loro di un file alla loro indice. Durante la scrittura, però, dovrai modificare i loro riferimenti ad altri nodi per gli indici di quei nodi. Probabilmente avrai anche bisogno di un valore NULL. Si potrebbe usare -1 o si potrebbe usare (root = 1) e (NULL = 0).

Vi sarà probabilmente anche essere in grado di comprimere questi nodi un po 'cambiando i loro campi puntatore ad essere i tipi più piccoli.

Se i nodi sono diverse dimensioni, allora è più . complicato