Algoritmo para detectar documentos similares en script python

Necesito escribir un módulo para detectar documentos similares. He leído muchos documentos de huellas dactilares de técnicas de documentos y otros, pero no sé cómo escribir código o implementar dicha solución. El algoritmo debería funcionar para el idioma chino, japonés, inglés y alemán o ser independiente del idioma. ¿Cómo puedo lograr esto?

Los filtros bayesianos tienen exactamente este propósito. Esa es la tecnología 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 para el que lo entrenará: texto técnico, canciones, chistes, etc. Siempre que pueda proporcionar suficiente material para que la herramienta sepa cómo se ve su documento.

Si estos son documentos de texto puro, o si tiene un método para extraer el texto de los documentos, puede utilizar una técnica llamada teja.

Primero calcula un hash único para cada documento. Si estos son los mismos, ya está hecho.

Si no, rompes cada documento en trozos más pequeños. Estas son tus ‘culebrillas’.

Una vez que tenga las tejas, puede calcular los hashes de identidad de cada teja y compararlas para determinar si los documentos son realmente iguales.

La otra técnica que puede usar es generar n-gtwigs de los documentos completos y calcular la cantidad de n-gramos similares en cada documento y producir una puntuación ponderada para cada documento. Básicamente, un n-gramo es dividir una palabra en partes más pequeñas. ‘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 computacionalmente en una gran cantidad de documentos o en dos documentos muy grandes. Por supuesto, los n-gtwigs comunes ‘el’, ‘th,’ th ‘, etc. deben ponderarse para obtener una puntuación más baja.

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!

Puede usar o, por último, estudiar el diflib de Python’s stdlib 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 puedes 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 sea un comienzo.

La similitud se puede encontrar fácilmente sin clasificación. Prueba 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 

Necesitas hacer tu pregunta más concreta. Si ya ha leído los documentos de huellas dactilares, ya conoce los principios en funcionamiento, por lo que describir 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 en la web que han salido de Stanford, Google, Yahoo y MS en los últimos años.

¿Tiene problemas específicos con la encoding de los algoritmos descritos?

¿Problemas para empezar?

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 de duplicados, de modo que sea fácil conectar analizadores diferentes para diferentes idiomas y mantener la pieza de detección duplicada lo mismo.

Hay una buena charla sobre redes neuronales en Google Techtalks que habla sobre el uso de máquinas Boltzmann en capas para generar vectores de características para documentos que luego se pueden usar para medir la distancia de los documentos. El problema principal es el requisito de tener un gran conjunto de documentos de muestra para capacitar a la red para descubrir características relevantes.

Si está preparado para indexar los archivos entre los que desea buscar, Xapian es un excelente motor y proporciona enlaces de Python:

http://xapian.org/

http://xapian.org/docs/bindings/python/

Si está tratando de detectar los documentos que hablan sobre el mismo tema, puede intentar recostackr las palabras que se usan con más frecuencia y tirar las palabras de parada . Los documentos que tienen una distribución similar de las palabras que se usan con más frecuencia probablemente hablan de cosas similares. Es posible que tenga que hacer algunos arreglos y extender el concepto a n-grams si desea una mayor precisión. Para técnicas más avanzadas, mira en el aprendizaje automático.

Creo que Jeremy ha acertado en la cabeza: si solo quieres detectar si los archivos son diferentes, un algoritmo hash como MD5 o SHA1 es una buena manera de hacerlo.

El software de control de fuente Git de Linus Torvalds utiliza el hash SHA1 de esta manera, para verificar cuándo se han modificado los archivos.

Es posible que desee ver el algoritmo DustBuster como se describe en este documento .

Desde el papel, pueden detectar páginas duplicadas sin siquiera examinar el contenido de la página. Por supuesto, examinar los contenidos aumenta la eficacia, pero el uso de registros de servidor sin procesar es adecuado para que el método detecte páginas duplicadas.

Similar a la recomendación de usar hashes MD5 o SHA1, el método DustBuster se basa en gran medida en comparar el tamaño del archivo como su señal principal. Tan simple como suena, es bastante efectivo para una primera pasada inicial.