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,^[1] 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.

def RabinKarp(s, p):
  n, m = len(s), len(p)
  hp = hash(p)
  for i in range(0, n-m):
    hs = hash(s[i:i+m])
    if hs == hp:
      if s[i:i+m] == p[0:m]:
        return i
  return -1 # not found

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)$ .^[2]

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.

def RabinKarpMulti(s, subs):
  n, m = len(s),  min([len(p) for p in subs])
  hsubs = set()
  for sub in subs:
    hsubs.add(hash(sub[0:m]))
  for i in range(0, n-m):
    hs = hash(s[i:i+m])
    if hs in hsubs and s[i:i+m] in subs:
      return i
  return -1 # not found

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.

Note

^ Cormen et al., p. 990.
^ Cormen et al., pp. 990-994.

Bibliografia

(EN) Richard Karp e Michael O. Rabin, Efficient randomized pattern-matching algorithms, in IBM Journal of Research and Development, XXXI, n. 2, marzo 1987, pp. 249–260, DOI:10.1147/rd.312.0249.
(EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, The Rabin–Karp algorithm, in Introduction to Algorithms, 3ª ed., Cambridge, Massachusetts, MIT Press, 2009, ISBN 978-0-262-53305-8.