J'ai une carte en Java. Je voudrais comparer une chaîne source à tous les éléments de la carte et renvoyer la meilleure correspondance basée sur un algorithme de rapport levenshtein. Je me demande quelle serait la meilleure façon d'effectuer cette vérification sur tous les éléments de la liste.Méthode optimale pour effectuer une meilleure correspondance levenshtein contre la carte en Java
Merci, Matt
Depuis le rapport de levenshtein dépend à la fois de la source et sur la cible, les valeurs changent pour chaque chaîne source. À moins qu'il y ait une forte probabilité que la chaîne source puisse être répétée lors de recherches ultérieures, il suffit de parcourir les éléments de la carte. Si la vitesse est vraiment un problème, assurez-vous que vous utilisez les derniers compilateurs Java et utilisez les options d'optimisation.
Et bien sûr, si vous ne le faites pas déjà, utilisez une implémentation Levenshtein optimisée standard, comme celle de la chaîne StringStils de commons-lang.
Si l'itération de tous les éléments de la carte est trop coûteuse, vous pouvez envisager d'utiliser k-gram indexes.
Vous ne pourrez pas obtenir de meilleures performances que O (n) avec une carte standard - utilisez simplement l'approche naïve de les tester séquentiellement.
Il existe des moyens beaucoup plus efficaces de le faire, cependant. L'un d'eux s'appelle un bk-tree. Fondamentalement, vous construisez un arbre de n-way, avec des bords déterminés par la distance de levenshtein entre les noeuds. Ensuite, vous pouvez utiliser le triangle inequality pour réduire massivement les nœuds que vous devez rechercher. Pour de courtes distances, c'est très efficace. Voici un blog article que j'ai écrit il y a quelque temps, en le décrivant en détail. Avec un peu de travail supplémentaire, vous pouvez interroger pour le plus proche voisin, plutôt que d'interroger à plusieurs reprises avec la distance 1, 2, etc
blog ne fonctionne pas Nick! – Will
Correction maintenant, merci. –