Comparar textos usando IA con la Distancia de Levenshtein

Cuando estamos programando motores que pretenden emular a un ser humano, debemos comparar la similitud de muchos datos. El problema de las comparativas son que un ser humano tiene sentido común, un software NO.

Existen muchos casos dónde es necesario comparar cadenas de texto más allá de la comparativa usual:

Código :

if(cadena_1 == cadena_2) algo : otro;

Y más bien necesitan algo como:

Código :

if(cadena_1 {se_parece_a} cadena_2) algo:otro; 

Para esto usaremos la Distancia de Levenshtein. Que en realidad suena algo MUY complejo pero no lo es. En este tip intentaré explicar la manera de analizar algo con este algoritmo, no como funciona en sí mismo, ya que hasta PHP trae una función para solucionarlo.

Encontrar palabras similares aún con errores

Imaginen un caso simple, debemos detectar en nuestra base de datos quienes han tipeado mal el país. Ya que queremos implementar un sistema experto que analice de cada país viene cada uno como una subrutina. El problema, es que los datos están en String no Int.

Entonces para realizar el sistema, imaginen tenemos esto:

Código :

Freddie Colomia (En vez de Colombia)
Hernán Aregntina (En vez de Argentina)

Y otra tabla de países donde diremos:

Código :

Argentina ID = 1
Colombia ID = 2

El resultado final esperado será:

Código :

Freddie = 2
Hernan = 1

Traer los datos de países para comparación con el texto a detectar

No tiene sentido analizar toda la base de datos con la distancia de Levenshtein, ya que solo algunos pocos esperamos tengan problema (En nuestro ejemplo, Freddie y Hernán).

Por lo cual primero modelaremos un pequeño GPS (que ya vimos en otro tip) para procesar correctamente sin usar recursos extra:

Modelo GPS para Análisis:

1. Buscar con Inner Join en la tabla Usuarios y tabla Países
   
2. Todos estos resultados editarlos dándoles su value de país
   
3. Buscar todos los resultados que hayan quedado sin valor (int !=0)
   
4. Eliminar espacios en blanco de la cadena y pasar a minúsculas
   
5. Seleccionar en la base de datos los más similares a la cadena a analizar
   
6. Eliminar espacios en blanco de los resultados y pasar a minúsculas
   
7. Aplicar distancia de Levenshtein
   
8. Aplicar el valor más cercano al país

Algoritmo Levenshtein

En la propia Wikipedia podrán encontrar el algoritmo con muchas aplicaciones, sin embargo dejo aquí las dos más usadas para Clab (PHP y AS3).

Código :

public class StringUtils 
{  
    public static function levenshtein(s1:String, s2:String):int
    {      
        if (s1.length == 0 || s2.length == 0)
       return 0;
 
        var m:uint = s1.length + 1;
        var n:uint = s2.length + 1;
        var i:uint, j:uint, cost:uint;
        var d:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
 
        for (i = 0; i < m; i++)
        {
            d[i] = new Vector.<int>();
            for (j = 0; j < n; j++)
                d[i][j] = 0;
        }
 
        for (i = 0; i < m; d[i][0] = i++) ;
        for (j = 0; j < n; d[0][j] = j++) ;
 
        for (i = 1; i < m; i++)
        {
       for (j = 1; j < n; j++)
            {       
                cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
                d[i][j] = Math.min(Math.min(d[i - 1][j] + 1,
                d[i][j - 1] + 1),
                d[i - 1][j - 1] + cost);
            }
        }
 
        return d[m-1][n-1];
    }
}

Código :

<?php
   $lev = levenshtein($input, $word);
?>

Cuando usar la Distancia de Levenshtein

Conocer la existencia de este algoritmo de distancia entre Strings es muy útil para correctores ortográficos, buscar similitudes de búsqueda, encontrar errores de tipeo, etc. Y por sobre todo, es genial para evitar cagar comparativas en sistemas expertos que requieren de un aprendizaje estandarizado.

 

Tweet