El primer intento fue hacer que uno de los dos strings fuera por lo menos la mitad del largo del otro y que estuviera contenido. Como aproximación está bien, pero si por ejemplo uno de los dos tiene un tilde y el otro no, da que son diferentes.
Gracias a Matías me enteré que existe un algoritmo, llamado Distancia de Levenshtein, que se usa justamente para esto. Según Wikipedia:
En Teoría de la información y Ciencias de la Computación se llama Distancia de Levenshtein, distancia de edición, o distancia entre palabras, al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupara de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.Dejo acá el algoritmo en GeneXus, por si a alguien más le resulta útil:
/*
* Distancia de Levenshtein
*
* Fuente: http://es.wikipedia.org/wiki/Distancia_de_Levenshtein
*
* parm(in:&str1, in:&str2, out:&distance);
*
* Todas las variables son N(4) salvo &str1 y &str2 que son C(100)
*/
&lenStr1 = &str1.Length()
if &lenStr1 > 99
&lenStr1 = 99
endif
&lenStr2 = &str2.Length()
if &lenStr2 > 99
&lenStr2 = 99
endif
for &i = 1 to &lenStr1+1
&distMatrix(&i, 1) = &i-1
endfor
for &j = 1 to &lenStr2+1
&distMatrix(1, &j) = &j-1
endfor
for &i = 2 to &lenStr1+1
for &j = 2 to &lenStr2+1
if &str1.Substring(&i, 1) = &str2.Substring(&j, 1)
&costo = 0
else
&costo = 1
endif
&val1 = &distMatrix(&i-1, &j)+1 // deletion
&val2 = &distMatrix(&i, &j-1)+1 // insertion
&val3 = &distMatrix(&i-1, &j-1) + &costo // substitution
&min = &val1
if &val2 < &min
&min = &val2
endif
if &val3 < &min
&min = &val3
endif
&distMatrix(&i, &j) = &min
endfor
endfor
&distance = &distMatrix(&lenStr1+1, &lenStr2+1)
Deja un ej. de comparacion para que quede mas grafico, como seria?
ResponderEliminarPor ejemplo, si comparo "aproximacion" con "aproximación" la diferencia es 1. Si comparo "Aproximacion" con "aproximación" la diferencia es 2.
EliminarLa idea es que el número que devuelve es la cantidad de operaciones que tenés que realizar para transformar de uno en otro.
Excelente!!! parabens
ResponderEliminarEsto me acuerdo que en un sistema en el que trabaje lo usaban para buscar nombres parecidos a la lista de requeridos por Interpol. :)
ResponderEliminarDespués contá que vas a hacer con eso.
Abrazo
Muy buena información, gracias Marcos! En mi tesis de la licenciatura, uno de los puntos que quedaron a futuro fue la comparación de nombres de métodos y/o argumentos en un contexto de testing de componentes. (largo de explicar).
ResponderEliminarVoy a proponerselo al siguiente estudiante que esté con ésta rama.
Hola Marcos,
ResponderEliminarGracias por el aporte, estoy viendo de utilizarlo, pero me parece que el segundo "for" tiene un error, utiliza la &i en vez de la &j.
Saludos
Pablo:
EliminarSí parece que tenés razón... Viendo las implementaciones que hay en Wikipedia lo correcto es usar &j como decías.
Lo corrijo, gracias.