Distance de Damerau-Levenshtein
Ryuku
Messages postés
126
Statut
Membre
-
Unicornator -
Unicornator -
Bonjour,
Salut à tous,
J'ai lu et j'ai un qui permet de mesurer la distance entre les chaînes de caractères qu'on appelle la distance de Levenstein qui compte le nombre minimum d'opérations d'édition à effectuer pour transformer une chaîne de caractères à une autre (suppression, insertion et substitution) et une modification de celle ci : la distance Damerau-Levenshtein qui ajoute l'opération de permutation.
Maintenant si on remplace les chaînes de caractères source et destination par des tableaux Src et Dest tels que :
Dest est construit à partir de Src en permutant les éléments de ce dernier.
Peut-on connaitre le nombre de permutations minimal qui permet de transformer Src en Dest et ces permutations elles mêmes avec la distance de Damerau-Levenshtein ?
Merci.
Salut à tous,
J'ai lu et j'ai un qui permet de mesurer la distance entre les chaînes de caractères qu'on appelle la distance de Levenstein qui compte le nombre minimum d'opérations d'édition à effectuer pour transformer une chaîne de caractères à une autre (suppression, insertion et substitution) et une modification de celle ci : la distance Damerau-Levenshtein qui ajoute l'opération de permutation.
Maintenant si on remplace les chaînes de caractères source et destination par des tableaux Src et Dest tels que :
Dest est construit à partir de Src en permutant les éléments de ce dernier.
Peut-on connaitre le nombre de permutations minimal qui permet de transformer Src en Dest et ces permutations elles mêmes avec la distance de Damerau-Levenshtein ?
Merci.
2 réponses
Mais il n'y a pas de différence entre un tableau et une chaîne de caractères !
En effet, considérons le tableau suivant:
Bonne continuation.
En effet, considérons le tableau suivant:
a00 a01 a02 a10 a11 a12 a20 a21 a22comme la chaîne:
a00a01a02a10a11a12a20a21a22aAors le calcul de la distance de Levenshtein est connu.
Bonne continuation.
Bonjour Ryuku, je cherche quelque chose comme toi également. Il est difficile d'avoir la vraie distance Damerau-Levenshtein car on doit comprendre toute les possibilités de transpositions possibles pour chaque doublons de caractères des deux mots. J'ai toutefois réussi avec la méthode des tableaux à avoir une condition permettant d'avoir les transpositions de deux lettres adjacentes. Voilà ce que j'ai jusqu'à maintenant. Je me fis au site mentionné ci-haut:
http://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
Pour calculer la distance Damerau-Levenshtein, j'ai utilisé un tableau de (longueur premier mot+1 par longueur deuxieme mot+1) ou la premiere ligne et la premiere colonne sont simplement une suite de 0 à longueur mot prenons en exemple allo et holla:
__a l l o
__0 1 2 3 4
h_1
o_2
l_3
l_4
a_5
**Désolé pour les barre "_" c'est la seule manière que j'ai trouver de bien faire le tableaux en chaine de caractères.. ^_^' **
Ensuite, selon Levenshtein, tu calcules le cout en observant les 2 lettres, si elles sont pareil le cout est de 0 et sinon de 1. Ensuite à la case (2,2) tu prends le minimum entre le chiffre une case en haut +1, le chiffre à gauche plus 1 et le chiffre en haut à gauche (diagonale) + cout.
Jusqu'à maintenant je te montre ce qu'est la distance Levenshtein.
Mon autre condition est d'observer si la lettre précédente du mot1 = lettre du mot2 ET la lettre précédente du mot2 = lettre du mot1 (par exemple, AR et RA respecterais la condition). Si la condition est bonne tu peux prendre la deuxième case en diagonale gauche + cout. Voilà un exemple pour clarifier
_____A B
___0 1 2
B__1 1 1
A__2 1 X
Si tu prends Levenshtein, X te donne 2. Toutefois, avec la nouvelle condition qui est valide (ce qui nous permet d'observer la deuxième case en diagonale gauche), je peux prendre la case 0 + cout (1 dans notre cas) ce qui donne 1. Ainsi, la distance serait de 1 au lieu de 2.
En espérant que sa puisse t'aider!
http://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
Pour calculer la distance Damerau-Levenshtein, j'ai utilisé un tableau de (longueur premier mot+1 par longueur deuxieme mot+1) ou la premiere ligne et la premiere colonne sont simplement une suite de 0 à longueur mot prenons en exemple allo et holla:
__a l l o
__0 1 2 3 4
h_1
o_2
l_3
l_4
a_5
**Désolé pour les barre "_" c'est la seule manière que j'ai trouver de bien faire le tableaux en chaine de caractères.. ^_^' **
Ensuite, selon Levenshtein, tu calcules le cout en observant les 2 lettres, si elles sont pareil le cout est de 0 et sinon de 1. Ensuite à la case (2,2) tu prends le minimum entre le chiffre une case en haut +1, le chiffre à gauche plus 1 et le chiffre en haut à gauche (diagonale) + cout.
Jusqu'à maintenant je te montre ce qu'est la distance Levenshtein.
Mon autre condition est d'observer si la lettre précédente du mot1 = lettre du mot2 ET la lettre précédente du mot2 = lettre du mot1 (par exemple, AR et RA respecterais la condition). Si la condition est bonne tu peux prendre la deuxième case en diagonale gauche + cout. Voilà un exemple pour clarifier
_____A B
___0 1 2
B__1 1 1
A__2 1 X
Si tu prends Levenshtein, X te donne 2. Toutefois, avec la nouvelle condition qui est valide (ce qui nous permet d'observer la deuxième case en diagonale gauche), je peux prendre la case 0 + cout (1 dans notre cas) ce qui donne 1. Ainsi, la distance serait de 1 au lieu de 2.
En espérant que sa puisse t'aider!
Je sais que les chaînes de caractères sont des tableaux, moi je veux utiliser la distance de Damerau-Levenshtein (pas Levenshtein seule car la distance Damerau-Levenshtein compte les permutations) pour trouver le nombre minimal de permutations entre deux tableaux et ces permutations elles mêmes.
https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
Bon courage.