Diferencia entre revisiones de «Distancia de Levenshtein»
Contenido eliminado Contenido añadido
Sin resumen de edición |
|||
Línea 39:
==Implementación==
A continuación se puede ver la implementación de la función para varios lenguajes de programación. Otros lenguajes de más alto nível, como [[php]] o la funciones de usuario de [[MySQL]], las incorporan ya, sin necesidad de implementarla para ser usada.
===C===
int Levenshtein(char *s1,char *s2)
{ int t1,t2,i,j,*m,costo,res,ancho;
// Calcula tamanios strings
t1=strlen(s1); t2=strlen(s2);
// Verifica que exista algo que comparar
if (t1==0) return(t2);
if (t2==0) return(t1);
ancho=t1+1;
// Reserva matriz con malloc m[i,j] = m[j*ancho+i] !!
m=(int*)malloc(sizeof(int)*(t1+1)*(t2+1));
if (m==NULL) return(-1); // ERROR!!
// Rellena primera fila y primera columna
for (i=0;i<=t1;i++) m[i]=i;
for (j=0;j<=t2;j++) m[j*ancho]=j;
// Recorremos resto de la matriz llenando pesos
for (i=1;i<=t1;i++) for (j=1;j<=t2;j++)
{ if (s1[i-1]==s2[j-1]) costo=0; else costo=1;
m[j*ancho+i]=Minimo(Minimo(m[j*ancho+i-1]+1, // Eliminacion
m[(j-1)*ancho+i]+1), // Insercion
m[(j-1)*ancho+i-1]+costo); } // Sustitucion
// Devolvemos esquina final de la matriz
res=m[t2*ancho+t1];
free(m);
return(res);
}
===C++===
| |||