Algoritmo di Rabin-Karp

Alcune osservazioni sull'implementazione

Ci si riferirà alla notazione del testo di Cormen et al.

1. Scelta dei valori per d e q.

La costante d denota la cardinalità dell'alfabeto sul quale testo (T) e pattern (P) sono costruiti, a patto che i caratteri siano le cifre da 0 a d-1, in quanto l'algoritmo richiede di eseguire dell'aritmetica sui caratteri, p.e.

p  (d*p + P[i]) mod q

L'implementazione più ovvia di quest'espressione (in Java) è

p = (d*p + P[i]) % q;

La definizione di Java specifica che in contesti interi, un carattere denota il valore del suo codice UNICODE. Se si assume che i testi siano costituiti dai caratteri ascii stampabili, un buon valore per d è allora 256, che è maggiore del codice ascii di qualsiasi carattere ed è anche una potenza di 2, il che permetterebbe ad un buon compilatore ottimizzante di convertire le moltiplicazioni per d in operazioni di shift (più veloci delle moltiplicazioni).

Si deve ora scegliere q primo (per garantire un'aritmetica modulare corretta, cioè affinché Z_q sia un anello) ed inoltre che dq<=2³¹-1 (per evitare overflow ). Con d=256, si può scegliere q= 8388593.

2. Implementazione corretta dell'aritmetica modulare.

L'operazione % di Java non corrisponde correttamente all'operazione mod definita in aritmetica. Infatti, secondo la definizione classica, il mod di un numero (anche negativo) è sempre positivo, mentre è facile verificare che, p.e. -8 % 11 da' come risultato -8.

Questo ha conseguenze spiacevoli nell'implementazione dell'operazione di aggiornamento del valore del testo corrente. In pseudocodice si ha:

t  <-- (d*(t-T[s+1]*h)+T[s+m+1]) mod q

A lezione si è tradotto questo assegnamento in modo scorretto in:

t = (d*(t-T[s+1]*h)+T[s+m+1]) % q;

La versione corretta è:

t=(d*((t+(q-(T[s+1]*h)%q))%q)+T[s+m+1])%q;

Nel seguito si discutono i motivi di questa correzione.

(1) Il primo problema – il piu' grave – è il calcolo della sottrazione

t-T[s+1]*h

Si tratta di un'espressione a valore positivo, perché per come è stato calcolato precedentemente t, si ha t = T[s+1]*h + altri addendi. Siccome però le operazioni sono state effettuate modulo q, non e' garantito che t <= T[s+1]*h, cosicché si può generare un valore negativo scorretto. Per correggere l'operazione, si deve calcolare il valore corretto della sottrazione modulo q, cioè:

- si deve prima prendere il complemento mod q del secondo argomento:

q-(T[s+1]*h)%q

che sarebbe il valore corretto di (- T[s+1]*h) mod q (ovvero del complemento di T[s+1]*h nell'anello Z_q)

- poi si somma:

t+(q-(T[s+1]*h)%q)

(t è già stato calcolato mod q dal codice precedente).

(2) Adesso nasce un secondo problema, dal fatto che se ora si moltiplica direttamente per d:

d*(t+(q-(T[s+1]*h)%q))

si puo' avere overflow . Infatti l'espressione che abbiamo discusso al punto (1) può assumere al massimo il valore (q-1)+q (quando t è al suo massimo q-1 e (T[s+1]*h)%q = 0). Moltiplicando per d, l'espressione può aver valore massimo 2dq - d che non è garantito essere rappresentabile dalla sola richiesta che dq sia rappresentabile. La via d'uscita più semplice è quella di prendere un ulteriore modulo prima della moltiplicazione:

d*( (t+(q-(T[s+1]*h)%q)) % q)

In definitiva l'espressione incriminata deve essere riscritta come:

t=(d*((t+(q-(T[s+1]*h)%q))%q)+T[s+m+1])%q;