Hash generati da Rabin Karp Rolling Hash che non si riflettono sul testo

Question

Nota: molti possibili duplicati, ma nulla sembra risolvere il mio problema.

Sto lavorando a un rilevamento del plagio basato su MOSS .

Dopo aver implementato con successo un filtro che elimina tutti i dettagli necessari (commenti, punteggiatura, ecc.), ho sottoposto a hashing il contenuto utilizzando un'implementazione Rolling Hash (Rabin Karp)

Tuttavia gli hash che corrispondono in due file di testo del codice sorgente, hanno un testo sottostante molto diverso (nessun plagio e tuttavia gli stessi hash)

L'algoritmo che ho implementato (Ruby) -> (Snippet parziale)

 #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    

C'è un problema con la mia implementazione? O i parametri che ho specificato possono essere in errore?

Prendo radix= 34 (Non sono sicuro che sia il valore giusto, presumo che il testo rimosso conterrà solo alfabeti + alcuni caratteri speciali come '+', '-', '*', '/' quindi una stima approssimativa del totale 34 caratteri)

Immagino che q (primo) sia 101

Sto trattando un problema di collisione? Qualche suggerimento su come affrontare il problema?

Answer 1

Noto che con q= 101, ci sono solo 101 possibili valori hash: 0, 1, 2 ... 100.Hai provato ad aumentare q?Un altro approccio potrebbe essere quello di guardare e vedere se i valori hash sembrano valori scelti a caso entro i possibili valori di 0,1..q-1.

Ovviamente dovresti anche testare il tuo programma su casi in cui ci sono stringhe ripetute da trovare: un errore potrebbe essere un altro sintomo di qualsiasi problema che sta anche causando collisioni, e sarebbe più facile da trovare ed eseguire il debug.

/ p>