La distance levenshtein vs les fautes de frappe

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 710 fois - Téléchargée 33 fois

Contenu du snippet

La distance Levenshtein kesako ?
Du nom de son inventeur cette fonction permet de savoir précisément le nombre de remplacements/suppressions/ajouts de lettres qu'il faut effectuer dans un mot pour arriver a un autre mot. (La fonction fonctionne aussi très bien sur des phrases)

Par exemple pour passer de "CHIEN" à "NICHE" il en faut 4.
CHIEN
CHEN
CHE
ICHE
NICHE
(il y a peut-être une autre façon de faire, mais vous n'arriverez pas à moins de 4)

Note : Cette fonction utilise la fonction mathématique $min qui n'existe pas dans mIRC 6.16, vous pouvez utiliser la fonction que je vous donne ici (qui ne marche qu'avec 2 paramêtres) ou utiliser une fonction plus compliquée.

A quoi ca sert ?
C'est simple, voici exemple d'utilisation :
on *:text:!*:#MonCanal:{
; Premier cas : Le mot est trop court pour que $levenshtein soit utilisé.
if ($1 == !re) /rebonjour $nick
; Deuxième cas : Pour un mot de taille moyenne une distance de 1 est appropriée.
if ($levenshtein($1,!salut) < 2) /salut $nick
; Troisième cas : Pour un mot long on pourra utiliser une distance plus importante.
if ($levenshtein($1,!rebonjour) < 3) /rebonjour $nick
}

Ici la fonction "/salut" se déclanche si quelqu'un tape "!salu", "!zalut" ou "!saluut". De même la fonction "/rebonjour" se déclanche si quelqu'un tape "!rebonjr", "!rbonjur" ou ... "!bonjour" AïE !!! C'est le problème avec les distances trops importantes, il faudra traiter ce cas séparément.

Source / Exemple :


alias -l min return $iif($1 < $2,$1,$2)
alias levenshtein { ; <texte 1> <texte 2> -> <distance>
  var %a $len($1), %b $len($2)
  if (%a == 0) return %b
  if (%b == 0) return %a
  var %i %a | while %i > 0 { var % $+ m $+ %i $+ x0 %i | dec %i }
  var %j %b | while %j >= 0 { var % $+ m0x $+ %j %j | dec %j }
  while %i < %a {
    inc %i
    var %j 1
    while %j <= %b {
      var %cout $iif($mid($1, $+ %i $+ ,1) == $mid($2, $+ %j $+ ,1),0,1)
      var %tmp $calc($min($eval($+(%,m,$calc(%i - 1),x, $+ %j),2),$eval($+(%,m, $+ %i $+ ,x,$calc(%j - 1)),2)) + 1)
      var %m $+ %i $+ x $+ %j $min(%tmp $+ ,$calc($eval($+(%,m,$calc(%i - 1),x,$calc(%j - 1)),2) + %cout))
      inc %j
    }
  }
  return $eval(% $+ m $+ %a $+ x $+ %b $+ ,2)
}

; NE COPIEZ PAS CE QUI SUIT DANS VOS SCRIPTS
; Il s'agit du même code mais commenté, pour ceux qui veulent comprendre.

alias levenshtein { ; <texte 1> <texte 2> -> <distance>
	var %a $len($1), %b $len($2)
	if (%a == 0) return %b
	; Si %a =0, il faut ajouter %b caractères à $1 pour arriver à $2, donc on revoit %b
	if (%b == 0) return %a
	; Si %b =0, il faut enlever %a caractères à $1 pour arriver à $2, donc on revoit %a

	; M est un tableau en 2 dimensions de taille (%a+1) * (%b+1)
	; Sa première dimension (i) va de 0 à %a et la seconde (j) de 0 à b
	var %i %a | while %i > 0 { var % $+ m $+ %i $+ x0 %i | dec %i }
	; Pour %i allant de %a à 1 on initialise M[%i][0] = %i
	; Ca revient à initialiser la première ligne du tableau à la valeur de son abscisse : 1, 2, 3 ... %a
	var %j %b | while %j >= 0 { var % $+ m0x $+ %j %j | dec %j }
	; Pour %j allant de %b à 0 on initialise M[0][%j] = %j
	; On initialise la première colone à la valeur de son ordonnée (de 0 à %b)
	; Cette fois-ci on s'arrête à 0 pour ne pas oublier la case a l'intersection de la ligne et la colone.

	; Notez qu'ici %i vaut 0
	while %i < %a {
		inc %i
		; Donc ici %i a une valeur qui varie de 1 jusqu'a %a
		var %j 1
		while %j <= %b {
			var %cout $iif($mid($1, $+ %i $+ ,1) == $mid($2, $+ %j $+ ,1),0,1)
			; Le cout est très important puisqu'il s'agit de savoir si on peut garder la lettre actuelle.
			; En gros si la lettre est conservée y'a pas de coût, si la lettre est remplacée ca fait une "action" en plus.
			; Plus on est près de la diagonale centrale (%i == %j) plus on conserve les lettres à leur position d'origine.
			var %tmp $calc($min($eval($+(%,m,$calc(%i - 1),x, $+ %j),2),$eval($+(%,m, $+ %i $+ ,x,$calc(%j - 1)),2)) + 1)
			; %tmp = $min(M[%i - 1][%j], M[%i][%j - 1]) + 1
			; La valeur %tmp represente le cout minimun pour effectuer un décalage (soit une suppression ou ajout)
			var %m $+ %i $+ x $+ %j $min(%tmp $+ ,$calc($eval($+(%,m,$calc(%i - 1),x,$calc(%j - 1)),2) + %cout))
			; M[%i][%j] = $min(%tmp, M[%i - 1][%j - 1] + %cout)
			; On regarde s'il vaut utiliser %tmp (ajout/suppression) ou %cout (conserver la lettre/remplacement)
			inc %j
		}
	}
	return $eval(% $+ m $+ %a $+ x $+ %b $+ ,2)
	; La réponse est dans M[%a][%b] soit le coin en bas à droite du tableau
}

Conclusion :


Je met cette source dans "Débutant" car elle est extrèment facile à utiliser, et bien adaptée à la conception "amusante" du script sous mIRC. Il est difficile de croire pour un non-initié que vous êtes capables de gérer TOUTES les fautes uniques possibles aussi facilement donc la personne croit automatiquement que vous êtes très fort ;)
De plus ce script est une simple traduction bête et méchante de l'algorithme, il n'y a aucunes volonté ici de faire la preuve mathématique de celui-ci (non.. je n'ai pas dis que je ne pouvais pas, j'ai dis "voulais" XDDD).

Ca n'a rien à voir avec le but de ce code mais vous remarquerez que cette fonction contient un exemple de tableau (ou matrice) alors que mIRC ne gère pas du tout ce type de structure de donnée -en théorie du moins-.

Note de fin :
Cette fonction ne permet pas de comprendre les orthographes massacrées ... Pour ca il faudra diriger vos pas vers une fonction type soundex (utilisez google) ; mais autant vous prévenir tout de suite : En général ces fonctions sont prévues pour l'anglais.
Grâce à google je suis tombé immédiatement sur une page présentant un algorithme (pour le français) assez simulaire appelé "phonex". Je l'ai transcrise en mIRC Script, il m'a fallu environ 3~6 secondes de test pour me rendre compte des énormes lacunes de cette fonction, pourtant l'auteur précise bien que son code est plus efficace que soundex v1 et v2. A mon avis cela est principalement dût au fait qu'il à testé la validité de son code sur des noms propres au lieu de le tester sur des pages de dictionnaire.

Melnofil

A voir également

Ajouter un commentaire Commentaires
Messages postés
1052
Date d'inscription
samedi 10 juillet 2004
Statut
Membre
Dernière intervention
30 novembre 2009
2
c'est déja plus compréhensible :)
Messages postés
71
Date d'inscription
dimanche 23 juin 2002
Statut
Membre
Dernière intervention
1 février 2008

lol on s'est croisé KiNdErMaXi ^^

J'ai bien suivis tes conseils et mis une version commentée. Ceci dis à mon avis, il est + simple de chercher "Levenshtein" sur google, j'ai d'ailleurs utilisé cette technique pour faire cette source.

Pour la petite histoire c'est MagicalTux (certains d'entre vous le connaissent peut-être) qui m'a donné une référence en PHP sur cette fonction pour un projet (deux en faite : le sien et le mien XD ). En lisant la description j'ai trouvé génial et j'ai eu envis de voir si on pouvait refaire l'algo en Script mIRC. Et voilà le travail ;)
Messages postés
71
Date d'inscription
dimanche 23 juin 2002
Statut
Membre
Dernière intervention
1 février 2008

Elsay : A part la variable %tmp toutes ces variables sont définie dans l'énoncé de l'algorithme de M. Levenshtein, ce n'est pas moi qui les ai choisies (j'ai juste changé leurs noms).

%a et %b servent à ne pas avoir a calculer la longueur des chaines plusieurs fois.
%i et %j sont les compteurs essencielles pour parcourir un tableau.
%m(...) represente mon tableau.
%count n'est a prioris pas obligatoire mais l'algo en parle : il s'agit du coût pour conserver la lettre.

Donc si tu parle de %tmp effectivement on pourrait le virer bah pour ceux qui veulent absolument le faire utilisez $& à la place parsque sinon la ligne fait 3km c pas génial :/

En faite la le code est pas optimisé du tout comme je l'ai dis c'est une traduction bête et méchante de l'algorithme.
Messages postés
1052
Date d'inscription
samedi 10 juillet 2004
Statut
Membre
Dernière intervention
30 novembre 2009
2
c'est vrai, que de variable mais si ca vaut le coup ya pas de pb, c'est vrai qu'on y voit pas très clair dans ton code mais si tu te comprend :)
ce qui serai bien c'est que tu commente ton code ligne par ligne ;)
bonne continuation
Messages postés
11
Date d'inscription
vendredi 19 novembre 2004
Statut
Membre
Dernière intervention
24 novembre 2004

Que de variables ....
Afficher les 6 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.