miércoles, 2 de mayo de 2012

Comparación de strings por aproximación

Para una aplicación que estoy haciendo con GeneXus (después cuento de que se trata...), necesitaba poder comparar dos strings, pero no necesito que sean exáctamente iguales, me alcanza con que sean aproximados.

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)

7 comentarios:

  1. Deja un ej. de comparacion para que quede mas grafico, como seria?

    ResponderEliminar
    Respuestas
    1. Por ejemplo, si comparo "aproximacion" con "aproximación" la diferencia es 1. Si comparo "Aproximacion" con "aproximación" la diferencia es 2.

      La idea es que el número que devuelve es la cantidad de operaciones que tenés que realizar para transformar de uno en otro.

      Eliminar
  2. Esto me acuerdo que en un sistema en el que trabaje lo usaban para buscar nombres parecidos a la lista de requeridos por Interpol. :)

    Después contá que vas a hacer con eso.

    Abrazo

    ResponderEliminar
  3. 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).

    Voy a proponerselo al siguiente estudiante que esté con ésta rama.

    ResponderEliminar
  4. Hola Marcos,
    Gracias 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

    ResponderEliminar
    Respuestas
    1. Pablo:

      Sí parece que tenés razón... Viendo las implementaciones que hay en Wikipedia lo correcto es usar &j como decías.

      Lo corrijo, gracias.

      Eliminar