Quelles sont les bonnes structures de données pour les algorithmes d'auto-complétion? Quelles structures de données permettent de trouver efficacement des chaînes contenant une sous-chaîne particulière?structure de données pour l'auto-complétion
Si vous cherchez à faire quelque chose de similaire à la façon dont Google implémente est saisie semi-automatique, vous pouvez consulter un arbre de recherche ternaire:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Cependant, si vous voulez trouver une sous-chaîne aléatoire dans une chaîne, essayez un arbre de suffixes généralisés.
Cela ne fonctionne-t-il pas seulement si vous voulez seulement faire correspondre les préfixes? par exemple. un arbre de recherche ternaire vous aide à faire correspondre "ab" dans "abcd", mais pas "bc" dans "abcd" (peut être épais, ne pas savoir beaucoup sur les arbres de recherche ternaires, et n'a donné qu'un coup d'oeil fugace). –
Je pense que oui, en général ça marche dans un x "commence avec". Cependant, dans la pratique, il semble que toutes les fonctions d'autocomplétion que j'ai utilisées aient fonctionné. –
fwiw un certain nombre de widgets auto-complétés J'utilise la correspondance au jour le jour n'importe où dans la chaîne; néanmoins - lien utile, donc +1. –
Découvrez suffix array et suffix tree.
Homme, j'ai cherché l'algorithme d'Ukkonen pendant des années et je ne l'ai jamais su! J'ai une application qui nécessite une correspondance efficace des sous-chaînes avec des erreurs. J'ai même demandé dans des forums comme celui-ci dans le passé et n'a pas obtenu de bons conseils. Tu as fait ma journée! – swestrup
@swestrup: Je suis heureux que je vous ai aidé à tracer cette information :) Vous devriez obtenir une copie de * The Algorithm Design Manual *, http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref = sr_1_1? Ie = UTF8 & s = livres & qid = 1268325877 & sr = 8-1 c'est une * compilation * inestimable de structures de données, d'algorithmes et de références bibliographiques/URL;) –
Si vous faites des préfixes (ce que font la plupart des autocomplètes), un arbre de recherche ternaire est aussi ce que je recommande. Si vous faites des infixes généraux, allez avec un arbre de suffixes, comme mentionné ci-dessus.
Nah, c'est une idée stupide. Utilisez des arbres de suffixe. Beaucoup mieux. – swestrup
si c'est idiot, éditez votre réponse –
Comme alternative aux tableaux de suffixes, arbres et essais, jetez un oeil à Directed Acyclic Word Graphs (DAWG) et à la variante compressée (CDAWG). Ils peuvent être construits en temps linéaire, prendre de l'espace linéaire et permettre la recherche par sous-chaîne.
Avec une fonction de recherche plus compliquée, vous pouvez même prendre en charge un jeu limité de caractères génériques.
J'ai créé une application pour ce que vous voulez. Il s'agit de l'algorithme de saisie semi-automatique le plus efficace basé sur le préfixe.
Si l'ensemble des suggestions de saisie semi-automatique est commandé rang, un SuggestTree est une bonne structure de données. Pour n'importe quel préfixe donné, il fournit un accès rapide aux k suggestions commençant par ce préfixe.
http://en.wikipedia.org/wiki/Trie – frankc