Hash generati da Rabin Karp Rolling Hash che non si riflettono sul testo
-
28-10-2019 - |
Domanda
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?
Soluzione
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>