Quel est le meilleur algorithme d'autocomplétion/suggestion, structure de données [C++/C] ?

Question

Nous voyons que Google, Firefox et certaines pages AJAX affichent une liste d'éléments probables lorsque l'utilisateur tape des caractères.

Quelqu'un peut-il donner un bon algorithme et une bonne structure de données pour l'implémentation de l'autocomplétion ?

Answer 1

A essai devrait être assez utile pour quelque chose comme ça

Edit : Et voici un exemple montrant comment l'utiliser pour cela. http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Voici une comparaison de 3 différents mises en œuvre de l'autocomplétion (bien que ce soit en Java et non en C++).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

Lors de la recherche de clés, le trie est légèrement plus rapide que l'implémentation Set, tandis que les deux sont un peu plus rapides que la version basée sur Db.

Le coût d'installation du Set est nettement inférieur à celui de la solution Trie ou DB. Je suppose donc que vous devez décider si vous allez créer ces recherches fréquemment ou si la vitesse de recherche est une priorité.

Comme ces résultats sont basés sur Java, votre expérience variera avec une solution C++, mais au moins cela vous montre quelques possibilités.

Answer 2

Pour les grands ensembles de données, un bon candidat pour le backend serait les arbres de recherche ternaires. Ils combinent le meilleur de deux mondes : le faible encombrement des arbres de recherche binaires et l'efficacité temporelle basée sur les caractères des essais de recherche numériques.

Voir dans le journal du Dr Dobbs : http://www.ddj.com/Windows/184410528

L'objectif est d'extraire rapidement un ensemble fini de résultats au fur et à mesure que l'utilisateur tape. Considérons d'abord que pour rechercher "informatique", vous pouvez commencer à taper "ordinateur" ou "science" mais pas "ordinateur". Donc, étant donné une phrase, générer les sous-phrases commençant par un mot. Maintenant, pour chacune des phrases, introduisez-les dans le CT (arbre de recherche ternaire). Chaque nœud du TST représentera un préfixe d'une phrase qui a été tapée jusqu'à présent. Nous stockons les 10 meilleurs résultats (disons) pour ce préfixe dans ce nœud. S'il y a beaucoup plus de candidats que la quantité finie de résultats (10 ici) pour un nœud, il devrait y avoir une fonction de classement pour résoudre la compétition entre deux résultats.

L'arbre peut être construit une fois toutes les quelques heures, en fonction du dynamisme des données. Si les données sont en temps réel, alors je pense qu'un autre algorithme donnera un meilleur équilibre. Dans ce cas, l'exigence absolue est la récupération rapide des résultats pour chaque touche tapée, ce qu'il fait très bien.

Les complications seront plus grandes si l'on suggère des corrections orthographiques. Dans ce cas, les algorithmes de distance d'édition devront également être pris en compte.

Pour les petits ensembles de données comme une liste de pays, une simple implémentation de Trie suffira. Si vous avez l'intention d'implémenter une telle liste déroulante d'autocomplétion dans une application web, le widget d'autocomplétion de YUI3 fera tout pour vous après avoir fourni les données dans une liste. Si vous utilisez YUI3 comme simple frontal pour un autocomplétion soutenu par de grandes données, faites le service web basé sur TST en C++, et utilisez ensuite script la source de données du noeud du widget autocomplétion pour récupérer les données du service web au lieu d'une simple liste.

Answer 3

Arbres segmentés peut être utilisé pour mettre en œuvre efficacement auto complète

Answer 4

Si vous voulez suggérer les compléments les plus populaires, un "arbre de suggestion" peut être un bon choix : Suggérer un arbre

Answer 5

Pour une solution simple : vous générez un 'candidat' avec une édition minimale ( Levenshtein ) distance (1 ou 2) alors vous testez l'existence du candidat avec un conteneur de hachage ( set suffira pour une solution simple, puis utilisez ensemble non ordonné du tr1 ou du boost).

Exemple : Vous avez écrit carr et vous voulez car. arr est généré par 1 suppression. Est-ce que arr est dans votre unordered_set ? Non. crr est généré par 1 suppression. Est-ce que crr est dans votre unordered_set ? Non. car est généré par 1 suppression. Est-ce que car est dans votre unordered_set ? Oui, vous avez gagné.

Bien sûr, il y a l'insertion, la suppression, la transposition etc...

Vous constatez que c'est dans votre algorithme de génération de candidats que vous perdez du temps, surtout si vous n'avez que très peu d'expérience. ensemble non ordonné .