Distance de jaro-winkler

Soyez le premier à donner votre avis sur cette source.

Snippet vu 11 229 fois - Téléchargée 17 fois

Contenu du snippet

La distance de Jaro-Winkler mesure la similarité entre deux chaînes de caractères.

Cette fonction permet de renvoyer la valeur de la distance de Jaro-Winkler.
Elle est comprise entre 0 et 1 .

voir :
http://fr.wikipedia.org/wiki/Distance_de_Jaro-Winkler

Source / Exemple :


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define true 0
#define false 1
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

char *TrouverMatches(char * txt,int *bl)
{
	int i,j;
	char *res=malloc(256*sizeof(char));
	char ctmp='a';
	for (i=0;i<256;i++)
	{res[i]=0;}
	i=0,j=0;
	while (ctmp!=0)
	{
		ctmp=txt[i];
		if (bl[i]==true)
		{
			res[j]=ctmp;
			j++;
		}
		i++;
	}
	return res;
}

double JaroWinkler(char *t1,char *t2)
{
	int ecartMax,l1,l2,compteMatching,compteTransposition,longueurPrefix,i,j;
	char *t1Matche,*t2Matche;
	int *b1,*b2;
	double distanceJaro;
	if (t1[0]==0 || t2[0]==0)
		return 0.0;
	l1=strlen(t1);
	l2=strlen(t2);
	ecartMax=(max(l1,l2)/2)-1;
	compteMatching=0;
	b1=malloc((l1+2)*sizeof(int));
	b2=malloc((l2+2)*sizeof(int));
	for (i=0;i<l1;i++)
		b1[i]=false;
	for (i=0;i<l2;i++)
		b2[i]=false;

	for (i=0;i<l1;i++)
	{
		for (j=max(i-ecartMax,0);j<=min(i+ecartMax,l2);j++)
		{
			if (t1[i]==t2[j])
			{
				b1[i]=true; //Indique qu'on a bien trouvé ce caractère
				b2[j]=true;
				compteMatching++; //Incrémente le nombre de caractères correspondants
				break;
			}
			
		}
		
	}
	
	if (compteMatching==0)
		return 0.0;
		
	t1Matche=TrouverMatches(t1,b1); //Génére la liste des caractères communs dans l'ordre de t1
	t2Matche=TrouverMatches(t2,b2);
	
	compteTransposition=0;
	if (strcmp(t1Matche,t2Matche)!=0)
	{
		for (i=0;i<strlen(t1Matche);i++)
			if (t1Matche[i]!=t2Matche[i])
				compteTransposition++; //Calcul le nombre de transpositions
	}
	else
		compteTransposition=0;
	
	free(t1Matche);
	free(t2Matche);
	
	distanceJaro=(((double)compteMatching/l1)+((double)compteMatching/l2)+((compteMatching-compteTransposition/2.0)/compteMatching))/3.0;
	
	longueurPrefix=0;
	for (i=0;i<min(3,min(l1,l2))+1;i++) //longueur max : 4
	{
		if (t1[i]==t2[i])
			longueurPrefix++;
		else
			break;
		
	}
	return distanceJaro+(longueurPrefix*0.1*(1-distanceJaro));
}

int main ()
{
char *t1=malloc(256*sizeof(char));
char *t2=malloc(256*sizeof(char));
strcpy(t1,"MARTHA");
strcpy(t2,"MARHTA");
printf("distance %s %s : %f\n",t1,t2,JaroWinkler(t1,t2));
strcpy(t1,"DWAYNE");
strcpy(t2,"DUANE");
printf("distance %s %s : %f\n",t1,t2,JaroWinkler(t1,t2));
strcpy(t1,"DIXON");
strcpy(t2,"DICKSONX");
printf("distance %s %s : %f\n",t1,t2,JaroWinkler(t1,t2));

return 0;
}

A voir également

Ajouter un commentaire Commentaires
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
C'est bien maintenant. Merci pour les corrections et pour les remarques et variantes éventuelles qui peuvent effectivement être utilisées.
Messages postés
51
Date d'inscription
mercredi 11 mai 2005
Statut
Membre
Dernière intervention
8 avril 2009

nan pas d'erreur de compilation
y'avais une erreur de <= à corriger, décidément !
les mots de 1 caractères sont tout de même pas pris en compte (d'après le jaro winkler officiel)

Sinon tu peux jouer sur les paramètres de la boucle for (j...
par exemple de j=0;j<l2;j++
cela permettra de vérifier tout les caractères (et marchera pour les mots de 1 lettre)
mais c'est plus le Jaro-Winkler officiel.
A mon avis on pourrais mettre un plus grand écart de recherche (quand même pas de 0 à l2) cela permettrait de meilleurs résultats.
Il y a aussi l'importance que l'on accorde au préfixe, ici 0.1 qui peut être modifié, par contre ici je penses c'est une bonne valeur.

Je sais pas si tu connais des textes ou l'ordre des lettres est inversé, tant que la première et la dernière lettre sont corrects et que le mot reste un anagramme alors le cerveau arrive à le comprendre sans problème, en se basant sur ce principe (pour la correction orthographique) pourquoi ne pas accorder aussi une importance au suffixe ?
Je penses un préfix max de 4 lettres coeff 0.1 et suffixe max 2 lettres coeff 0.08 est un assez bon réglage.
Enfin sa peut faire l'objet d'une autre source (ou en complément de celle-ci) je vais voir.

Merci pour tes tests en tout cas !
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
Maintenant c'est beaucoup mieux. Les 3 exemples de Wikipedia sont bien évalués comme il faut. Mais si on ajoute le calcul de la distance entre "AAA" et "AAA" on trouve : 0 ! On s'attend à : 1, je crois. Est-ce ma compilation qui est en défaut ?
Messages postés
51
Date d'inscription
mercredi 11 mai 2005
Statut
Membre
Dernière intervention
8 avril 2009

oups désolé j'avais pas testé mon code !
J'ai corrigé aussi le calcul du nombre de transposition et libération de la mémoire quand on en a plus besoin.

Je n'avais pas mis d'include ni de main pour poster seulement un algorithme pas un programme !
j'ai tout de même rajouté un main de test de la fonction.
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
J'ai quelques soucis avec ce programme.
A la place de : if (&t1[i]==&t1[j])
j'aurais bien vu : if (t1[i]==t2[j])
De plus la ligne : distanceJaro=(double)...
comporte des divisions entières.
Mais 4/8 vaut 0 et non pas 0.5 !
Il manque les #include et un main.
Cela peut donc s'améliorer.

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.