Quali algoritmi posso utilizzare per rilevare se articoli o post sono duplicati?

17

Sto cercando di rilevare se un articolo o un post sul forum è una voce duplicata all'interno del database. Ho riflettuto su questo, giungendo alla conclusione che qualcuno che duplica il contenuto lo farà usando uno dei tre (in ordine discendente difficile da rilevare):

  1. copia semplice incolla l'intero testo
  2. copia e incolla parti di testo unendole con le proprie
  3. copia un articolo da un sito esterno e esegui il masquerade come proprio

Preparazione del testo per l'analisi

Praticamente qualsiasi anomalia; l'obiettivo è rendere il testo il più "puro" possibile. Per risultati più accurati, il testo è "standardizzato" da:

  1. Strippaggio degli spazi bianchi duplicati e ritaglio di inizio e fine.
  2. Le nuove righe sono standardizzate per \ n.
  3. I tag HTML vengono rimossi.
  4. Usando un RegEx chiamato Daring Fireball, gli URL vengono rimossi.
  5. Uso il codice BB nella mia applicazione in modo tale che vada a
  6. (ä) ccented e foreign (oltre a Enlgish) vengono convertiti nella loro forma non straniera.

Conservo le informazioni su ciascun articolo nella (1) tabella delle statistiche e nella (2) tabella delle parole chiave.

(1) Tabella delle statistiche Le seguenti statistiche sono memorizzate sul contenuto testuale (molto simile a questo post)

  1. lunghezza del testo
  2. numero di lettere
  3. numero di parole
  4. numero di frasi
  5. parole medie per frase
  6. indice di leggibilità automatica
  7. gunning fog score

Per le lingue europee dovrebbe essere utilizzato Coleman-Liau e l'indice di leggibilità automatizzata in quanto non usano il conteggio delle sillabe, quindi dovrebbe produrre un punteggio ragionevolmente accurato.

(2) tabella delle parole chiave

Le parole chiave vengono generate escludendo un enorme elenco di parole di arresto (parole comuni), ad esempio "il", "un", "di", "a", ecc. ecc.

Dati campione

  • text_length, 3963
  • letter_count, 3052
  • word_count, 684
  • frase_count, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • Parola chiave 1, uccisa
  • parola chiave 2, ufficiali
  • parola chiave 3, polizia

Va notato che una volta che un articolo viene aggiornato tutte le statistiche di cui sopra vengono rigenerate e potrebbero essere valori completamente diversi.

Come potrei utilizzare le informazioni di cui sopra per rilevare se un articolo che viene pubblicato per la prima volta, è già presente nel database?

Sono a conoscenza che tutto ciò che progetterò non sarà perfetto, il più grande rischio è (1) Il contenuto che non è un duplicato verrà contrassegnato come duplicato (2) Il sistema consente il contenuto duplicato attraverso.

Quindi l'algoritmo dovrebbe generare un numero di valutazione del rischio da 0 in cui nessun rischio duplicato 5 è possibile duplicato e 10 duplicato. Qualunque cosa al di sopra di 5 allora c'è una buona possibilità che il contenuto sia duplicato. In questo caso il contenuto potrebbe essere contrassegnato e collegato all'articolo che sono possibili duplicati e un essere umano potrebbe decidere se eliminarlo o consentire.

Come ho detto prima sto memorizzando le parole chiave per l'intero articolo, tuttavia mi chiedo se potrei fare lo stesso sul paragrafo; questo significherebbe anche separare ulteriormente i miei dati nel DB, ma sarebbe anche più facile da rilevare (2) nel mio post iniziale.

Sto pensando alla media ponderata tra le statistiche, ma in quale ordine e quali sarebbero le conseguenze ...

    
posta michael 08.10.2012 - 01:41
fonte

4 risposte

4

Esistono molti algoritmi che trattano la similarità dei documenti in PNL. Ecco un documento seminale che descrive vari algoritmi. Anche wikipedia ha una collezione più ampia. Sono favorevole alla misura di Jaro Winkler e l'ho usato per i progetti scolastici dei gradienti nei metodi di clustering aglomerativo.

    
risposta data 08.10.2012 - 02:22
fonte
6

Dai un'occhiata al algoritmo Rabin-Karp . Usa un rolling hash in qualche modo come rsync usa per minimizzare i byte trasmessi durante una sincronizzazione. Regolando la dimensione della finestra che usi per l'hash puoi renderlo più o meno sensibile. R-K è utilizzato, tra le altre cose, per il rilevamento di plagio, che è fondamentalmente alla ricerca di una sorta di dupes.

    
risposta data 08.10.2012 - 06:50
fonte
4

Un primo approccio potrebbe essere quello di rilevare frasi (o qualche altro ragionevole blocco di dati. Prendi quei blocchi e spoglia tutti i dati di mete, html spazio bianco casuale, ritorna ecc. Prendi un MD5 di risultato e memorizzalo in una tabella Potresti quindi abbinare questi blocchi per cercare le corrispondenze.

Se questo non funziona potresti provare n-grammi. Qui hai bisogno di una voce di ogni parola sulla pagina, ma dovrebbe essere in grado di darti delle corrispondenze piuttosto buone.

link

    
risposta data 08.10.2012 - 02:34
fonte
1

Per una matematica matematica esatta, memorizzerei un hash e poi lo confronterei.

Penso che i sistemi usati per gli esami misuri gruppi di parole e quindi la frequenza di gruppi di ogni dimensione. Ad esempio una catena di 30 parole che vengono copiate otterrebbe 5 punti di rischio e 5 occorrenze di 10 catene di parole wold punteggio di 5 punti. Allora avresti una sospensione di 30 punti per 500 parole.

In realtà hai bisogno di un algoritmo semantico in modo che le parole come "anche" e "e" siano analizzate come le stesse.

    
risposta data 08.10.2012 - 13:48
fonte

Leggi altre domande sui tag