#include "EXTERN.h" #include "perl.h" #include "XSUB.h" /****************************************************/ /* Levenshtein Distance Algorithm */ /* C Implementation by Lorenzo Seidenari */ /* http://www.merriampark.com/ldc.htm */ /* modified by dree */ /****************************************************/ #include <stdlib.h> #include <string.h> int levenshtein_distance(char *s,char*t); int minimum(int a,int b,int c); int levenshtein_distance(char *s,char*t) /*Compute levenshtein distance between s and t*/ { //Step 1 int k,i,j,n,m,cost,*d,distance; if (strcmp(s,t) == 0) {return 0;} n=strlen(s); m=strlen(t); if(n==0) {return m;} if(m==0) {return n;} d=malloc((sizeof(int))*(m+1)*(n+1)); m++; n++; //Step 2 for(k=0;k<n;k++) d[k]=k; for(k=0;k<m;k++) d[k*n]=k; //Step 3 and 4 for(i=1;i<n;i++) for(j=1;j<m;j++) { //Step 5 if(s[i-1]==t[j-1]) cost=0; else cost=1; //Step 6 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; } 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; } MODULE = Text::LevenshteinXS PACKAGE = Text::LevenshteinXS int distance(s,t) char * s char * t CODE: RETVAL = levenshtein_distance(s,t); OUTPUT: RETVAL