Métricas de similitud para cadenas de texto. Parte II: Métricas basadas en operaciones de edición.

Share on facebook
Share on twitter
Share on linkedin

Parte I: Introducción.
Parte II: Métricas basadas en operaciones de edición (lo estás leyendo).
Parte III: Métricas de conjuntos y emparejamiento de caracteres (próximamente).
Parte IV: Biblioteca hermetrics para python (próximamente).

En la primera parte de esta serie de artículos, se habló sobre las métricas de similitud para cadenas de texto en general. Este artículo se tratará de algunas métricas de similitud basadas en caracteres, enfocándose en aquellas que utilizan las operaciones de edición descritas en el artículo previo, tales como borrado, inserción, sustitución o transposición de caracteres. Una implementación de estas métricas puede encontrarse en la biblioteca hermetrics para python disponible en github.

Hamming

La distancia de Hamming, de uso común en teoría de la información, criptografía y telecomunicaciones, es una de las métricas de distancia más simples.

Al comparar dos cadenas de texto con la distancia de Hamming simplemente se hace un conteo del número de posiciones en las que los símbolos de las cadenas son diferentes. Una restricción de la distancia de Hamming tradicional es que las cadenas para ser comparadas deben ser del mismo tamaño.

Otra forma de ver la distancia de Hamming, es como una distancia de edición que cuenta el número mínimo de sustituciones de caracteres requeridas para convertir una cadena en la otra.

Una implementación del algoritmo en python es:

def hamming_distance(s1, s2):
    """Calcula la distancia de Hamming entre dos cadenas
    devuelve -1 si las cadenas son de diferente longitud"""
    if len(s1) != len(s2):
        return -1
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

Ejemplos:

hamming_distance(“carcasa”,”carroza”)
3hamming_distance(“amigo”,”amigo”)
0hamming_distance(“perro”,”elefante”)
-1

Levenshtein

La distancia de Levenshtein es quizá la más común y simple (sin tomar en cuenta la distancia de Hamming) de las métricas de edición basadas en caracteres, por lo que generalmente (y quizá también por la dificultad de pronunciación) se le conoce simplemente como “distancia de edición”, aunque este término se refiere en realidad a una familia más grande de métricas, algunas de las cuales se hablará más adelante.

Esta distancia puede definirse como el número mínimo de operaciones de edición requeridas para convertir una cadena en la otra, considerando como operaciones válidas el borrado, la inserción o la sustitución. Algunos de los campos de aplicación que utilizan la distancia de Levenshtein son: la corrección ortográfica automática, los sistemas de reconocimiento del habla, el análisis de ADN y en la detección de plagio.

Esta métrica es, en cierto sentido, una forma de cuantificar la diferencia entre dos cadenas de texto, sin embargo, aunque por su descripción parezca sencilla, la forma de calcularla no es trivial como en el caso de la distancia de Hamming, además, a diferencia de ésta última, la distancia de Levenshtein tradicional es capaz de comparar cadenas de diferente tamaño.

El algoritmo convencional para calcular esta métrica usa programación dinámica, aunque existen diversas adaptaciones y aproximaciones para reducir el costo computacional de su cálculo. En la implementación con programación dinámica, se utiliza una matriz en la que se van almacenando los resultados intermedios, producto de calcular la distancia de Levenshtein, entre los prefijos de las cadenas originales a comparar. Al final, el elemento de la esquina inferior derecha de la matriz contiene el valor de la distancia de Levenshtein.

En los siguientes ejemplos, se ve la cadena origen a la izquierda de la matriz y la cadena destino en la parte superior. La matriz contiene los valores de las distancias parciales entre las subcadenas con las celdas en amarillo indicando el “recorrido” de la distancia mínima y el resultado final en la casilla inferior derecha. Las figuras fueron obtenidas usando una calculadora en linea.

Empecemos con un ejemplo conocido, en este caso la distancia de Levenshtein coincide con la de Hamming, ya que se calcula contando las tres sustituciones necesarias para modificar las posiciones donde los caracteres no coinciden, r por c, o por a y z por s.

La distancia de Levenshtein entre “carcasa” y “carroza” es 3

Algunos otros ejemplos con su respectiva matriz que muestra la contabilización de las operaciones de edición entre dos palabras.

La distancia entre “gato” y “garabato” consiste en 4 inserciones (subcadena “arab”)
La distancia de una palabra consigo misma es 0
La diferencia entre “cebra” y “caballo” no son solo las rayas

Alineación Óptima de Cadenas (OSA)

Esta es una extensión de la distancia de Levenshtein con la diferencia de que contabiliza la transposición como una operación válida, como ejemplo miremos la comparación en el cálculo de la distancia entre las palabras “peor” y “pero” usando ambos métodos.

Distancia de Levenshtein=2 a la izquierda y OSA=1 a la derecha

La diferencia estriba en que Levenshtein necesita hacer dos operaciones (sustituir r por o y luego sustituir o por r), mientras que OSA es capaz de detectar que al invertir la o y la r, realizando una operación de transposición, se obtiene la palabra objetivo.

Una restricción de la distancia OSA es que una vez que se transpone un par de caracteres, estos ya no pueden ser utilizados nuevamente en transposiciones subsecuentes, por tal motivo OSA también recibe el nombre de distancia de edición restringida.

Otro aspecto relevante de la distancia OSA es que no necesariamente cumple con la desigualdad del triángulo, por lo que no puede considerarse como una verdadera métrica en el estricto sentido. Para verificarlo considérese que de acuerdo con la desigualdad del triángulo lo siguiente debería cumplirse:

OSA(“ca”,”abc”) ≤ OSA(“ca”, “ac”) + OSA(“ac”,”abc”)

Sin embargo, nótese que:

OSA(“ca”,”abc”) = 3,

OSA(“ca”, “ac”) = 1,

OSA(“ac”,”abc”) = 1,

y al ser 3 > 1+1 = 2, entonces la desigualdad del triángulo no se cumple.

Damerau-Levenshtein

Esta distancia es una versión no restringida de la OSA, en el sentido que puede considerar transposiciones adyacentes, para verificarlo utilicemos un ejemplo conocido con las operaciones necesarias para transformar la cadena “ca” a la cadena “abc” usando OSA y Damerau-Levenshtein (DL).

OSA(“ca”,”abc”) = 3, (“ca” -> “a” -> “ab” -> “abc”)

DL(“ca”,”abc”) = 2, (“ca” -> “ac” -> “abc”)

La capacidad de considerar transposiciones adyacentes agrega complejidad al algoritmo para calcular la distancia, sin embargo existen optimizaciones que reducen la complejidad al caso de una distancia de Levenshtein tradicional.

La distancia DL es de gran utilidad en tareas de Procesamiento de Lenguaje Natural, como por ejemplo en los correctores ortográficos presentes en editores de texto, ya que es muy común invertir caracteres al escribir por medio de un teclado.

Conclusiones

En esta segunda parte hemos visto algunas de las métricas de edición tradicionales basadas en el número mínimo de operaciones de edición necesarias para transformar una cadena en la otra. En la tercera parte de esta serie continuaremos revisando otras funciones de distancia, algunas de las cuales no consideran operaciones de edición, sino que miden la diferencia entre los conjuntos de caracteres presentes en las cadenas comparadas.

Share on facebook
Share on twitter
Share on linkedin

No hay comentarios

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

¡Conozcámonos mejor!

Te haremos llegar las novedades de SoldAI, ofertas exclusivas, notificaciones, y mucho más.

¡Deja tu correo, tenemos mucho que contarte!