LA DISTANCE LEVENSHTEIN VS LES FAUTES DE FRAPPE

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
}

24 novembre 2004 17:21:23 :

24 novembre 2004 17:25:03 :

24 novembre 2004 17:28:49 :