Persévérer dans un fichier - C

Question

J'ai un trie que j'utilise pour faire un traitement de chaîne. J'ai un compilateur simple qui génère trie à partir de certaines données. Une fois généré, mon trie ne changera pas au moment de l'exécution.

Je cherche une approche où je peux persister le trie dans un dossier et le charger efficacement. J'ai regardé sqllite pour comprendre comment ils persistent b-tree mais leur format de fichier semble peu avancé et je n'ai peut-être pas besoin de tout cela.

Il serait utile si quelqu'un peut fournir des idées pour persister et lire le trie. Je suis programmation en utilisant C.

Answer 1

Je l'ai fait quelques recherches et trouvé les petites gemmes suivantes en ligne:

1. trie.h
2. trie.c

A Trie travailler avec sérialisation et désérialisation. Il a été écrit à l'origine pour une utilisation en Python (il y a un triemodule.c correspondant pour l'attacher à Python), mais c'est du C pur; vous pouvez l'exploiter pour des idées ou l'utiliser comme vous le souhaitez.

Mise à jour:

Il semble que les liens ne fonctionnent plus. Je vais garder les originaux, mais voici les liens dans la machine à remonter le temps:

1. trie.h
2. trie.c

Answer 2

En supposant que l'ensemble de votre structure de données correspond à la mémoire, une approche de sérialisation récursive est plus simple . Sqllite travaille avec des structures de données qui ne rentrent pas dans la mémoire, il est donc probablement exagéré d'essayer de copier leurs méthodes.

Voici un exemple de pseudocode pour lire/écrire un noeud. Il fonctionne en lisant/écrivant récursivement les nœuds enfants. Il n'a rien de spécifique au trie, et devrait aussi fonctionner pour d'autres structures de données arborescentes.

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 tous vos nœuds sont de la même taille, alors vous pouvez simplement énumérer vos noeuds (root = 0) et écrire chacun d'entre eux dans un fichier à leur index. En les écrivant, vous devrez cependant modifier leurs références aux autres nœuds par rapport aux index de ces nœuds. Vous aurez probablement aussi besoin d'une valeur NULL. Vous pouvez utiliser -1 ou vous pouvez utiliser (root = 1) et (NULL = 0).

Vous serez probablement aussi capable de compresser ces nœuds un peu en changeant leurs champs de pointeur pour être plus petits types.

Si vos nœuds sont de tailles différentes alors il est plus compliqué