Distance de jaro-winkler

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 537 fois - Téléchargée 19 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 normalement comprise entre 0 et 1 mais peut dépasser légèrement 1 dans le cas ou le paramètre p est modifié.
(p est un coefficient qui permet de favoriser les chaînes avec un préfixe commun. Winkler propose pour valeur p = 0.1)

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

Source / Exemple :


function JaroWinkler(prmT1, prmT2: String;p:Double=0.1): Double;
Var
ecartMax,l1,l2,compteMatching,compteTransposition,longueurPrefix,i,j:integer;
c1,c2,t1Matche,t2Matche:string;
b1,b2:array of Boolean;
distanceJaro:Double;
label endfor,exitfor2;
  function  TrouverMatches(prmTextInitial:string;b1:array of Boolean):string;
  var
  i:integer;
  res:string;
  begin
  // Calcule le nombre de caractères qui match
    for i := 1 to Length(prmTextInitial) do
    begin
      if b1[i] then//prmTextMatche[i]='_' then
      begin
        res:=res+prmTextInitial[i];
      end;
    end;
  TrouverMatches:=res;
  end;
begin
 ecartMax:=round(Max(Length(prmT1), Length(prmT2))/2)-1;
 if ((prmT1='') or (prmT2='')) then
 begin
  JaroWinkler:=0;
  exit;
 end;
 compteMatching:=0;
 compteTransposition:=0;
 l1:=Length(prmT1);
 l2:=Length(prmT2);
 Setlength(b1,l1+1);
 Setlength(b2,l2+1);
 for i := 0 to l1 do
 begin
  b1[i]:=false;
 end;
 for i := 0 to l2 do
 begin
  b2[i]:=false;
 end;

 for i := 1 to l1 do
 begin
  c1:=prmT1[i];
  if (i<=l2) then
    c2:=prmT2[i]
  else
    c2:='';
  for j := Max(i-ecartMax,1) to Min(i+ecartMax,l2) do
  begin
    c2:=prmT2[j];
    if c1=c2 then //compteMatching avec transposition
    begin
     b1[i]:=true;
     b2[j]:=true;
     //Le caractère a été matché, il n'est plus disponible
     Inc(compteMatching);
     break;
    end;
  end;
 end;
 if (compteMatching=0) then
 begin
  JaroWinkler:=0;
  exit;
 end;
 //Dans les caractères matchés, compte ceux qui ne matchent pas exactement
 t1Matche:=TrouverMatches(prmT1,b1);
 t2Matche:=TrouverMatches(prmT2,b2);
 if t1Matche<>t2Matche then
 begin
  for i := 1 to length(t1Matche) do
  begin
    if t1Matche[i]<>t2Matche[i] then
      Inc(compteTransposition)
  end;
 end else begin
   compteTransposition:=0;
 end;

 distanceJaro:=1/3*((compteMatching/l1)+(compteMatching/l2)+((compteMatching-Int(compteTransposition/2))/compteMatching));

 //Calcule la distance Winkler
 //Calcule le prefix sur les 4 premiers car aux max
 longueurPrefix:=0;
 for i := 1 to min(4,min(l1,l2)) do
 begin
  c1:=prmT1[i];
  c2:=prmT2[i];
  if c1=c2 then
    inc(longueurPrefix)
  else
  break;
 end;
 //Valeur constante définie par l'algo
 JaroWinkler:=distanceJaro+(longueurPrefix*p*(1-distanceJaro));
end;

Conclusion :


cette source est juste un portage delphi d'une source vb trouvée sur le net.

A voir également

Ajouter un commentaire

Commentaires

Messages postés
237
Date d'inscription
mardi 13 novembre 2007
Statut
Membre
Dernière intervention
21 novembre 2013

Je me demande ce que cela donnerait en utilisant un algorythme de comparaison de bitmap !

Tu dessines la chaine sur un canvas, et tu fais la difference avec un bitma p rempli selon un pourcentage ....???
Messages postés
51
Date d'inscription
mercredi 11 mai 2005
Statut
Membre
Dernière intervention
8 avril 2009

Ben pour les accents l'algo considère pareil une lettre accentuée qu'une autre lettre.
Pour y remédier on pourrais y incorporer juste avant un algo qui supprime les accents avant comparaison par exemple.

Et au faite pour Loda, si tu veux utiliser cet algo dans ton aglomérateur de news, ne te sert pas du côté Winkler (car sa compte plus le préfixe)
Utilise juste la distance de Jaro.
Messages postés
814
Date d'inscription
vendredi 3 novembre 2000
Statut
Membre
Dernière intervention
30 juillet 2009
3
merci pour la comparaison. Cela éclaire bien ma lanterne....

a+
Messages postés
237
Date d'inscription
mardi 13 novembre 2007
Statut
Membre
Dernière intervention
21 novembre 2013

En fait, comparé à SoundEx, il paraît plus international ton algo !

Les accents, tu gais comment ?

Pour SoundEx, il y a une correspondance spéciale...

http://fr.wikipedia.org/wiki/Soundex
Messages postés
51
Date d'inscription
mercredi 11 mai 2005
Statut
Membre
Dernière intervention
8 avril 2009

Alors si on prend pour
A : la distance de Levenstein / Longeur max des 2 mots
B : la distance de Jaro
C : la distance de Jaro-Winkler
cela donne le tableau suivant :

Robert - Rupert
A=66.67%
B=77.78%
C=80%

Robert - Rubin
A=33.33%
B=57.78%
C=62%

Rupert - Rubin
A=33.33%
B=57.78%
C=66.22%

on constate que Robert ressemble plus à Rupert que Rubin (via tout les algos)
après on peut même dire via Jaro-Winkler que Rubin ressemble plus à Rupert qu'à Robert
mais sa c'est surtout parce que Winkler à rajouté le fait que le préfixe est plus important.
Afficher les 13 commentaires

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.