Meilleure pratique pour la distance Levenshtein sur SQL Server

J'ai une application Web et un dictionnaire mobile qui utilise SQL Server. J'essaie d'implémenter une version simple de la fonctionnalité "Voulez-vous dire". Si la phrase que l'utilisateur a entré n'existe pas dans la base de données, j'ai besoin de faire des suggestions. J'ai l'intention d'utiliser l'algorithme de distance levenshtein. Mais il y a un point que je ne pouvais pas comprendre: ai-je besoin de calculer la distance levenshtein entre l'entrée de l'utilisateur et tous les mots qui existent dans ma base de données un par un?Meilleure pratique pour la distance Levenshtein sur SQL Server

Supposons que j'ai un million de mots dans ma base de données. Lorsque l'utilisateur entre un mot incorrect, vais-je calculer la distance d'un million de fois?

Évidemment, cela nécessiterait beaucoup de temps. Quelle est la meilleure pratique pour cette situation?

Source

2017-09-02 Umut Derbentoğlu

Oui, vous auriez besoin de comparer 1 par 1. Il n'y a pas de magie. – Paparazzi

Peut être un peu daté, mais jetez un coup d'œil à https://stackoverflow.com/questions/560709/levenshtein-distance-in-t-sql –

Si vous faites cela pour autre chose qu'une expérience d'apprentissage, je vous conseillerais sérieusement de reconsidérer faire cela dans la base de données. Une base de données sql est très bonne pour les requêtes relationnelles, mais quand il s'agit de quelque chose comme ça, il existe de bien meilleurs outils que vous pouvez utiliser. –

Avez-vous déjà consulté la fonction définie par l'utilisateur SOUNDEX disponible dans SQL Server?

Vous pouvez utiliser un déclencheur qui calcule l'indice sonore d'une colonne et l'enregistre à côté de cette colonne chaque fois que la colonne est mise à jour. Lors de la recherche, vous pouvez calculer l'indice sonore du critère de recherche et le comparer avec la colonne soundex stockée dans le tableau.

Source

2017-09-02 10:03:03

Qu'en est-il des autres langues? Dans mon application, les utilisateurs entreront des mots espagnols ou turcs. –

En termes de mise en œuvre, je l'ai configuré pour que la liste de mots soit mise en cache sur le serveur Web et y effectue les comparaisons. Vous ne voulez pas exécuter une procédure stockée de base de données chaque fois qu'un utilisateur effectue une frappe. Pour des raisons de performances, vous devez rendre le dos & aussi abouti et simple que possible. En outre, les langages procéduraux sont mieux à faire ces types de calculs que les langages déclaratifs de toute façon. Si possible, vous pouvez créer un petit cache indexé sur l'ordinateur client de sorte que les étapes finales puissent être terminées sans passer d'appels Web.

Pour ce qui est des correspondances réelles, recherchez l'algorithme Double Metaphone de Lawrence Philips. Ce n'est pas aussi bon que Google "vouliez-vous dire?" mais c'est beaucoup mieux que SOUNDEX ... Et ça a été traduit en plusieurs langages de codage. En utilisant double metaphone en conjonction avec la distance de Levenshtein, vous devriez être en mesure de faire de bons matchs.

Source

2017-09-02 21:51:47

Meilleure pratique pour la distance Levenshtein sur SQL Server

Répondre

Questions connexes