Rilevamento di plagio - algoritmo di vagliatura - scontro di impronte digitali

Question

Scrivo applicazione per il rilevamento di plagio in file di testo di grandi dimensioni. Dopo aver letto molti articoli su di esso ho deciso di usare Winnowing algorithm (con la funzione di hash rolling di Karp-Rabin), ma ho qualche problema con esso.

dati:

Ho due semplici file di testo - primo è più grande, secondo è solo un paragrafo dal primo.

algoritmo utilizzato:

Questo è algoritmo che ho usato per selezionare le mie impronte digitali da tutti gli hash.

void winnow(int w /*window size*/) { 
    // circular buffer implementing window of size w 
    hash_t h[w]; 
    for (int i=0; i<w; ++i) h[i] = INT_MAX; 
    int r = 0; // window right end 
    int min = 0; // index of minimum hash 
    // At the end of each iteration, min holds the 
    // position of the rightmost minimal hash in the 
    // current window. record(x) is called only the 
    // first time an instance of x is selected as the 
    // rightmost minimal hash of a window. 
    while (true) { 
     r = (r + 1) % w; // shift the window by one 
     h[r] = next_hash(); // and add one new hash, if hash = -1, then it's end of file 
     if(h[r] == -1) 
      break; 
     if (min == r) { 
      // The previous minimum is no longer in this 
      // window. Scan h leftward starting from r 
      // for the rightmost minimal hash. Note min 
      // starts with the index of the rightmost 
      // hash. 
      for(int i=(r-1)%w; i!=r; i=(i-1+w)%w) 
       if (h[i] < h[min]) min = i; 
        record(h[min], global_pos(min, r, w)); 
     } else { 
      // Otherwise, the previous minimum is still in 
      // this window. Compare against the new value 
      // and update min if necessary. 
      if (h[r] <= h[min]) { // (*) 
       min = r; 
       record(h[min], global_pos(min, r, w)); 
      } 
     } 
    } 
} 

Avanti, per rilevare se abbiamo lo stesso testo in entrambi i file ho appena confrontare le impronte digitali di entrambi i textes per controllare se abbiamo partite. Quindi per rilevare il plagio, l'algoritmo deve prendere degli hash che inizieranno esattamente nello stesso punto nel testo, ad esempio:

Testo1: Un do run | t^his my check your.

Testo2: Il mio bla lol | t^è il mio pollo dasd.

Per ottenere gli hash corretti, che avranno gli stessi valori (che significa anche che abbiamo lo stesso testo), l'algoritmo dovrebbe prendere le impronte digitali dai punti che ho indicato con '|' o '^' (presumo che prendiamo 5 caratteri per calcolare l'hash, senza spazi). Non può accettare hash da '|' nel testo 1 e '^' nel testo 2 perché questi due hash saranno diversi e il plagio non verrà rilevato.

Problema:

per rilevare se questo paragrafo è stato copiato dal numero di testo 1 devo avere due stesse impronte digitali, da qualche parte in entrambi i testi. Il problema è che l'algoritmo sceglie le impronte digitali, che non si adattano a vicenda, voglio dire che mancano, anche in testi molto più grandi.

Domanda:

Hai qualche idea di come posso migliorare questo algoritmo (che in realtà porta giù per correggere l'algoritmo di Takin impronte digitali), che avrebbe più probabilità di trovare plagi?

I miei pensieri:

ho pensato di correre vagliare volte la funzione di coppia, per le diverse dimensioni della finestra (che farà sì che le diverse hash sarebbero prese), ma per i grandi testi sui quali questo programma dovrà lavorare (come 2MB solo testo) questo richiederà troppo tempo.

Answer 1

Se la finestra corrente su cui si sta calcolando l'hash, è possibile aggiornare il valore di hash in tempo costante quando si sposta la finestra. Il metodo è chiamato Rabin fingerprint (see also). Ciò dovrebbe consentire di calcolare tutte le impronte digitali di dimensione X in tempo di esecuzione O (n) (n è una dimensione di un documento di input). Immagino che la carta che citi sia un'estensione avanzata di questo metodo e, se implementata correttamente, dovrebbe anche darti un tempo di esecuzione simile. La chiave è aggiornare l'hash non ricalcolarlo.