En 4D distance de Levenshtein par lettre ou mots entiers

Bonjour,

j’ai eut du mal a faire fonctionner des plugin existant, alors j’ai refait une méthode selon l’algorithme classique “distance de Levenshtein” qui calcule la “distance” (comparaison) de 2 chaines de caractères .
Je l’ai aussi adapté a comparer des mots au lieu de caractères pour des besoins de comparaisons spécifiques (comparaison de coordonnées par exemple) :

exemples,

COMPARAISON DE CARACTERES (Levensthein classique) :

$chaine1:=“paul durand va a la montagne”
$chaine2:=“durand paul va a la mer”

$Distance_lettres:=Distance_levenshtein ($chaine1;$chaine2) // =16

COMPARAISON DE MOTS (Levensthein modifé) => plus rapide :

A) Avec ou sans dédoublonnage
B) Avec ou sans tris des mots

exemple ;

$chaine1:=“paul durand 2 ter av du gen de Gaulle 75020 Paris”
$chaine2:=“Durand Paul 2 avenue du général de Gaulle 75020 Paris”

$Distance_mots_non_trie:=Distance_mots_dans_phrase ($chaine1;$chaine2;1;0) // = 5

$Distance_mots_tries:=Distance_mots_dans_phrase ($chaine1;$chaine2;1;1) // = 3

Le 3ème paramètre effectue ou non un dedoublonnement des mots des 2 chaines // 0=non 1=dédoubloné
Le 4ème paramètre est pour le tri du tableau des mots // 0=pas de tris 1=mots tries

Les méthodes 4DC et base sources sont jointes. J’ai testé sur des millions de fiches, normalement je n’ai pas fait de bêtises …

J’espère que c’est utile pour certains ? ^^

Bases sources V16 et V17 + compilé + components a intégrer
http://forums.4d.com/4DBB_Main/x_User/5117062/files/26923095.zip

Les méthodes aussi en clair ici :

Méthode “Distance_levenshtein” ;
<code 4D>
// Retourne un entier dans $0
C_TEXTE($1;$2;$chaine1;$chaine2)
C_ENTIER LONG($l_STR1;$l_STR2;$i;$j;$t1;$0)
$chaine1:=$1
$chaine2:=$2

$l_STR1:=Longueur($chaine1)
$l_STR2:=Longueur($chaine2)

TABLEAU ENTIER LONG($MATRICE;$l_STR1;$l_STR2)
TABLEAU ENTIER LONG($VALEURS;3)

Boucle ($i;1;$l_STR1)
$MATRICE{$i}{0}:=$i
Fin de boucle

Boucle ($i;1;$l_STR2)
$MATRICE{0}{$i}:=$i
Fin de boucle

Boucle ($i;1;$l_STR1)
Boucle ($j;1;$l_STR2)
$valmin:=$MATRICE{$i-1}{$j-1}

	Si ($MATRICE{$i-1}{$j}<$valmin)
		$valmin:=$MATRICE{$i-1}{$j}
	Fin de si 
	
	
	Si ($MATRICE{$i}{$j-1}<$valmin)
		$valmin:=$MATRICE{$i}{$j-1}
	Fin de si 
	
	
	Si ($chaine1[$i]=$chaine2[$j])
		$MATRICE{$i}{$j}:=$valmin
	Sinon 
		$MATRICE{$i}{$j}:=$valmin+1
	Fin de si 
Fin de boucle 

Fin de boucle
$0:=$MATRICE{$l_STR1}{$l_STR2}

</code 4D>

Méthode “Distance_mots_dans_phrase”
<code 4D>
//$1 = chaine A
//$2 = chaine B
//$3 = entier long 0 ou 1 => 1 = mots unique dedoublonés
//$4 = entier long 0 ou 1 => 1 = tris sur mots
// Retourne un entier dans $0

C_TEXTE($1;$2;$chaine1;$chaine2)
C_ENTIER LONG($l_STR1;$l_STR2;$i;$j;$t1;$0;$3;$4)
$chaine1:=$1
$chaine2:=$2

TABLEAU TEXTE($group_mots1;0)
TABLEAU TEXTE($group_mots2;0)
Si ($3=0) // mots en double
LIRE MOTS CLÉS TEXTE($1;$group_mots1)
LIRE MOTS CLÉS TEXTE($2;$group_mots2)
Sinon
LIRE MOTS CLÉS TEXTE($1;$group_mots1;)
LIRE MOTS CLÉS TEXTE($2;$group_mots2;
)
Fin de si
Si ($4=1) // 1 = tris sur mots
TRIER TABLEAU($group_mots1;<)
TRIER TABLEAU($group_mots2;<)
Fin de si

$l_STR1:=Taille tableau($group_mots1)
$l_STR2:=Taille tableau($group_mots2)

TABLEAU ENTIER LONG($MATRICE;$l_STR1;$l_STR2)

Boucle ($i;1;$l_STR1)
$MATRICE{$i}{0}:=$i
Fin de boucle

Boucle ($i;1;$l_STR2)
$MATRICE{0}{$i}:=$i
Fin de boucle

Boucle ($i;1;$l_STR1)
Boucle ($j;1;$l_STR2)
$valmin:=$MATRICE{$i-1}{$j-1}

	Si ($MATRICE{$i-1}{$j}<$valmin)
		$valmin:=$MATRICE{$i-1}{$j}
	Fin de si 
	
	
	Si ($MATRICE{$i}{$j-1}<$valmin)
		$valmin:=$MATRICE{$i}{$j-1}
	Fin de si 
	
	
	Si ($group_mots1{$i}=$group_mots2{$j})
		$MATRICE{$i}{$j}:=$valmin
	Sinon 
		$MATRICE{$i}{$j}:=$valmin+1
	Fin de si 
Fin de boucle 

Fin de boucle
$0:=$MATRICE{$l_STR1}{$l_STR2}

</code 4D>

Méthode pour tester : TEST_distance
<code 4D>
C_ENTIER LONG($t1;$t2;$t3;$t4;$Distance_lettres;$Distance_mots_non_trie;$Distance_mots_tries)
$chaine1:=“paul durand va a la montagne”
$chaine2:=“durand paul va a la mer”

$t1:=Nombre de millisecondes
$Distance_lettres:=Distance_levenshtein ($chaine1;$chaine2) // =9
$t1:=Nombre de millisecondes-$t1

$chaine1:=“paul durand 2 ter av du gen de Gaulle 75020 Paris”
$chaine2:=“durand paul 2 avenue du général de Gaulle 75020 Paris”

$t2:=Nombre de millisecondes
$Distance_mots_non_trie:=Distance_mots_dans_phrase ($chaine1;$chaine2;1;0) // = 2
$t2:=Nombre de millisecondes-$t2

$t3:=Nombre de millisecondes
$Distance_mots_tries:=Distance_mots_dans_phrase ($chaine1;$chaine2;1;1) // = 0
$t3:=Nombre de millisecondes-$t3

//$t4:=Nombre de millisecondes
//$Distance:=Levenshtein ($chaine1;$chaine2) // 4d-plugin-common-string-algorithm by Miyako
//$t4:=Nombre de millisecondes-$t4

ALERTE("Temps 4D : “+Chaîne($t1)+”\nTemps mots : “+Chaîne($t2)+”\nTemps mots triés : “+Chaîne($t3)+”\nTemps plugin : "+Chaîne($t4))

</code 4D>

ATTENTION, les méthodes ne sont pas sécurisées (contrôle du nombre de paramètres, chaine vide, longueur excessive pour la comparaison de lettres etc …)

Evidement, j’ai oublié de compiler une méthode dans le composant, les voici recompilés (v16 v17)
http://forums.4d.com/4DBB_Main/x_User/5117062/files/26932809.zip