Wykrywanie plagiatu - algorytm przesiewania - zderzenie odcisków palców

Question

Piszę aplikację do wykrywania plagiatu w dużych plikach tekstowych. Po przeczytaniu wielu artykułów o tym zdecydowałem się użyć Winnowing algorithm (z funkcją mieszania karp-Rabina), ale mam z tym pewne problemy.

danych:

Mam dwie proste pliki tekstowe - pierwszy jest większy, drugi jest tylko jeden ustęp z pierwszego.

używany algorytm:

Jest to algorytm, który służy do wyboru i moje odciski palców od wszystkich skrótów.

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)); 
      } 
     } 
    } 
} 

Następnie, aby sprawdzić, czy mamy taki sam tekst w obu plikach, po prostu porównuję odciski palców obu tekstów, aby sprawdzić, czy mamy dopasowania. Aby wykryć plagiat, algorytm musi przyjmować skróty, które zaczynają się dokładnie w tym samym miejscu w tekście, na przykład:

Tekst 1: A uruchom go, sprawdź moje.

Tekst2: Mój bla lol | t^jego mój dasd kurczaka.

Aby uzyskać poprawne hashy, które będą miały te same wartości (co oznacza również, że mamy ten sam tekst), algorytm powinien pobrać odciski palców z miejsc, które wskazałem przez "|" lub '^' (zakładam, że bierzemy 5 znaków do obliczenia skrótu, bez spacji). Nie może wziąć hasha od "|" w tekście 1 i "^" w tekście 2, ponieważ te dwa skróty będą różne i plagiat nie zostanie wykryty.

Problem:

Aby wykryć, czy ustęp ten został skopiowany z numerem tekstowej 1 muszę mieć dwa takie same odciski palców, gdzieś w obu tekstach. Problem polega na tym, że algorytm wybiera odciski palców, które nie pasują do siebie, to znaczy, że po prostu tęsknią, nawet w znacznie większych tekstach.

Pytanie:

Jeżeli masz jakieś pomysły jak mogę poprawić ten algorytm (który faktycznie obniża poprawić algorytm takin odciski palców), że będzie mieć więcej prawdopodobieństwo znalezienia plagiaty?

Myślami:

myślałem o perspektywie winnow funkcja kilka razy, na różnych okiennych rozmiarach (co spowoduje, że zostaną podjęte różne skróty), ale dla dużych tekstów, na którym program ten będzie musiał pracować (jak 2 MB tylko tekst) zajmie to zbyt dużo czasu.

Answer 1

Jeśli masz uruchomione okno, nad którym obliczasz hasz, możesz zaktualizować wartość mieszania w stałym czasie, gdy okno się poruszy. Metoda nazywa się Rabin fingerprint (see also). Powinno to umożliwić obliczenie wszystkich odcisków palców o rozmiarze X w czasie działania O (n) (n jest rozmiarem dokumentu wejściowego). Sądzę, że cytowany artykuł jest rozszerzeniem zaawansowanym tej metody, a gdy zostanie poprawnie zaimplementowany, powinien również dać podobny czas pracy. Kluczem jest zaktualizowanie hasha, aby go nie przeliczyć.