Distancia de Levenshtein y similitud de texto en Python

D

Introducción

Escribir texto es un proceso creativo que se basa en pensamientos e ideas que nos vienen a la mente. La forma en que está escrito el texto refleja nuestra personalidad y también está muy influenciada por el estado de ánimo en el que nos encontramos, la forma en que organizamos nuestros pensamientos, el tema en sí y las personas a las que nos dirigimos: nuestros lectores.

En el pasado sucedía que dos o más autores tenían la misma idea, la escribían por separado, la publicaban con su nombre y creaban algo muy parecido. Antes de las publicaciones electrónicas, sus ideas tardaban un tiempo en circular y, por lo tanto, generaban conflictos sobre el verdadero inventor y quién debería ser el honrado por ello.

Hoy en día, todos los artículos están disponibles de inmediato en línea en formato digital. Los artículos en línea están indexados correctamente y vinculados a otros documentos, lo que hace que sea fácil encontrarlos rápidamente. Por un lado esta forma de trabajar simplifica el intercambio de ideas así como la investigación sobre un tema pero por otro lado la accesibilidad abre puertas para simplemente copiar y pegar otros trabajos sin permiso o reconocerlos, lo que se llama plagio.

En este punto entran en juego métodos que se ocupan de la similitud de diferentes textos. La idea principal detrás de esto es poder responder a las preguntas si dos textos (o conjuntos de datos en general) son total o al menos parcialmente similares, si están relacionados entre sí en términos del mismo tema y cuántas ediciones deben ser hecho para transformar un texto en otro.

Como ejemplo, esta tecnología es utilizada por sistemas de recuperación de información, motores de búsqueda, sistemas de indexación automática, resúmenes de texto, sistemas de categorización, verificadores de plagio, reconocimiento de voz, sistemas de clasificación, análisis de ADN y algoritmos de creación de perfiles (programas IR / AI para vincular datos automáticamente entre las personas y lo que hacen).

Métodos de búsqueda y comparación

Todos estamos familiarizados con la búsqueda en un texto de una palabra específica o secuencia de caracteres (patrón). El objetivo es encontrar la ocurrencia exacta (coincidencia) o encontrar una coincidencia no exacta utilizando caracteres con un significado especial, por ejemplo, expresiones regulares o por lógica difusa. En su mayoría, es una secuencia de caracteres similar a otra.

Además, la similitud se puede medir por la forma en que suenan las palabras: ¿suenan similares pero están escritas de una manera diferente? Las traducciones de un alfabeto a otro a menudo dan más de un resultado según el idioma, por lo que para encontrar parientes basados ​​en las diferentes grafías de su apellido y nombre, se creó el algoritmo Soundex y sigue siendo uno de los más populares y extendidos en la actualidad.

Por último, pero no menos importante, ¿cuántos cambios (ediciones) son necesarios para pasar de una palabra a la otra? Cuantas menos ediciones se hagan, mayor será el nivel de similitud. Esta categoría de comparación contiene la Distancia de Levenshtein en los que nos centraremos con más detalle a continuación.

La Tabla 1 cubre una selección de formas de buscar y comparar datos de texto. La columna de la derecha de la tabla contiene una selección de los módulos de Python correspondientes para lograr estas tareas.

Paquetes de Python de método o algoritmo de categoría

Busqueda exactaBúsqueda de cadenas de Boyer-Moore, búsqueda de cadenas de Rabin-Karp, Knuth-Morris-Pratt (KMP), Expresiones regularesString, re, Advas
Búsqueda exactabúsqueda de bigramas, búsqueda de trigramas, lógica difusaBorroso
Algoritmos fonéticosSoundex, Metaphone, Double Metaphone, Caverphone, NYIIS, Kölner Phonetik, Match Rating codexAdvas, Borroso, Medusa, fonética, kph
Cambios o edicionesDistancia de Levenshtein, distancia de Hamming, distancia de Jaro, distancia de Jaro-Winklereditar distancia, python-Levenshtein, Medusa

tabla 1

La distancia de Levenshtein

Este método fue inventado en 1965 por el matemático ruso Vladimir Levenshtein (1935-2017). El valor de distancia describe el número mínimo de eliminaciones, inserciones o sustituciones que se requieren para transformar una cadena (la fuente) en otra (el destino). A diferencia del Distancia de Hamming, la distancia de Levenshtein funciona en Strings con una longitud desigual.

Cuanto mayor es la distancia de Levenshtein, mayor es la diferencia entre las Strings. Por ejemplo, de “prueba” a “prueba”, la distancia de Levenshtein es 0 porque las cadenas de origen y de destino son idénticas. No se necesitan transformaciones. Por el contrario, de “prueba” a “equipo”, la distancia de Levenshtein es 2: se deben realizar dos sustituciones para convertir “prueba” en “equipo”.

Aquí hay un gran video que explica cómo funciona el algoritmo:

Implementación de la distancia de Levenshtein en Python

Para Python, hay bastantes implementaciones diferentes disponibles en línea [9,10] así como de diferentes paquetes de Python (consulte la tabla anterior). Esto incluye versiones que siguen el Programación dinámica concepto, así como versiones vectorizadas. La versión que mostramos aquí es una versión iterativa que usa el paquete NumPy y una única matriz para hacer los cálculos. Como ejemplo, nos gustaría encontrar la distancia de edición entre “prueba” y “texto”.

Comienza con una matriz vacía que tiene el tamaño de la longitud de las cadenas. Tanto la primera fila como la columna, comenzando desde cero, se indexan cada vez más:

         t   e   s   t
  [[ 0.  1.  2.  3.  4.]
 t [ 1.  0.  0.  0.  0.]
 e [ 2.  0.  0.  0.  0.]
 x [ 3.  0.  0.  0.  0.]
 t [ 4.  0.  0.  0.  0.]]

A continuación, siguen dos bucles para comparar las cadenas letra por letra: en filas y en columnas. Si dos letras son iguales, el nuevo valor en la posición [x, y] es el mínimo entre el valor de la posición [x-1, y] + 1, posición [x-1, y-1]y posición [x, y-1] + 1.

[+0.] [+1.]
[+1.] [   ]

De lo contrario, es el mínimo entre el valor de la posición [x-1, y] + 1, posición [x-1, y-1] + 1y posición [x, y-1] + 1. Nuevamente, esto se puede visualizar como una submatriz de dos por dos donde está calculando el valor faltante en la posición inferior derecha como se muestra a continuación:

[+1.] [+1.]
[+1.] [   ]

Tenga en cuenta que hay tres tipos posibles de cambio si los dos caracteres son diferentes: insertar, eliminar y sustituir. Finalmente, la matriz se ve como sigue:

         t   e   s   t
  [[ 0.  1.  2.  3.  4.]
 t [ 1.  0.  1.  2.  3.]
 e [ 2.  1.  0.  1.  2.]
 x [ 3.  2.  1.  1.  2.]
 t [ 4.  3.  2.  1.  1.]]

La distancia de edición es el valor en la posición [4, 4] – en la esquina inferior derecha – que es 1, en realidad. Tenga en cuenta que esta implementación está en O(N*M) tiempo, para N y M las longitudes de las dos Strings. Otras implementaciones pueden ejecutarse en menos tiempo, pero son más ambiciosas de comprender.

Aquí está el código correspondiente para el algoritmo de distancia de Levenshtein que acabo de describir:

import numpy as np

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    for x in xrange(size_x):
        matrix [x, 0] = x
    for y in xrange(size_y):
        matrix [0, y] = y

    for x in xrange(1, size_x):
        for y in xrange(1, size_y):
            if seq1[x-1] == seq2[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    print (matrix)
    return (matrix[size_x - 1, size_y - 1])

Referencias

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

1 comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con tus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad