¿Qué algoritmos puedo usar para detectar si los artículos o publicaciones son duplicados?

17

Estoy tratando de detectar si un artículo o publicación en el foro es una entrada duplicada dentro de la base de datos. He pensado en esto, llegando a la conclusión de que alguien que duplica el contenido lo hará usando uno de los tres (en descendente difícil de detectar):

  1. copia simple pegue todo el texto
  2. copiar y pegar partes del texto fusionándolo con el suyo
  3. copiar un artículo de un sitio externo y disfrazarse como propio

Preparación de texto para análisis

Básicamente cualquier anomalía; El objetivo es hacer que el texto sea lo más "puro" posible. Para obtener resultados más precisos, el texto está "estandarizado" por:

  1. Eliminando los espacios en blanco duplicados y recortando al principio y al final.
  2. Las nuevas líneas están estandarizadas a \ n.
  3. Se eliminan las etiquetas HTML.
  4. El uso de un RegEx llamado URL de Daring Fireball se elimina.
  5. Yo uso el código BB en mi aplicación para que vaya a.
  6. (ä) centavos y extranjeros (además de Enlgish) se convierten a su forma no extranjera.

Guardo información sobre cada artículo en (1) tabla de estadísticas y en (2) tabla de palabras clave.

(1) Tabla de estadísticas Las siguientes estadísticas se almacenan sobre el contenido textual (al igual que esta publicación)

  1. longitud del texto
  2. recuento de letras
  3. el recuento de palabras
  4. recuento de oraciones
  5. palabras promedio por oración
  6. índice de legibilidad automatizada
  7. puntaje de niebla

Para los idiomas europeos, deben usarse Coleman-Liau y el Índice de legibilidad automatizada, ya que no utilizan el conteo de sílabas, por lo que deben producir una puntuación razonablemente precisa.

(2) Tabla de palabras clave

Las palabras clave se generan al excluir una gran lista de palabras vacías (palabras comunes), por ejemplo, 'the', 'a', 'of', 'to', etc., etc.

Data de muestra

  • longitud del texto, 3963
  • letter_count, 3052
  • número de palabras, 684
  • sentencia_contador, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • palabra clave 1, asesinado
  • palabra clave 2, oficiales
  • palabra clave 3, policía

Cabe señalar que una vez que se actualiza un artículo, todas las estadísticas anteriores se regeneran y podrían tener valores completamente diferentes.

¿Cómo podría utilizar la información anterior para detectar si un artículo que se publica por primera vez ya existe en la base de datos?

Soy consciente de que cualquier cosa que diseñe no será perfecta, el mayor riesgo es (1) El contenido que no es un duplicado se marcará como duplicado (2) El sistema permite que pase el contenido duplicado.

Por lo tanto, el algoritmo debe generar un número de evaluación de riesgos a partir de 0 sin riesgo duplicado, siendo posible 5 duplicado y 10 duplicado. Cualquier cosa por encima de 5, entonces hay una buena posibilidad de que el contenido esté duplicado. En este caso, el contenido podría marcarse y vincularse a los artículos que son posibles duplicados y un humano podría decidir si desea eliminarlo o permitirlo.

Como dije antes, estoy almacenando palabras clave para todo el artículo, sin embargo, me pregunto si podría hacer lo mismo en base al párrafo; Esto también significaría una mayor separación de mis datos en la base de datos, pero también facilitaría la detección de (2) en mi publicación inicial.

Estoy pensando en el promedio ponderado entre las estadísticas, pero en qué orden y cuáles serían las consecuencias ...

algorithms Miguel
fuente
Si es una coincidencia exacta, simplemente puede establecer un campo en único. De lo contrario, deberá decidir en qué momento un texto puede considerarse una copia o un trabajo derivado.
James P.
2
Hay muchas direcciones en las que puede ir este tipo de análisis. La gente escribe libros enteros sobre este tipo de tema. Si su objetivo es determinar la "cercanía relativa", realmente no tiene más remedio que profundizar en lo que se denomina procesamiento del lenguaje natural y aprendizaje automático . Así lo llaman los científicos informáticos, pero en realidad es solo un análisis estadístico avanzado. Un buen punto de partida podría ser mirar las distancias de levenshtein, pero las estadísticas "tontas" como el recuento de palabras / frases probablemente harán muy poco por usted.
rdlowrey
1
Además, antes de que se migrara desde SO, esto se etiquetaba [php], por lo que puede consultar la función levenshtein nativa de php
rdlowrey
¡Gran idea tener un cheque humano probablemente duplicado! Es posible que pueda decidir automáticamente que> 7 es un duplicado y <6 es diferente y solo los humanos verifican puntajes de 6 o 7. Sé que con la identificación de spam hay una máquina-no-sabe-Y-humana- no sabe-ninguna de las categorías; un área gris entre un duplicado cercano y un trabajo original donde lo mejor que puede hacer es hacer una decisión de juicio algo arbitraria.
GlenPeterson
@rdlowrey: los algoritmos de Levenshtein son los que utilicé en un proyecto similar que hice en C #. Estoy de acuerdo, es un buen lugar para comenzar y puede ser suficiente.
jfrankcarr

Respuestas:

4

Hay muchos algoritmos que se ocupan de la similitud de documentos en PNL. Aquí hay un artículo seminal que describe varios algoritmos. También wikipedia tiene una colección más grande. Estoy a favor de la medida de Jaro Winkler y la he usado para proyectos de escuelas de posgrado en métodos de agrupamiento aglomerativo.

Sincero
fuente
6

Echa un vistazo al algoritmo Rabin-Karp . Utiliza un hash móvil similar a rsync para minimizar los bytes transmitidos durante una sincronización. Al ajustar el tamaño de la ventana que usa para el hash, puede hacerlo más o menos sensible. RK se utiliza para, entre otras cosas, la detección de plagio, que básicamente busca una especie de engaños.

Peter Rowell
fuente
44
El problema que describe el OP parece exactamente la detección de plagio , y sugeriría que es el primer lugar para buscar ayuda. (¡Solo asegúrese de identificar sus fuentes!)
Caleb
4

Un primer intento podría ser detectar oraciones (o algún otro bloque de datos razonable. Tome esos bloques y elimine cualquier dato mete, espacio en blanco aleatorio html, retornos, etc. Tome un resultado MD5 y guárdelo en una tabla. Podría luego haga coincidir estos bloques para intentar encontrar coincidencias.

Si esto no funciona, puede probar n-gramas. Aquí necesita una entrada de cada palabra en la página, pero debería poder darle coincidencias bastante buenas.

http://en.wikipedia.org/wiki/N-gram

gam3
fuente
Las medidas basadas en n gramos son mucho mejores que los hash md5, especialmente para datos semiestructurados como html.
Candide
1

Para una matemática matemática exacta, guardaría un hash y luego lo compararía.

Creo que los sistemas que se usan para los exámenes miden grupos de palabras y luego la frecuencia de grupos de cada tamaño. Por ejemplo, una cadena de 30 palabras que se copian obtendría 5 puntos de riesgo y 5 ocurrencias de cadenas de 10 palabras obtendrían 5 puntos. Entonces tendrías un umbral de 30 puntos por cada 500 palabras.

Realmente necesitas un algoritmo semántico para que palabras como 'también' y 'y' se analicen de la misma manera.

Llama invertida
fuente