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.
Recientemente en grupos de .NET salió el tema de cómo se pueden redimensionar las dos dimensiones de una matriz de dos dimensiones sin perder los valores que ya se tienen almacenados en dicha matriz.
Últimos comentarios
RSS