Algoritmo di Rabin-Karp
# Algoritmo di Rabin-Karp

L'algoritmo di Rabin–Karp è un algoritmo di pattern matching su stringhe proposto da Michael O. Rabin e Richard M. Karp nel 1987. Utilizza una funzione di hash per individuare possibili occorrenze del pattern, e per la ricerca di un pattern di lunghezza $m$ in un testo di lunghezza $n$ ha una complessità computazionale al caso medio di $O(n+m)$ in tempo e di $O(m)$ in spazio, e di $O(nm)$ in tempo al caso pessimo.

L'algoritmo può essere generalizzato per la ricerca simultanea di pattern multipli nello stesso testo. Nella ricerca di un singolo pattern è efficiente in pratica, ma ha una complessità al caso pessimo superiore ad altri algoritmi come quelli di Knut-Morris-Pratt, Aho-Corasick e Boyer-Moore.

## Algoritmo

Data una funzione hash $h$ opportunamente definita su stringhe, un testo $s=s_{1},s_{2},\dots ,s_{n}$ di $n$ caratteri e un pattern $p=p_{1},p_{2},\dots ,p_{m}$ di $m$ caratteri, per ogni shift $i$ = 1, ..., $n-m$ l'algoritmo calcola l'hash della sottostringa $s^{i}=s_{i},s_{i+1},\dots ,s_{i+m-1}$ e lo confronta con l'hash precalcolato di $p$. Se gli hash differiscono il pattern sicuramente non occorre in posizione $i$, mentre nel caso siano uguali viene eseguito un confronto fra $p$ e $s^{i}$ per escludere che si tratti di una collisione spuria.

Impiegando una generica funzione hash alla riga 5, il cui costo è al meglio $O(m)$, l'algoritmo non è più efficiente di una ricerca naïve. Se invece si usa una funzione rolling hash, l'istruzione alla riga 5 può essere eseguita in tempo costante $O(1)$. Il precalcolo dell'hash del pattern (riga 3) e il confronto in caso di hit (riga 7) hanno un costo $O(m)$ in tempo. Al caso pessimo, quando ogni singolo shift causa una collisione richiedente una verifica e l'algoritmo degenera in una ricerca naïve, la complessità in tempo è $O(mn)$. Denotando come $q$ la cardinalità del codominio della funzione hash e assumendo che gli hash siano uniformemente distribuiti, il valore atteso di collisioni spurie sarà $O(n/q)$. Assumendo un numero costante $c$ di occorrenze valide del pattern nel testo, la complessità in tempo attesa al caso medio dell'algoritmo è $O(n)+O(m(c+n/q))$, che per $q\geq m$ è pari a $O(n+m)$.

## Scelta della funzione hash

La scelta della funzione hash è determinante per l'efficienza dell'algoritmo, in particolare l'uso di una funzione rolling hash è fondamentale per calcolare l'hash ad ogni shift in tempo costante. Una stringa $s=s_{0},s_{1},\dots ,s_{k}$ può essere interpretata come numero, associando un valore $x_{i}$ a ogni carattere $s_{i}$ (e.g. il rispettivo codice ASCII) come cifra e fissando una certa base $q$ (tipicamente un numero primo sufficientemente grande), il valore numerico associato a $s$ sarà pari a $\textstyle x=\sum _{i=0}^{k}x_{i}\cdot q^{i}$; nel caso $q$ sia maggiore o uguale alla dimensione dell'alfabeto, tale procedimento è formalmente equivalente ad interpretare la stringa come notazione posizionale di un numero in base $q$.

Una funzione hash molto semplice può essere definita reinterpretando la stringa come numero nella maniera appena descritta, e quindi usando come hash il valore $x\mod q$. Nelle implementazioni dell'algoritmo, una scelta usuale per la funzione hash è l'impronta di Rabin.

## Ricerca di pattern multipli

Per la ricerca simultanea di $k$ pattern di lunghezza $m$, l'algoritmo può essere generalizzato conservando in una hash table gli hash di tutti i pattern, che permette di verificare ad ogni iterazione, in tempo costante, se l'hash della sottostringa $s$ corrisponde a quello di qualche pattern.

La complessità in tempo dell'algoritmo al caso medio diventa $O(n+km)$. Nel caso i pattern abbiano lunghezza diversa, è possibile porre $m$ pari alla lunghezza del pattern più breve e calcolare l'hash su $m$ caratteri per tutti i pattern, controllando i restanti caratteri solo alla verifica degli hit.

