| |
Voici une implémentation de la distance de Levenshtein pour calculer la similarité entre 2 chaînes. Ce code utilise cette classe crée par r0d pour simuler des tableaux 2D.
template < class T> int distanceLevenshtein (const T& s1,const T& s2)
{
const int N1= s1.size ();
const int N2= s2.size ();
if (N1= = 0 )
return N2;
if (N2= = 0 )
return N1;
int cout;
DynMatrix:: Dyn2DMatrix< int > mat (N1+ 1 ,N2+ 1 );
for (int i= 0 ;i<= N1;+ + i)
mat (i,0 )= i;
for (int i= 0 ;i<= N2;+ + i)
mat (0 ,i)= i;
for (int i= 1 ;i<= N1;+ + i)
{
for (int j= 1 ;j<= N2;+ + j)
{
cout= s1[i- 1 ]= = s2[j- 1 ] ? 0 : 1 ;
mat (i,j)= std:: min (std:: min (mat (i- 1 ,j)+ 1 ,mat (i,j- 1 )+ 1 ),mat (i- 1 ,j- 1 )+ cout);
}
}
return mat (N1,N2);
}
|
|
Consultez les autres pages sources


Les sources présentées sur cette page sont libres de droits
et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation
constitue une œuvre intellectuelle protégée par les droits d'auteur.
Copyright © 2004 Developpez Developpez LLC.
Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne
peut être faite de ce site ni de l'ensemble de son contenu : textes, documents
et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez
selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.