Distancia de Levenshtein en VisualBasic.NET.
Hace un rato se me ha planteado un problema que quien más quien menos habrá tenido en alguna ocasión. Necesitaba poder comparar dos cadenas y obtener algún indicador de hasta qué punto podría tratarse de la misma cadena escrita de maneras ligeramente diferentes. He estado dándole vueltas sobre cómo podría jugar con los distintos métodos de la clase String para conseguir algún valor. Me he planteado utilizar análisis de frecuencias, generar números ponderados en función de carácter y posición dentro de la cadena... Pero nada me convencía, así que he insistido un poco más en buscar si ya alguien había desarrollado alguna función parecida y para mi mayúscula sorpresa me he dado de bruces con la Distancia de Levenshtein.
Resulta que esto que andaba buscando es exactamente esta distancia. Y tal como reza la Wikipedia... "se llama Distancia de Levenshtein o distancia de edición 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 substitució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."
Y para mayor regocijo, en la propia página de la Wikipedia aparece el algoritmo en pseudocódigo de la función:
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)
return d[lenStr1, lenStr2]
Incluso viene la implementación en algunos lenguajes de programación (C++, Java, Perl, Python, Ruby, Delphi y ColdFusion). Lástima que no viniera también en VisualBasic.NET que es el lenguaje en el que yo desarrollo... pero bueno, como codificar un algoritmo que ya nos viene dado en pseudocódigo tampoco es tarea infernal, a ello me he dedicado:
' Author: Albert Mata (www.albertmata.net)
' Date: 20081212
' Description: Calculates Levenshtein distance between two different
' strings.
'--------------------------------------------------------------------
Public Function LevenshteinDistance(ByVal STR1 As String, _
ByVal STR2 As String) As Integer
'Variables to iterate (i, j) and get cost for any needed
'operation.
Dim i As Integer
Dim j As Integer
Dim Cost As Integer
'Creating array with string's lengths as bounds.
Dim D(STR1.Length, STR2.Length) As Integer
'Initializing array's values.
For i = 0 To STR1.Length
D(i, 0) = i
Next
For j = 0 To STR2.Length
D(0, j) = j
Next
'Calculating Levenshtein distance.
For i = 1 To STR1.Length
For j = 1 To STR2.Length
If STR1(i - 1) = STR2(j - 1) Then
Cost = 0
Else
Cost = 1
End If
'First compared element: deletion.
'Second compared element: insertion.
'Third compared element: substitution.
D(i, j) = Math.Min(Math.Min(D(i - 1, j) + 1, _
D(i, j - 1) + 1), _
D(i - 1, j - 1) + Cost)
Next
Next
'Returning result.
Return D(STR1.Length, STR2.Length)
End Function
Creo que está bien. Y el resultado de algunas pruebas así parece demostrarlo:
0
Debug.Print(Me.LevenshteinDistance("Albert Mata", "Alber Matas"))
2
Debug.Print(Me.LevenshteinDistance("Albert Mata", "Mr. Albert Mata"))
4
No es ni mucho menos un sistema infalible, pero nos puede resultar muy útil para estimar si dos cadenas algo distintas pueden ser (o pretender ser) en realidad la misma. No obstante hay que utilizarla con cabeza, ya que por ejemplo si comparamos...
Albert Mata
Antoni Pons
...obtendremos una distancia de 9. Y si comparamos...
Berberechos y enlatados del norte, S.A.
Berberechos y enlatd. norte, SA
...obtendremos también una distancia de 9. Sin embargo en el primer caso las personas son claramente distintas y en el segundo caso el cliente parece ser el mismo. Para corregir esto se podrían buscar varias alternativas, pero yo propongo algo tan sencillo como ponderar la distancia entre la longitud de alguna de las cadenas:
Dim S2 As String = "Antoni Pons"
Dim LD As Integer = Me.LevenshteinDistance(S1, S2)
Dim Similar As Double = (S1.Length - LD) / S1.Length
Esto nos da un coeficiente de similitud del 0,181818181818182 (escaso, escaso). En cambio esto otro...
Dim S2 As String = "Berberechos y enlatd. norte, SA"
Dim LD As Integer = Me.LevenshteinDistance(S1, S2)
Dim Similar As Double = (S1.Length - LD) / S1.Length
...nos da un coeficiente de similitud del 0,769230769230769 (¡mucho mejor!). Se tratará en cada caso de establecer dónde ponemos el límite.
Tags: .NET, array, levenshtein, string, visual basic
Diciembre 14th, 2008 at 00:28
Hace tiempo también tuve esa misma necesidad e implementé la Distancia de Levenshtein en ASP.
Lo que me parece muy interesante es el último paso que comentas ¿se trata de algo ad-hoc que te has currado para esos ejemplos o has hecho más pruebas y se comporta bien?
Diciembre 14th, 2008 at 12:17
Es que la distancia en sí misma no me parece demasiado significativa. Al menos en mi caso. Lo utilizo para comparar nombres de clientes (empresas) y que no se dé de alta dos veces el mismo. Si fuera obligatorio introducir el CIF no tendría ese problema, pero el caso es que en la aplicación en cuestión el único dato requerido para dar de alta un cliente es su razón social. Y ahí entra el problema de que unos ponen "XXX, S.L." mientras otros "XXX SL" y otros directamente "XXX". Eso sin contar que XXX lo pueden escribir de muchas maneras distintas (letras dobles, errores tipográficos, clientes extranjeros que te deletrean el nombre por teléfono, etc etc). Así que una distancia de 6 sobre una longitud de 40 puede ser simplemente diferencia en las siglas de la forma jurídica y algún mínimo error tipográfico. Pero una distancia de 6 sobre una longitud de 10 probablemente sean clientes que no tienen nada que ver.
En mi caso concreto, pondero siempre entre la longitud máxima de las dos cadenas y sugiero al usuario que el cliente que intenta crear presenta similitudes con otros ya existentes cuando el coeficiente está por encima del 50%. Un 51% es la mayor parte de las veces una no-coincidencia, pero en algún caso puede sí serlo, así que cojo ese límite. De todos modos ordeno los resultados en orden decreciente de coincidencia. Bajo mi punto de vista, el resultado final es bueno.