La distance levenshtein vs les fautes de frappe

Commenter

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

S'inscrire maintenant

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.

Du même auteur (cs_Melnofil)