Étant donné une liste de mots - ce qui serait un bon algorithme pour l'achèvement de mots en Java? Compromis: vitesse/efficacité/empreinte mémoire

Question

J'explore les besoins matériels/logiciels (l'objectif ultime est l'application mobile Java) pour une application libre/payante potentielle.

L'application débutera avec ce but simple: Compte tenu d'une liste de mots pertinents dans une base de données, pour être en mesure de compléter le mot sur une seule entrée de chaîne. En d'autres termes, je connais déjà le contenu de la base de données - mais l'empreinte mémoire/vitesse/efficacité de recherche de l'algorithme déterminera la quantité de données supportées. Je commence au début avec des recherches arborescentes basées sur des suffixes, mais je me demande si quelqu'un a de l'expérience avec les compromis vitesse/taille de mémoire de cette approche simple par rapport aux plus complexes dont on parle dans les conférences. Honnêtement, l'application initiale n'a probablement que moins de 500 mots dans le contexte, donc cela pourrait ne pas importer, mais finalement l'application pourrait s'étendre à des dizaines de milliers ou des centaines de milliers d'enregistrements - la question de la vitesse par rapport à l'empreinte mémoire. Je suppose que je pourrais commencer avec quelque chose de simple et passer plus tard, mais j'espère comprendre le compromis plus tôt!

Answer 1

L'achèvement du mot suggère que vous voulez trouver tous les mots commençant par un préfixe donné.

Tries sont bons pour ceci, et particulièrement bons si vous ajoutez ou enlevez des éléments - d'autres noeuds n'ont pas besoin d'être réaffectés.

Si le dictionnaire est assez statique et que la recherche est importante, envisagez une structure de données beaucoup plus simple: placez vos mots dans un vecteur ordonné! Vous pouvez faire binary-search pour découvrir un candidat commençant par le préfixe correct, et une recherche linéaire de chaque côté de celui-ci pour découvrir tous les autres candidats.