Text Mining: Distancia de Levenshtein

La distancia de Levenshtein es un potente algoritmo que puede ser aplicado para tareas de Text Mining.  Se considera a la distancia de Levenshtein como la generalización de la distancia de Hamming y de la distancia de Damerau-Levenshtein, y determina una medida de “similaridad” o “cercanía” entre dos cadenas de caracteres. Por ejemplo, la distancia de Levenshtein entre “honda” y “ondas” es de 2, ya que se necesitan al menos dos ediciones elementales para cambiar uno en el otro:

  1. honda → onda (eliminación de ‘h’)
  2. onda → ondas (inserción de ‘s’ al final)

Este algoritmo fue propuesto por Vladimir Levenshtein en 1965 y desde entonces ha sido ampliamente usado para realizar el matching entre cadenas, por ejemplo, para correctores ortográficos.

La implementación del algoritmo requiere el uso de una matriz de tamaño (n + 1) × (m + 1), donde n y m son las longitudes de los cadenas que se comparan. Su implementación es sencilla y se puede encontrar en distintos lenguajes, tales como C++, C#, Java, Perl, Python, Ruby, PHP, Delphi, VB.NET, ActionScript y ColdFusion. Presentamos aquí la implementación en SQL (gentileza de Joseph Gama que ha escrito una implementación en T-SQL) que utilizaremos en el ejercicio de más adelante:

CREATE function LEVENSHTEIN( @s varchar(50), @t varchar(50) )
--Returns the Levenshtein Distance between strings s1 and s2.
--Original developer: Michael Gilleland http://www.merriampark.com/ld.htm
--Translated to TSQL by Joseph Gama
returns varchar(50)
as
BEGIN
DECLARE @d varchar(100), @LD int, @m int, @n int, @i int, @j int, @s_i char(1), @t_j char(1),@cost int
--Step 1
SET @n=LEN(@s)
SET @m=LEN(@t)
SET @d=replicate(CHAR(0),100)
If @n = 0
	BEGIN
	SET @LD = @m
	GOTO done
	END
If @m = 0
	BEGIN
	SET @LD = @n
	GOTO done
	END
--Step 2
SET @i=0
WHILE @i<=@n
	BEGIN
	SET @d=STUFF(@d,@i+1,1,CHAR(@i)) --d(i, 0) = i
	SET @i=@i+1
	END

SET @i=0
WHILE @i<=@m
	BEGIN
	SET @d=STUFF(@d,@i*(@n+1)+1,1,CHAR(@i)) --d(0, j) = j
	SET @i=@i+1
	END
--goto done
--Step 3
	SET @i=1
	WHILE @i<=@n
		BEGIN
		SET @s_i=(substring(@s,@i,1))
--Step 4
	SET @j=1
	WHILE @j<=@m
		BEGIN
		SET @t_j=(substring(@t,@j,1))
		--Step 5
		If @s_i = @t_j
			SET @cost=0
		ELSE
			SET @cost=1
--Step 6
		SET @d=STUFF(@d,@j*(@n+1)+@i+1,1,CHAR(dbo.MIN3(
		ASCII(substring(@d,@j*(@n+1)+@i-1+1,1))+1,
		ASCII(substring(@d,(@j-1)*(@n+1)+@i+1,1))+1,
		ASCII(substring(@d,(@j-1)*(@n+1)+@i-1+1,1))+@cost)
		))
		SET @j=@j+1
		END
	SET @i=@i+1
	END
--Step 7
SET @LD = ASCII(substring(@d,@n*(@m+1)+@m+1,1))
done:
--RETURN @LD
--I kept this code that can be used to display the matrix with all calculated values
--From Query Analyser it provides a nice way to check the algorithm in action
--
RETURN @LD
--declare @z varchar(255)
--set @z=''
--SET @i=0
--WHILE @i<=@n
--	BEGIN
--	SET @j=0
--	WHILE @j<=@m
--		BEGIN
--		set
@z=@z+CONVERT(char(3),ASCII(substring(@d,@i*(@m+1)+@j+1 ,1)))
--		SET @j=@j+1
--		END
--	SET @i=@i+1
--	END
--print dbo.wrap(@z,3*(@n+1))
END

El Ejercicio

Supóngase que tiene un listado de direcciones postales “sucias” y necesita hacer una limpieza de datos, con un diccionario callejero, para determinar la calidad de sus datos:

Dirección sucia Diccionario
YUNGAY YUNGAY
7 JUNIO SIETE DE JUNIO
R SOTOMAYOR RAFAEL SOTOMAYOR
B ENCALADA BLANCO ENCALADA
GRAL VELASQUEZ GENERAL VELASQUEZ
STA MARIA SANTA MARIA
V MACKENNA VICUÑA MACKENNA
SN ANTONIO SAN ANTONIO
A BELLO ANDRES BELLO

Lo primero que uno podría hacer es separar las cadenas de búsqueda, con un split, e ir comparando palabra por palabra, y devolver la media de los resultados máximos obtenidos. No obstante,  podríamos también usar la distancia de Levenshtein y luego hacer un rankig, desde la menor distancia hasta la más alta. Luego, determinar un punto de corte y poder así determinar cuán buenos son nuestros datos:

Dirección sucia Diccionario DL
YUNGAY YUNGAY 0
SN ANTONIO SAN ANTONIO 1
STA MARIA SANTA MARIA 2
GRAL VELASQUEZ GENERAL VELASQUEZ 3
R SOTOMAYOR RAFAEL SOTOMAYOR 5
V MACKENNA VICUÑA MACKENNA 5
A BELLO ANDRES BELLO 5
B ENCALADA BLANCO ENCALADA 6
7 JUNIO SIETE DE JUNIO 13

Interesante cierto?.  Aparte de Text Mining, este tipo de algoritmos también se utiliza para tareas más complejas, como comparar secuencias de ADN. Les dejamos aquí el enlace a una tremenda página por si quieren seguir profundizando en el tema. Saludos y escriban sus comentarios!.

Comments ( 2 )

  1. / Wilfo Martel
    Interesante sitio , pero me gustaría que expliques el proceso del algoritmo para aprender su funcionamiento.Pero realmente me he quedado con ganas de averiguar mucho de esto.

Leave a reply