Comparar dos documentos es una tarea relativamente compleja, especialmente si buscamos coincidencias parciales entre los mismos. Para esta tarea en el módulo difflib de Python podemos encontrar la clase SequenceMatcher con la que realizar esta tarea. Una clase con la que localizar las coincidencias existentes en las subsecuencia, al mismo tiempo que se puede obtener un grado de similitud entre los documentos. Veamos cómo funciona esta clase.
LCS (Longest Contiguous matching Subsequence)
El problema básico que resuelve la clase SequenceMatcher es localizar la subsecuencia de coincidencia contigua más larga (LCS, Longest Contiguous matching Subsequence) entre dos secuencias. Esto sin tener en cuenta la presencia de elementos “basura”, es decir, aquellas subsecuencias que no aportan valor a la secuencia.
Por ejemplo, si tenemos la cadena “Hola mundo” y “Hola Analytics Lane” la subsecuencia de coincidencia contigua más larga es “Hola ”. Esto es, la subcadena de texto más larga que se encuentra en ambas.
Uso de SequenceMatcher
El constructor SequenceMatcher tiene la siguiente forma
SequenceMatcher(isjunk=None, a='', b='', autojunk=True)
En donde isjunk es una función que devuelve verdadero para aquellos elementos que se considera “basura”, a es la primera secuencia, b es la segunda secuencia y autojunk es una opción con la que eliminar la heurística que permite detectar automáticamente secuencias “basura”. Una vez creada la clase se puede acceder al método find_longest_match para localizar la subsecuencia de coincidencia contigua más larga. Método que requiere cuatro entradas: la posición inicial de búsqueda en la secuencia a, la posición final de búsqueda en la secuencia a, la posición inicial de búsqueda en la secuencia b y la posición final de búsqueda en la secuencia b. Así para buscar en dos cadenas se puede usar:
from difflib import SequenceMatcher str1 = ' Hola' str2 = 'Hola Hola' matcher = SequenceMatcher(None, str1, str2) match = matcher.find_longest_match(0, len(str1), 0, len(str2)) match
Match(a=0, b=4, size=5)
Lo que nos devuelve en match un objeto Match en el que nos da la posición inicial de la subsecuencia en a, b y la longitud de esta. Así es posible ver la cadena usando la siguiente línea de código:
str1[match.a:match.a + match.size]
' Hola'
Indicar las secuencias “basura”
Habitualmente es posible que deseemos que algunos elementos como los espacios y la puntuación ya que no aportan información. Es decir, los podemos considerar “basura” dentro de la secuencia. Lo que se puede configurar a través del primer parámetro de la clase. Así para eliminar los espacios en blanco se puede usar:
matcher = SequenceMatcher(lambda x: x in " ", str1, str2) match = matcher.find_longest_match(0, len(str1), 0, len(str2)) str1[match.a:match.a + match.size]
'Hola'
Obtener todas las secuencias
Además del método find_longest_match También existe el método get_matching_blocks que devolverá todos los bloques de texto coincidentes existentes en las dos secuencias. Lo que devolverá un listado de objetos Mathc como el que devuelve el método find_longest_match. Los objetos no están ordenados, pero si queremos ordenarlos en base al tamaño se puede usar la función sort:
sorted(matcher.get_matching_blocks(), key=lambda obj: obj.size, reverse=True)
Ratio de similitud
Finalmente se puede obtener una ratio de similitud entre las dos secuencias que se puede obtener mediante el método ratio. Un valor que se calcula como 2*M/T donde M son la coincidencias y T el número de elementos en ambas secuencias. Así se puede comprobar el resultado usando
T = len(str1) + len(str2)
M = 0
for matchin matcher.get_matching_blocks():
M += match.size
ratio = 2 * M / T
ratio0.7142857142857143
El mismo resultado que el método ratio
matcher.ratio()
0.7142857142857143
Esta ratio, que tiene valores entre 0 y 1, es una medida de similares o no que las dos secuencias comparadas. No es una distancia pero se podría crear una a partir del resutlado.
Conclusiones
En esta entrada se ha visto el comportamiento de la clase SequenceMatcher con la que se puede comparar las coincidencias entre dos secuencias. Una herramienta con la que se puede analizar las similitudes que existen entre dos documentos.
Deja una respuesta