Structure de données espace-efficace pour stocker une liste de mots?

Question

Y a-t-il quelque chose de mieux qu'un Trie pour cette situation?

• Enregistrement d'une liste de mots anglais ~ 100k
• a besoin d'utiliser la mémoire minimale
• Lookups doivent être raisonnables, mais ne doit pas être rapide comme l'éclair

Je travaille avec Java, donc ma première tentative était d'utiliser simplement un Set <String>. Cependant, je cible un appareil mobile et commence à manquer de mémoire. Puisque beaucoup de mots anglais partagent des préfixes communs, un trie semble être un pari décent pour sauver de la mémoire - quelqu'un connaît d'autres bonnes options?

EDIT - Plus d'informations - La structure de données sera utilisée pour deux opérations

• : Est-Answering un mot XYZ dans la liste?
• Génération du quartier de mots autour de XYZ avec une lettre différente

Merci pour les bonnes suggestions

Answer 1

Que faites-vous? Si c'est la vérification orthographique, vous pouvez utiliser un filtre bloom - voir ceci code kata.

Answer 2

Vous avez encore de maintenir la structure de l'arbre lui-même avec Trie. Huffman encoding l'alphabet ou N-lettres (pour les formes courantes comme "tion", "un", "ing") peut tirer parti de la fréquence d'occurrence dans votre dictionnaire et compresser l'entrée en bits.

Answer 3

Une structure I vu pour minimiser l'espace dans un dictionnaire d'orthographe est de coder chaque mot comme:

• le nombre de caractères (un octet) en commun avec la dernière; et
• la nouvelle fin.

donc la liste des mots

HERE   would encode as THIS 
sanctimonious      0,sanctimonious 
sanction       6,on 
sanguine       3,guine 
trivial       0,trivial 

vous économisez 7 octets directement là-bas (19%), je soupçonne que l'épargne serait similaire pour un dictionnaire de 20.000 mots juste en raison des distances minimales entre (préfixes communs de) mots adjacents.

Pour accélérer la recherche, il y avait une table de 26 entrées en mémoire qui contenait les décalages de départ pour les mots commençant par a, b, c, ..., z. Les mots à ces décalages avaient toujours 0 comme premier octet car ils n'avaient pas de lettres communes avec le mot précédent. Cela semble être une sorte de trie mais sans les pointeurs, ce qui serait sûrement trop cher si tous les caractères de l'arbre étaient associés à un pointeur de 4 octets.

Rappelez-vous, c'était à partir de mon CP/M jours où la mémoire était beaucoup plus rare qu'elle ne l'est maintenant.

Answer 4

Une Patricia Trie peut être plus approprié:

http://en.wikipedia.org/wiki/Patricia_tree

Ma mémoire (floue) me dit qu'il a été utilisé dans certains des premiers texte intégral des moteurs de recherche ...

Paul.

Answer 5

idée complètement sauvage ... (à savoir très probablement très mal)

Que diriez-vous de stocker les mots comme un arbre de toutes les combinaisons de lettres possibles?

Ensuite, chaque "mot" ne coûte qu'un seul caractère et deux pointeurs (un pour le caractère et un pour un terminateur.) Ainsi, plus il y a de lettres communes, moins le coût de chaque mot.

 . . 
    // 
    r-p-s-. 
    /\\ 
    a \s-. 
/ t-. 
c  \ 
     s-. 

carpe voiture Carpes voitures panier charrettes

Donc, pour 9 caractères et 14 pointeurs nous obtenons 6 "mots" totalisant 25 lettres.

Les recherches seraient rapides (les recherches de pointeur au lieu des comparaisons de caractères) et vous pourriez faire quelques optimisations de tige pour économiser encore plus d'espace ...?

EDIT: On dirait que j'ai réinventé la roue. ;-)

Answer 6

liés au poste de Paul:

Toute raison pour laquelle vous ne pouvez pas envisager un dans votre cas Trie? Si c'est juste un problème de implementaiton, voici une mise en œuvre serré de l'insert Patricia et de Trie rechercher dans C (NIST):

Patricia Insert in C

Patricia Search in C