Mise en œuvre de la distance Levenshtein pour mysql / recherche floue?

Question

Je voudrais être en mesure de rechercher une table comme suit pour smith comme obtenir tout ce qu'il dans 1 variance.

Données:

 O'Brien Smithe Dolan Smuth Wong Smoth Gunther Smiht 

J'ai examiné l'utilisation de la distance Levenshtein quelqu'un sait comment mettre en œuvre cela avec elle?

Answer 1

Est-ce que cela aide? Requête de distance MySQL Levenshtein

EDIT: L'ancien lien Levenshtein Distance comme une fonction stockée MySQL (Google Cache) est cassé, Merci à Robert pour le souligner dans le commentaire.

Answer 2

Afin d'optimiser l'efficacité de la recherche à l'aide de levenshtein, vous avez besoin d'un moyen efficace, spécialisé index, comme un bk-arbre. Malheureusement, aucun système de base de données que je connais, y compris MySQL, met en œuvre bk-arbre d'index. Cela est d'autant plus compliqué si vous êtes à la recherche pour la recherche de texte intégral, au lieu de seulement un seul terme par ligne. De la main gauche, je ne pense pas de toute façon que vous pourriez faire de l'indexation de texte intégral dans une manière qui permet la recherche basée sur la distance de levenshtein.

Answer 3

Il y a une implémentation de distance de Mysql UDF de la fonction distance de Levenshtein

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

Il est mis en œuvre en C et a de meilleures performances que le "MySQL Levenshtein distance requête" mentionné par schnaader

Answer 4

Une mise en œuvre pour la distance damerau-levenshtein peut être trouvée ici: Algorithme Damerau-Levenshtein: Levenshtein avec transpositions L'amélioration par rapport à la distance pure de Levenshtein est que l'échange de caractères est considéré. Je l'ai trouvé dans les commentaires du lien de schnaader, merci!