Implémentation Trie (ou Prefix Tree) sauvegardée par fichier

Question

Je dois stocker beaucoup de chaînes dans la carte C++ pour conserver les chaînes uniques et quand une chaîne dupliquée se produit, il suffit d'incrémenter le compteur (paire.second). J'ai utilisé la carte C++ et cela correspond bien à cette situation. Depuis le fichier que le traitement est parti maintenant jusqu'à 30gig j'essaye de garder ceci dans un dossier au lieu de la mémoire.

Je suis également tombé sur trie qui est plus rapide que la carte dans ce cas. Quelqu'un a-t-il connaissance de l'implémentation de la trie? Je suis tombé sur une implémentation Trie similaire à ce que je cherche, mais ne semble pas être sans bug ..

Answer 1

Si vous pouvez trier votre fichier contenant les chaînes, alors lire la liste triée et compter les doublons serait facile. (Vous pouvez conserver le fichier d'origine et créer un nouveau fichier de chaînes triées.) Le tri de fichiers volumineux est une technologie ancienne. Vous devriez être capable de trouver un utilitaire pour cela.

Si vous ne pouvez pas trier, alors considérez digesting les chaînes. MD5 peut être exagéré pour votre usage. Vous pouvez paver quelque chose. Pour des milliards de chaînes, vous pouvez utiliser des condensés de 8 octets. Utilisez un arbre (probablement un BST) de digests. Conservez les décalages de fichier des chaînes uniques qui produisent ce condensé pour chaque résumé.

Lorsque vous lisez une chaîne, calculez son résumé et recherchez-la. Si vous ne trouvez pas le résumé, vous savez que la chaîne est unique. Rangez-le dans l'arbre. Si vous trouvez le résumé, vérifiez chaque chaîne associée pour une correspondance et gérez-la en conséquence.

Pour comparer les chaînes, vous devez accéder au fichier, car tout ce que vous avez stocké correspond aux décalages de fichiers.

Ce qui est important de se rappeler que si deux condensés sont différents, les chaînes qui les ont produites doivent être différentes. Si les condensés sont les mêmes, les chaînes peuvent ne pas être les mêmes, vous devez donc vérifier. Cet algorithme sera plus efficace lorsqu'il y aura moins de chaînes en double.

Answer 2

Comment allez-vous charger 30 Go en mémoire en une fois? Et comme c'est un comportement basé sur un dictionnaire que vous voulez, j'imagine que chaque fois que vous insérez, ou incrémentez, vous aurez besoin de charger le fichier entier (même si morceau par morceau) pour la recherche.

Je suggère d'utiliser une base de données. C'est ce qu'ils sont pour ...