Levenshtein distance

La Levenshtein distance est un classique de la programmation. Elle est utile pour comparer la similarité de deux chaines de caractères.  Son défaut majeur est le temps de calcul (deux boucles imbriquées).

Le code source:  levenshtein_distance

/*------------- functions ------------*/
void errmalloc(char *msg) {
  printf("\nError memory allocation - %s\n",msg);
  exit(EXIT_FAILURE);

int minimum(int a,int b,int c) {
/*Gets the minimum of three values*/
  int min=a;
  if(b<min) min=b;
  if(c<min) min=c;
  return min;
}

int levenshtein_distance(char *s,char *t) {
/*Compute levenshtein distance between s and t*/
  int k,i,j,n,m,cost,*d,distance;
  n=strlen(s);
  m=strlen(t);
  if ((n!=0) && (m!=0))
  {
    if ((d=malloc((sizeof(int))*(m+1)*(n+1))) == NULL) errmalloc("levenshtein");
    m++;
    n++;
    for(k=0;k<n;k++) d[k]=k;
    for(k=0;k<m;k++) d[k*n]=k;
    for(i=1;i<n;i++)
      for(j=1;j<m;j++) {
        if(s[i-1]==t[j-1]) cost=0;
        else cost=1;
        d[j*n+i]=minimum(d[(j-1)*n+i]+1,d[j*n+i-1]+1,d[(j-1)*n+i-1]+cost);
      }
    distance=d[n*m-1];
    free(d);
    return distance;
  }
  else return -1; //string empty.
}

/* Compute the Levenshtein distance between 2 strings
Usage:  distance=levenshtein_distance(string1,string2);
*/