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 :-)
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.