Implémentation autocomplète côté serveur

Question

Qu'est-ce qu'un moyen rapide et efficace d'implémenter le composant côté serveur pour une fonctionnalité de saisie semi-automatique dans une zone de saisie HTML? J'écris un service de saisie semi-automatique des requêtes utilisateur dans la boîte de recherche principale de notre interface web, et les complétions sont affichées dans une liste déroulante ajax-powered. Les données que nous utilisons sont simplement une grande table de concepts que notre système connaît, ce qui correspond à peu près à l'ensemble des titres de pages wikipedia. Pour ce service, la rapidité est évidemment d'une importance capitale, car la réactivité de la page Web est importante pour l'expérience de l'utilisateur.

La mise en œuvre actuelle charge simplement tous les concepts en mémoire dans un ensemble trié et effectue une simple recherche de journal (n) sur une séquence de touches utilisateur. Le jeu de mots est ensuite utilisé pour fournir des correspondances supplémentaires au-delà de la correspondance la plus proche. Le problème avec cette solution est qu'elle n'est pas évolutive. Il est actuellement en cours d'exécution par rapport à la limite d'espace de segment VM (j'ai défini -Xmx2g, ce qui correspond à peu près à nos machines 32 bits), ce qui nous empêche d'étendre notre table de concepts ou d'ajouter plus de fonctionnalités. Passer à des machines virtuelles 64 bits sur des machines disposant de plus de mémoire n'est pas une option immédiate.

J'ai hésité à commencer à travailler sur une solution basée sur disque car je crains que le temps de recherche de disque ne tue les performances. Existe-t-il des solutions possibles qui me permettront de mieux évoluer, que ce soit entièrement en mémoire ou avec des implémentations rapides appuyées par des disques?

: Edits

@Gandalf: Pour notre cas d'utilisation, il est important que le l'autocomplétion est complet et est non seulement une aide supplémentaire pour l'utilisateur. Quant à ce que nous sommes en train de compléter, il s'agit d'une liste de paires de types de concepts. Par exemple, les entrées possibles sont [("Microsoft", "Société de logiciels"), ("Jeff Atwood", "Programmeur"), ("StackOverflow.com", "Site Web")]. Nous utilisons Lucene pour la recherche complète une fois qu'un utilisateur sélectionne un élément de la liste de saisie semi-automatique, mais je ne suis pas encore sûr que Lucene fonctionnerait bien pour la saisie semi-automatique elle-même.

@Glen: Aucune base de données n'est utilisée ici. Quand je parle d'une table, je veux simplement dire la représentation structurée de mes données.

@Jason Day: Mon implémentation d'origine de ce problème consistait à utiliser un Trie, mais le problème de mémoire était pire que l'ensemble trié en raison du besoin d'un grand nombre de références d'objet. Je lis sur les arbres de recherche ternaires pour voir si cela pourrait être utile.

Answer 1

Avec un ensemble de cette taille, j'essaierais quelque chose comme un index Lucene pour trouver les termes que vous voulez, et définir une tâche de minuterie qui se réinitialise après chaque coup de touche, avec un retard de 0,5 seconde. De cette façon, si un utilisateur tape plusieurs caractères rapidement, il n'interroge pas l'index à chaque coup, seulement lorsque l'utilisateur s'interrompt une seconde. Les tests d'utilisabilité vous permettront de savoir combien de temps cette pause devrait être.

Timer findQuery = new Timer(); 
... 
public void keyStrokeDetected(..) { 
    findQuery.cancel(); 
    findQuery = new Timer(); 
    String text = widget.getEnteredText(); 
    final TimerTask task = new TimerTask() { 
     public void run() { 
     ...query Lucene Index for matches 
     } 
    }; 
    findQuery.schedule(task, 350); //350 ms delay 
} 

Un pseduocode existe, mais c'est l'idée. De plus, si les termes de la requête sont définis, l'index Lucene peut être pré-créé et optimisé.

Answer 2

Si vous ne pouvez pas charger physiquement toutes les données dans la mémoire RAM, vous devrez en avoir sur le disque.

Quel DB utilisez-vous? Par exemple, Oracle a une option dans laquelle vous pouvez conserver la totalité de la table en mémoire et effectuer vos requêtes par rapport à celle-ci. MySQL prétend également avoir des capacités en mémoire, mais je ne connais pas grand-chose à MySQL.Vous pouvez ensuite supprimer votre cache Java, ou vous pouvez utiliser le cache pour les recherches les plus populaires/récentes. De toute évidence, lorsque vous manquez de RAM, certaines données seront sur le disque lorsque vous en ferez la demande, mais en fonction de la charge sur le système, ce sera seulement un problème pour la première pression sur la touche, pas les suivantes , car la rangée sera en mémoire après cela. Si la recherche de disque vous ralentit, vous pouvez rechercher des lecteurs SSD pour accélérer vos lectures.

Answer 3

J'avais une exigence similaire. J'ai utilisé la base de données relationnelle avec une seule table synthétique bien indexée (évitant les jointures et les vues pour accélérer les recherches), et le cache en mémoire (Ehcache) pour stocker les entrées les plus utilisées. En utilisant le cache MRU vous pourrez avoir des temps de réponse instantanés pour la plupart des recherches, et il n'y a probablement rien qui puisse battre la base de données relationnelle en accédant à la colonne indexée dans une grande table stockée sur le disque.

Ceci est la solution pour les grands ensembles de données que vous ne pouvez pas stocker sur le client et cela fonctionne assez rapidement (la recherche non-mise en cache a toujours été récupérée sous 0,5 secondes dans mon cas). Il est également évolutif horizontalement - vous pouvez toujours ajouter des serveurs et des serveurs de base de données supplémentaires.

Vous pouvez également jouer avec la mise en cache des résultats les plus utilisés sur le client, surtout si vous l'avez déjà implémenté. Dans mon cas, la solution côté serveur est assez rapide et les temps de chargement des clients sont assez lents, ce qui n'est pas garanti.

P.S. Avoir une requête client uniquement lorsque l'utilisateur fait une pause pendant un certain temps pour éviter les recherches répétées comme suggéré est une bonne solution. Sur mon client, j'interroge la base de données uniquement après que les trois premiers caractères soient entrés, car moins de cela renvoie trop de résultats dans toutes les instances.

Answer 4

Peut-être que j'ai mal compris votre question, mais ne pourriez-vous pas utiliser un plugin JQuery pour Ajax les informations de votre application?

Je l'ai utilisé celui-ci avant:

Ajax Auto Suggest v2

Answer 5

Je l'ai fait pour les petits ensembles de données à l'aide d'un Ternary search tree. Le code DDJ n'est pas trop difficile à convertir en Java, mais il suppose que tout l'ensemble de données rentrera dans la mémoire. Il existe des implémentations sur le disque des arbres de recherche Ternary (here est un en python), mais bien sûr, ils vont être moins performants. Puisque les arbres de recherche ternaire excellent dans les correspondances partielles, la performance peut être adaptée à vos besoins.

Answer 6

Y at-il des solutions possibles qui Permettez-moi une meilleure échelle

Oui, Oracle. C'est le genre de chose pour lequel les bases de données sont construites. Il suffit d'indexer les colonnes pertinentes. Si vous travaillez contre le mur des solutions en mémoire, le compromis avec le temps de recherche de disque ou la latence du réseau est probablement discutable. Surtout si vous insérez une couche de mise en cache entre les deux.

En outre, vous pouvez peut-être réduire le nombre de résultats si vous modifiez un peu le code côté client. Tels que la définition d'un nombre minimum de caractères de type avant l'exécution d'une requête ou la définition d'une fraction de seconde de retard après que l'utilisateur arrête de taper.Si vous les utilisez déjà, définissez-les un peu plus haut.

Answer 7

Je fini par résoudre celui-ci via Lucene; les tests de performance initiaux semblent suffisants pour notre cas d'utilisation. Un petit piratage était nécessaire pour que les requêtes de préfixes fonctionnent, car je courrais dans l'exception TooManyClauses lors de l'expansion de requêtes telles que "Jeff At *". J'ai fini d'enrouler mon IndexReader avec un FilterIndexReader, et j'ai fixé un nombre maximal de termes renvoyés lors d'un appel de préfixe. Voici mon code:

Directory directory = FSDirectory.getDirectory(indexDir); 
IndexReader reader = IndexReader.open(directory); 
FilterIndexReader filteredReader = new FilterIndexReader(reader) { 
    @Override public TermEnum terms(Term t) throws IOException { 
    final TermEnum origEnum = super.terms(t); 

    return new TermEnum() { 
     protected int count = 0; 
     @Override public boolean next() throws IOException { 
     if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) 
      return origEnum.next(); 
     else return false; 
     } 

     @Override public Term term() { 
     return origEnum.term(); 
     } 

     @Override public int docFreq() { 
     return origEnum.docFreq(); 
     } 

     @Override public void close() throws IOException { 
     origEnum.close(); 
     } 
    }; 
    } 
}; 

IndexSearcher searcher = new IndexSearcher(filteredReader); 

Answer 8

Pour ceux qui trébuchent sur cette question ...

Je viens de publier un server-side autocomplete implementation sur Google Code. Le projet comprend une bibliothèque java qui peut être intégrée dans des applications existantes et un serveur autocomplete HTTP AJAX autonome.

Mon espoir est qui permet aux gens d'intégrer autocomplete efficaces dans leurs applications. Kick les pneus!

Answer 9

I utilisé Hashtable et mmap() et 10,000,000+ dossiers liste terme n'est pas problème. Voir démo ici: http://olegh.ath.cx/autocomplete.html

Answer 10

utilisation structure de données arborescente ici est le wiki http://en.wikipedia.org/wiki/Trie