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