Hashes generados por Rabin Karp Rolling Hash que no se reflejan en el texto

Question

Nota: muchos posibles duplicados, pero nada parece resolver mi problema.

Estoy trabajando en una detección de plagio basada en MOSS .

Después de implementar con éxito un filtro que elimina todos los detalles necesarios (comentarios, puntuaciones, etc.), hago un hash en el contenido usando una implementación de Rolling Hash (Rabin Karp)

Sin embargo, los hash que coinciden en dos archivos de texto de código fuente, tienen un texto subyacente muy diferente (sin plagio y sin embargo los mismos hash)

El algoritmo que implementé (Ruby) -> (Fragmento parcial)

 #Preprocessing from RobinKarp Algorithm
  for c in 0...k do
    text_hash=(radix*text_hash+text_to_process[c].ord)%q
  end

  #Main loop
  for c in 0...loop do   
        text_hash=((radix*text_hash-(text_to_process[c].ord)*highorder)+(text_hash[c+k].ord))%q    

¿Hay algún problema con mi implementación? ¿O los parámetros que especifico pueden tener fallas?

Tomo radix= 34 (No estoy seguro de si es el valor correcto, supongo que el texto eliminado solo contendrá alfabetos + algunos caracteres especiales como '+', '-', '*', '/' por lo que una estimación aproximada del total 34 personajes)

Supongo que q (principal) es 101

¿Es este un problema de colisión con el que estoy lidiando? ¿Algún consejo sobre cómo abordar el problema?

Answer 1

Observo que con q= 101, solo hay 101 valores hash posibles: 0, 1, 2 ... 100.¿Ha intentado aumentar q?Otro enfoque sería mirar y ver si los valores hash parecen ser valores elegidos al azar dentro de los valores posibles de 0,1..q-1.

Por supuesto, también debe probar su programa en los casos en que haya cadenas repetidas para que las encuentre; una falla, podría haber otro síntoma de cualquier problema que también esté causando colisiones, y sería más fácil de encontrar y depurar.