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)