Distancia de Levenshtein y similitud de texto en Python

    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 鈥嬧媏n 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

    Etiquetas:

    Deja una respuesta

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