C'est une implémentation en ASP de l'algorithme de Levenshtein
Il sert à calculer la proximité de deux chaînes de caractères.
‘ minimum entre a, b ou c
function min( a, b, c )
if a < b then
if ( c < a ) then
min = c
else
min = a
end if
else
if ( c < b ) then
min = c
else
min = b
end if
end if
end function
‘ d est un tableau à deux dimensions de ( taille( candidate ) , taille( ref ) ) : Pour faire simple on peut créer une matrice de borne max comme avec dim d( 100, 100 )
‘ candidate : La chaîne 1
‘ ref : La chaîne 2
‘ Cette fonction retourne la distance entre deux chaînes
function distanceDeLevenshtein( d, candidate, ref )
for i = 0 to len( candidate ) - 1
d( i, 0 ) = i
next
for i = 0 to len( ref ) - 1
d( 0, i ) = i
next
for i = 1 to len( candidate )
for j = 1 to len( ref )
if mid( candidate, i, 1 ) = mid( ref, j, 1 ) then
cout = 0
else
cout = 1
end if
ni = i
nj = j
d( ni, nj ) = min( d( ni - 1, nj ) + 1, d( ni, nj - 1 ) + 1, d( ni - 1, nj - 1 ) + cout )
next
next
distanceDeLevenshtein = d( len( candidate ) - 1, len( ref ) - 1 )
end function