Distancia de Levenshtein y similitud de texto en Python

Escribir un texto es un proceso creativo que se basa en pensamientos e ideas que vienen a nuestra mente. La forma en que está escrito el texto refleja nuestra personalidad y es...

Introducción

Escribir un texto es un proceso creativo que se basa en pensamientos e ideas que vienen a nuestra 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 por las personas a las que lo dirigimos: nuestros lectores.

En el pasado sucedió que dos o más autores tuvieron la misma idea, la escribieron por separado, la publicaron con su nombre y crearon algo muy similar. Antes de las publicaciones electrónicas, sus ideas tardaban en circular y, por lo tanto, generaban conflictos sobre el inventor real y quién debería ser el homenajeado por ello.

Hoy en día, cada artículo está inmediatamente disponible en línea en formato digital. Los artículos en línea están indexados correctamente y vinculados a otros documentos, lo que facilita 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 reconocimiento, lo que se denomina 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 parcialmente similares, si están relacionados entre sí en términos del mismo tema y cuántas ediciones deben realizarse. 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 calificación, análisis de ADN y algoritmos de creación de perfiles (programas IR/AI para vincular automáticamente datos entre las personas y lo que hacen).

Métodos de búsqueda y comparación

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

Además, la similitud se puede medir por la forma en que suenan las palabras: ¿suenan similar pero se escriben de manera diferente? Las traducciones de un alfabeto a otro suelen dar más de un resultado dependiendo del idioma, por lo que para encontrar familiares en base a las diferentes grafías de su apellido y nombre se creó el algoritmo Soundex y sigue siendo uno de los más populares y difundidos 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 haya que hacer, mayor será el nivel de similitud. Esta categoría de comparación contiene la distancia Levenstein en la 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 derecha de la tabla contiene una selección de los módulos de Python correspondientes para lograr estas tareas.

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


Búsqueda exacta Búsqueda de cadenas de Boyer-Moore, Búsqueda de cadenas de Rabin-Karp, Knuth-Morris-Pratt (KMP), Cadena de expresiones regulares, re, Advas Búsqueda exacta Búsqueda de bigramas, búsqueda de trigramas, lógica difusa Difuso Algoritmos fonéticos Soundex, Metaphone, Double Metaphone, Caverphone, NYIIS, Kölner Phonetik, códice Match Rating Advas, [Difuso](https://pypi.python.org/pypi /Fuzzy), Medusa, fonética, [kilómetros por hora](https: //pypi.python.org/pypi/kph) Cambia o edita la distancia de Levenshtein, la distancia de Hamming, la distancia de Jaro, la distancia de Jaro-Winkler editar distancia, [python-Levenshtein](https://pypi.python. org/pypi/python-Levenshtein/0.12.0), 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 (el origen) en otra (el destino). A diferencia de la distancia de hamming, la distancia de Levenshtein funciona en cuerdas de longitud desigual.

Cuanto mayor es la distancia de Levenshtein, mayor es la diferencia entre las cuerdas. Por ejemplo, de "prueba" a "prueba", la distancia de Levenshtein es 0 porque tanto la cadena de origen como la 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:

jugador no disponible

Ocurrió un error. {#ocurrió un error. .mensaje}

submensaje Intenta ver este video en www.youtube.com{target="_blank"}, o habilita JavaScript si está deshabilitado en tu navegador.

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 siguiendo el concepto Programación dinámica así como versiones vectorizadas. La versión que mostramos aquí es una versión iterativa que usa el paquete NumPy y una sola matriz para hacer los cálculos. Como ejemplo, nos gustaría averiguar 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 primera columna, a partir de cero, se indexan de forma creciente:

1
2
3
4
5
6
         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, por filas y por 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, la posición [x-1, y-1] , y la posición [x, y-1] + 1.

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

De lo contrario, es el mínimo entre el valor de la posición [x-1, y] + 1, la posición [x-1, y-1] + 1 y la 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
2
[+1.] [+1.]
[+1.] [   ]

Tenga en cuenta que hay tres posibles tipos de cambio si los dos caracteres son diferentes: insertar, eliminar y sustituir. Finalmente, la matriz queda de la siguiente manera:

1
2
3
4
5
6
         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 en realidad es 1. Tenga en cuenta que esta implementación está en tiempo O(N*M), para N y M las longitudes de las dos cadenas. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

Agradecimientos

El autor quisiera agradecer
axel beckert, Mandy Neumeyer, Geroldo Rupprecht y [Zoleka Hatitongwe](http://www. upsurgesa.co.za/) por su apoyo durante la preparación del artículo. culo.