examples - Algoritmo para detectar documentos similares en el script de python
html.parser python 3 (10)
Hay una charla bastante buena sobre redes neuronales en Google Techtalks que habla sobre el uso de máquinas en capas Boltzmann para generar vectores de características para documentos que luego pueden usarse para medir la distancia del documento. El problema principal es el requisito de tener un gran conjunto de documentos de muestra para capacitar a la red para descubrir las características relevantes.
Necesito escribir un módulo para detectar documentos similares. He leído muchos documentos sobre técnicas de huellas dactilares de documentos y otros, pero no sé cómo escribir código o implementar una solución de este tipo. El algoritmo debería funcionar en chino, japonés, inglés y alemán o ser independiente del idioma. ¿Cómo puedo lograr esto?
Necesitas hacer tu pregunta más concreta. Si ya ha leído los documentos de toma de huellas dactilares, ya conoce los principios en el trabajo, por lo que describir los enfoques comunes aquí no sería beneficioso. Si no lo ha hecho, también debe consultar los documentos sobre "detección de duplicados" y varios documentos relacionados con la detección de spam web que han surgido de Stanford, Google, Yahoo y MS en los últimos años.
¿Tienes problemas específicos para codificar los algoritmos descritos?
¿Tienes problemas para comenzar?
Lo primero que probablemente haría es separar la tokenización (el proceso de extracción de "palabras" u otras secuencias sensibles) de la lógica de detección duplicada, de modo que sea fácil conectar diferentes analizadores para diferentes idiomas y mantener la detección duplicada lo mismo.
Puede utilizar o, por fin, estudiar difflib de stdlib de Python para escribir su código.
Es muy flexible y tiene algoritmos para encontrar diferencias entre listas de cadenas y para señalar estas diferencias. Luego puede usar get_close_matches() para encontrar palabras similares:
>>> get_close_matches(''appel'', [''ape'', ''apple'', ''peach'', ''puppy''])
[''apple'', ''ape'']
No es la solución, pero tal vez es un comienzo.
Si está preparado para indexar los archivos que desea buscar, Xapian es un excelente motor y proporciona enlaces de Python:
Si está tratando de detectar los documentos que están hablando sobre el mismo tema, puede tratar de recopilar las palabras más utilizadas, deseche las palabras de finalización . Los documentos que tienen una distribución similar de las palabras usadas con mayor frecuencia probablemente estén hablando de cosas similares. Es posible que tenga que realizar una derivación y ampliar el concepto a n-grams si desea una mayor precisión. Para técnicas más avanzadas, busque en el aprendizaje automático.
Si se trata de documentos de texto puro, o si tiene un método para extraer el texto de los documentos, puede usar una técnica llamada escaldado.
Primero calcula un hash único para cada documento. Si estos son iguales, has terminado.
Si no, divide cada documento en trozos más pequeños. Estas son tus ''tejas''.
Una vez que tenga las tejas, puede calcular hashes de identidad para cada teja y comparar los hash de las tejas para determinar si los documentos son realmente iguales.
La otra técnica que puede usar es generar n-grams de los documentos completos y calcular la cantidad de n-gramas similares en cada documento y generar una calificación ponderada para cada documento. Básicamente, un n-grama está dividiendo una palabra en trozos más pequeños. ''apple'' se convertiría en ''a'', ''ap'', ''app'', ''ppl'', ''ple'', ''le''. (Esto es técnicamente un 3 gramos). Este enfoque puede llegar a ser bastante costoso desde el punto de vista computacional en una gran cantidad de documentos o en dos documentos muy grandes. Por supuesto, n-grams comunes ''the'', ''th,'' th '', etc. necesitan ser ponderados para calificarlos más bajos.
He publicado sobre esto en mi blog y hay algunos enlaces en la publicación de algunos otros artículos sobre el tema Shingling: no es solo para techadores .
¡La mejor de las suertes!
Creo que Jeremy ha dado en el clavo: si solo quieres detectar si los archivos son diferentes, un algoritmo hash como MD5 o SHA1 es una buena forma de hacerlo.
El software de control de fuente Git de Linus Torvalds usa el hash SHA1 de esta forma: para verificar cuándo se han modificado los archivos.
Los filtros bayesianos tienen exactamente este propósito. Ese es el techno que encontrarás en la mayoría de las herramientas que identifican el spam.
Ejemplo, para detectar un idioma (de http://sebsauvage.net/python/snyppets/#bayesian ):
from reverend.thomas import Bayes
guesser = Bayes()
guesser.train(''french'',''La souris est rentrée dans son trou.'')
guesser.train(''english'',''my tailor is rich.'')
guesser.train(''french'',''Je ne sais pas si je viendrai demain.'')
guesser.train(''english'',''I do not plan to update my website soon.'')
>>> print guesser.guess(''Jumping out of cliffs it not a good idea.'')
[(''english'', 0.99990000000000001), (''french'', 9.9999999999988987e-005)]
>>> print guesser.guess(''Demain il fera très probablement chaud.'')
[(''french'', 0.99990000000000001), (''english'', 9.9999999999988987e-005)]
Pero funciona para detectar cualquier tipo de entrenamiento: texto técnico, canciones, chistes, etc. Siempre que pueda proporcionar suficiente material para que la herramienta aprenda cómo se ve el documento.
La similitud se puede encontrar fácilmente sin clasificación. Pruebe este O (n2) pero funciona bien.
def jaccard_similarity(doc1, doc2):
a = sets(doc1.split())
b = sets(doc2.split())
similarity = float(len(a.intersection(b))*1.0/len(a.union(b))) #similarity belongs to [0,1] 1 means its exact replica.
return similarity
Es posible que desee examinar el algoritmo DustBuster como se describe en este documento .
A partir del documento, pueden detectar páginas duplicadas sin siquiera examinar los contenidos de la página. Por supuesto, examinar el contenido aumenta la eficacia, pero el uso de registros de servidor sin formato es adecuado para que el método detecte páginas duplicadas.
De forma similar a la recomendación de usar hashes MD5 o SHA1, el método DustBuster se basa principalmente en comparar el tamaño del archivo como señal primaria. Tan simple como suena, es bastante efectivo para un primer pase inicial.