Detección de plagio - Algoritmo de arrastre - Choque de huellas dactilares

Question

Escribo aplicaciones para la detección de plagio en archivos de texto grande. Después de leer muchos artículos al respecto, decidí usar Winnowing algorithm (con la función hash rodante Karp-Rabin), pero tengo algunos problemas con él.

datos:

Tengo dos archivos de texto simple - primero es más grande, en segundo lugar es sólo un párrafo de la primera.

algoritmo utilizado:

Este es el algoritmo que he utilizado para seleccionar las huellas digitales de todos los hashes.

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

A continuación, para detectar si tenemos un mismo texto en ambos archivos i Basta con comparar las huellas dactilares de ambos textes a comprobar si tenemos partidos. Para detectar plagio, el algoritmo debe tomar hashes que comenzarán exactamente en el mismo lugar en el texto, por ejemplo:

Text1: A ejecutar | t^his my check your.

Text2: Mi bla lol | t^his my dasd chicken.

Para obtener valores hash correctos, que tendrán los mismos valores (lo que también significa que tenemos el mismo texto), el algoritmo debe tomar huellas dactilares de los lugares señalados por '|' o '^' (supongo que tomamos 5 caracteres para calcular hash, sin espacios). No puede tomar hash de '|' en el texto 1 y '^' en el texto 2 porque estos dos hashes serán diferentes y no se detectará el plagio.

Problema:

para detectar si este párrafo fue copiado de texto número 1 i tiene que tener dos mismas huellas digitales, en algún lugar en ambos textos. El problema es que el algoritmo elige las huellas dactilares, que no se ajustan unas a otras, quiero decir que se pierden, incluso en textos mucho más grandes.

Pregunta:

¿Tienes alguna idea de cómo puedo mejorar este algoritmo (que en realidad lleva hacia abajo para corregir el algoritmo de huellas dactilares Takin), que tendría más probabilidad de encontrar plagios?

Mis pensamientos:

pensé en funcionamiento aventar veces función par, para diferentes tamaños de ventana (lo que provocará que se tomarían diferentes hashes), pero para textos largos en los que este programa va a tener que trabajar (como 2 MB de texto) esto llevará demasiado tiempo.

Answer 1

Si tiene una ventana en ejecución sobre la que está calculando el hash, puede actualizar el valor de hash en tiempo constante cuando se mueve la ventana. El método se llama Rabin fingerprint (see also). Esto debería permitirle calcular todas las huellas dactilares de tamaño X en O (n) tiempo de ejecución (n es el tamaño de un documento de entrada). Supongo que el documento que cita es una extensión avanzada de este método y, cuando se implementa correctamente, también debería darle un tiempo de ejecución similar. La clave es actualizar el hash no volver a calcularlo.