Comparaison "intelligente" et moteur de recherche

Télécharger le projet
Commenter

Description

Dans ce source vous trouverez l'unité SmartCompare. Elle définit la fonction

function SmartDist(s1,s2:string):Double;overload;

Cette fonction retourne un nombre inférieur ou égal à 1 (lorsque les 2 chaînes sont égales) calculant la distance entre les 2 chaînes de caractères s1 et s2. La comparaison est "intelligente" en ce sens qu'elle calcule le nombre de tronçons maximaux que les 2 chaînes ont en commun, et introduit une pénalité dépendant du nombre de tronçons et de leur écartement. L'utilité de tout ça est qu'on peut s'en servir pour définir un moteur de recherche pouvant trouver des termes ayant une orthographe très proche (voir l'exemple). Plus le résultat est proche de 1, plus les 2 chaînes sont proches.

La fonction est définie mathématiquement par récurrence, mais je l'ai optimisée pour que ça aille très vite.

Source / Exemple : 


unit SmartCompare;

interface

type
  TEqualityFunc=function(const x,y:Integer):Boolean;

function SmartDist(f:TEqualityFunc;n1,n2:Integer):Double;overload;
function SmartDist(s1,s2:string):Double;overload;

implementation

function Max3(a,b,c:Integer):Integer;
begin
  if a>b then begin
    if a>c then
      Result:=a
    else
      Result:=c;
  end else begin
    if b>c then
      Result:=b
    else
      Result:=c;
  end;
end;

function SmartDist(f:TEqualityFunc;n1,n2:Integer):Double;
var
  i,j,a,b,c:Integer;
  T:array[0..1] of PIntegerArray;
  u:Boolean;
begin
  GetMem(T[0],(n1+1)*(n2+1)*SizeOf(Integer));
  GetMem(T[1],(n1+1)*(n2+1)*SizeOf(Integer));
  for i:=0 to n1 do begin
    T[0,i]:=0;
    T[1,i]:=-1;
  end;
  for j:=0 to n2 do begin
    T[0,j*(n1+1)]:=0;
    T[1,j*(n1+1)]:=-1;
  end;
  T[1,0]:=0;
  for i:=1 to n1 do
    for j:=1 to n2 do begin
      u:=f(i-1,j-1);
      if u then
        a:=2+T[1,i-1+(j-1)*(n1+1)]
      else
        a:=T[0,i-1+(j-1)*(n1+1)];
      b:=T[0,i+(j-1)*(n1+1)];
      c:=T[0,i-1+j*(n1+1)];
      T[0,i+j*(n1+1)]:=Max3(a,b,c);
      if u then
        a:=2+T[1,i-1+(j-1)*(n1+1)]
      else
        a:=T[0,i-1+(j-1)*(n1+1)]-1;
      b:=T[0,i+(j-1)*(n1+1)]-1;
      c:=T[0,i-1+j*(n1+1)]-1;
      T[1,i+j*(n1+1)]:=Max3(a,b,c);
    end;
  Result:=(n1+n2-T[1,n1+n2*(n1+1)])/(n1+n2);
  FreeMem(T[0]);
  FreeMem(T[1]);
end;

var
  GS1,GS2:string;

function CompareStr(const x,y:Integer):Boolean;
begin
  Result:=GS1[x+1]=GS2[y+1];
end;

function SmartDist(s1,s2:string):Double;overload;
begin
  GS1:=s1;
  GS2:=s2;
  Result:=SmartDist(CompareStr,Length(s1),Length(s2));
  GS1:='';  // Decrement reference count 
  GS2:='';
end;

end.

Conclusion :


A noter: il existe une fonction overloadée du même nom qui travaille sur une fonction de comparaison quelconque (de cette façon-là, il est donc possible de travailler dur des données qui n'ont rien à voir avec des chaînes de caractères).

Ah oui une dernière chose: le texte utilisé dans l'exemple est tiré de Lovecraft (pas de copyright, donc :-)
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_Forman)