La distance de Leventshtein est un algorithme imaginé en 1965 par Vladimir Levenshtein qui permet de définir le nombre d’opérations minimum nécessaires pour transformer une chaine de caractères en une autre.  Et qui permet donc de calculer la différence entre deux chaines.

Utilisé en ActionScript notamment pour l’API de Mouse Gesture Recognition :

Je réfléchit en ce moment à l’utilisation de ce script pour un moteur d’apriori dans une intelligence artificielle :

Voici une implémentation ActionScript3.0 trouvée sur snipplr.com :

function levenshteinDistance(s1:String,s2:String):int
{
	var m:int = s1.length;
	var n:int = s2.length;
	var matrix:Array = new Array();
	var line:Array;
	var i:int;
	var j:int;
	for (i = 0; i <= m; i++)
	{
		line=new Array();
		for (j = 0; j <= n; j++)
		{
			if (i != 0) line.push(0)
			else line.push(j);
		}
		line[0] = i;
		matrix.push(line);
	}
	var cost:int;
	for (i = 1; i <= m; i++)
		for (j = 1; j <= n; j++)
		{
			if (s1.charAt(i - 1) == s2.charAt(j - 1)) cost = 0;
			else cost = 1;
			matrix[i][j] = Math.min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost);
		}
	return matrix[m][n];
}