J'ai un Je cherche une approche où je peux persister la trie dans un fichier et le charger efficacement. J'ai regardé Il serait utile que quelqu'un puisse fournir quelques idées à persister et à lire le trie que j'utilise pour effectuer 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.
sqllite pour comprendre comment ils persistent b-arbre mais leur format de fichier a l'air avancé et je n'ai peut-être pas besoin de tous ceux-ci.
trie . Je programmment en utilisant c.
4 Réponses :
J'ai fait des recherches et j'ai trouvé les petits gemmes suivants en ligne:
trie.h
trie.c
Une trie de travail avec sérialisation et désérialisation. Il a été écrit à l'origine destiné à être utilisé dans Python (il y a un triemodule.c pour l'attacher à Python), mais c'est pur c; Vous pourriez l'avoir pour les 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 de la machine de navigager:
Semble prometteur.let moi, essayez d'essayer.
Vous pouvez trouver ces fichiers dans cette git: github.com/jamestbrown/biopython/tree/master / Bio
En supposant que toute votre structure de données convient à la mémoire, une approche de sérialisation récursive est la plus simple. SQLLITE fonctionne avec des structures de données qui ne conviendront pas dans la mémoire, il est donc probablement surchargé d'essayer de copier leurs méthodes.
Voici exemple pseudocode pour lire / écrire un nœud. Cela fonctionne en lisant / écriture récursive les nœuds enfants. Il n'a rien de spécifique Trie et devrait également fonctionner pour d'autres structures de données d'arbres. P>
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)
Si tous vos nœuds ont la même taille, vous pouvez simplement énumérer vos nœuds Vous serez probablement aussi en mesure de compresser quelque peu ces nœuds en modifiant leurs champs de pointeur pour être des types plus petits.
Si vos nœuds sont différentes tailles, il est plus compliqué. (root = 0) et écrivez chacun d'entre eux dans un fichier à leur index. Tout en les écrivant, vous devrez modifier leurs références à d'autres nœuds aux index des nœuds, cependant. Vous aurez probablement également besoin d'une valeur null . Vous pouvez utiliser -1 ou vous pouvez utiliser (root = 1) et ( null = 0).
Une fois que vous avez généré une trie en mémoire, il n'est pas complexe de l'écrire dans un fichier, avec MMAP, c'est comme si nous réexécutons la trie dans un bloc de mémoire continue, ou vous pouvez écrire chaque nœud dans un fichier dans un fichier fonction récursive.
"Ce n'est pas complexe de l'écrire dans un fichier, avec NMAP" n'est pas une réponse très utile. Pourriez-vous s'il vous plaît montrer comment faire? Même chose pour l'approche de la fonction récursive: à quoi ressemblerait-il dans la pratique?