Meilleure façon de stocker et de récupérer une structure de données DAWG pour un chargement rapide

Question

J'ai une liste de mots 500k + que j'ai chargée dans une structure de données DAWG. Mon application est pour les téléphones mobiles. Je ne veux bien sûr pas répéter toutes les étapes de conversion pour charger cette liste de mots dans un DAWG à chaque fois, car il faudrait beaucoup d'espace de stockage pour avoir la liste de mots sur le téléphone et beaucoup de temps pour le charger dans un DAWG à chaque fois . Donc, je cherche un moyen de stocker les données dans mon DAWG à un fichier ou DB dans un format qui à la fois économiser de l'espace et me permettre de le charger rapidement dans ma structure de données DAWG.

J'ai reçu une suggestion que je pourrais stocker chaque nœud dans une base de données SQLite, mais je ne suis pas sûr de savoir comment cela fonctionnerait exactement et si je l'ai fait, comment puis-je le récupérer rapidement. Je ne voudrais certainement pas lancer beaucoup de requêtes. Est-ce qu'un autre type de méthode de stockage serait mieux? J'ai également reçu des suggestions de création d'un fichier sérialisé ou pour le stocker sous forme de bitmap.

Answer 1

Vous pouvez effectuer un vidage de mémoire, utilisez simplement des décalages au lieu de pointeurs (en termes Java, placez tous les nœuds dans un tableau et utilisez l'index de tableau pour faire référence à un nœud). 500k ne semble pas comme quantité qui serait problématique pour les téléphones modernes, surtout que DAWG est déjà assez efficace. Si vous mmap le fichier, vous seriez capable de travailler avec la structure de données même si elle ne rentre pas dans la mémoire.

Answer 2

Avez-vous essayé de réduire la liste de mots? Conservez-vous seulement le mot stam si possible pour votre application?

Autre main: Vous ne devriez jamais reconstruire la structure de données car la liste de mots est constante. Essayez d'utiliser un vidage de mémoire comme suggéré. Utilisez mmap pour le fichier, la sérialisation java ou les techniques de pickle corn pickle pour charger une structure de données prête à l'emploi dans votre mémoire.

Answer 3

Je suppose que vous utilisez DAWG pour rechercher rapidement un mot dans un dictionnaire. DAWG a O(LEN) complexité de recherche.

Il y a plusieurs années, j'ai développé l'application J2ME et j'ai rencontré le même problème. Mais à cette période multiplié les téléphones ne pouvaient pas fournir definetely cette quantité de RAM de mémoire RAM, pour stocker 500K + chaînes) La solution que j'utilisée est la suivante:

1. Lire tous les mots, les trier, mettre dans un fichier ligne par ligne et pour chaque mot précalculé skipBytes. - nombre d'octets avant ce mot . Le calcul de skipBytes est trivial. pseudo-code est skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
2. Lorsque l'application commence à lire 500k skipBytes à un tableau int. Il est est beaucoup plus petit que les chaînes 500K)
3. Recherche de mot dans une recherche dict-binaire. Imaginez que vous le faites sur un tableau trié, mais au lieu de faire array[i] vous faites quelque chose comme RandomAccessFile.read(skipBytes[i]). Google Java Random Access Fichiers mon pseudo bien sûr que c'est juste la direction.

Complexité - O(LEN*LOG(N)) = LOG de la recherche binaire et la comparaison de chaînes est une complexité linéaire. LOG (500000) ~ 19, LEN ~ mot moyen leng dans le pire des cas est 50 (borne supérieure fantastique), donc l'opération de recherche est encore très rapide, seulement ~ 1000 opération, il sera fait en microsecondes. Avantage - petite utilisation de la mémoire.Je dois mentionner que dans le cas d'une application web lorsque de nombreux utilisateurs effectuent des recherches, LOG(N) devient important, mais si votre application fournit un service pour une seule personne LOG (500000) ne change pas beaucoup si elle ne fonctionne pas dans une boucle