Trouver la similitude de deux chaînes

Question

Je suis à la recherche d'un algorithme qui prend 2 cordes et va me donner un "facteur de similitude".

En gros, je vais avoir une entrée qui peut être mal orthographié, avoir des lettres transposées, etc, et je dois trouver la correspondance la plus proche(es) dans une liste de valeurs possibles que j'ai.

Ce n'est pas pour la recherche dans une base de données. Je vais avoir une liste en mémoire de 500 chaînes de match contre, tous les moins de 30 caractères, de sorte qu'il peut être relativement lente.

Je sais que cela existe, je l'ai vu avant, mais je ne me souviens pas de son nom.

---

Edit: Merci de remarquer Levenshtein et de Hamming. Maintenant, lequel dois-je mettre en œuvre? En gros, ils mesurent des choses différentes, qui peuvent tous deux être utilisés pour ce que je veux, mais je ne suis pas sûr que l'on est plus approprié.

J'ai lu sur les algorithmes, Hamming semble évidemment plus rapide. Depuis, ni de détecter les deux personnages étant transposée (ie. La jordanie et Jodran), qui sera à mon avis une erreur commune, qui sera plus précis pour ce que je veux? Quelqu'un peut-il m'en dire un peu plus sur les compromis?

Answer 1

Ok, donc les algorithmes standards sont:

1) la distance de Hamming Seulement bon pour les chaînes de même longueur, mais très efficace. Fondamentalement, c'simplement de compter le nombre de caractères distincts. Pas utile pour une recherche floue, de texte en langage naturel.

2) distance de Levenstein. La distance de Levenstein mesure de la distance en termes de nombre d'opérations nécessaires pour transformer une chaîne à l'autre. Ces opérations comprennent l'insertion, la suppression et la substition. L'approche standard de calcul de la distance de Levenstein est d'utiliser la programmation dynamique.

3) Généralisée Levenstein/(distance de damerau–Levenshtein) Cette distance prend également en considération les transpositions de caractères dans un mot, et est probablement la distance d'édition la plus adaptée pour la correspondance floue de saisies manuellement texte. L'algorithme pour calculer la distance est un peu plus que la distance de Levenstein (détection de transpositions n'est pas facile). La plupart des communes des implémentations sont une modification de la bitap algorithme (comme grep).

En général, vous devriez probablement envisager une mise en œuvre de la troisième option, mis en œuvre dans une sorte de plus proche voisin de recherche basé sur un k-d tree

Answer 2

la distance Damerau-Levenshtein est similaire à la distance Levenshtein, mais inclut également la transposition à deux caractères. la page wikipedia (liée) inclut un pseudocode qui devrait être assez banal à mettre en œuvre.

Answer 3

• Distance Levenstein
• Distance de Hamming
• soundex
• métaphone

Answer 4

Vous recherchez la distance Levenshtein