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 ${\displaystyle m}$ in un testo di lunghezza ${\displaystyle n}$ ha una complessità computazionale al caso medio di ${\displaystyle O(n+m)}$ in tempo e di ${\displaystyle O(m)}$ in spazio, e di ${\displaystyle 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.

Data una funzione hash ${\displaystyle h}$ opportunamente definita su stringhe, un testo ${\displaystyle s=s_{1},s_{2},\dots ,s_{n}}$ di ${\displaystyle n}$ caratteri e un pattern ${\displaystyle p=p_{1},p_{2},\dots ,p_{m}}$ di ${\displaystyle m}$ caratteri, per ogni shift ${\displaystyle i}$ = 1, ..., ${\displaystyle n-m}$ l'algoritmo calcola l'hash della sottostringa ${\displaystyle s^{i}=s_{i},s_{i+1},\dots ,s_{i+m-1}}$ e lo confronta con l'hash precalcolato di ${\displaystyle p}$. Se gli hash differiscono il pattern sicuramente non occorre in posizione ${\displaystyle i}$, mentre nel caso siano uguali viene eseguito un confronto fra ${\displaystyle p}$ e ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(1)}$. Il precalcolo dell'hash del pattern (riga 3) e il confronto in caso di hit (riga 7) hanno un costo ${\displaystyle 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 è ${\displaystyle O(mn)}$. Denotando come ${\displaystyle q}$ la cardinalità del codominio della funzione hash e assumendo che gli hash siano uniformemente distribuiti, il valore atteso di collisioni spurie sarà ${\displaystyle O(n/q)}$. Assumendo un numero costante ${\displaystyle c}$ di occorrenze valide del pattern nel testo, la complessità in tempo attesa al caso medio dell'algoritmo è ${\displaystyle O(n)+O(m(c+n/q))}$, che per ${\displaystyle q\geq m}$ è pari a ${\displaystyle O(n+m)}$.^[2]

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 ${\displaystyle s=s_{0},s_{1},\dots ,s_{k}}$ può essere interpretata come numero, associando un valore ${\displaystyle x_{i}}$ a ogni carattere ${\displaystyle s_{i}}$ (e.g. il rispettivo codice ASCII) come cifra e fissando una certa base ${\displaystyle q}$ (tipicamente un numero primo sufficientemente grande), il valore numerico associato a ${\displaystyle s}$ sarà pari a ${\displaystyle \textstyle x=\sum _{i=0}^{k}x_{i}\cdot q^{i}}$; nel caso ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x\mod q}$. Nelle implementazioni dell'algoritmo, una scelta usuale per la funzione hash è l'impronta di Rabin.

Per la ricerca simultanea di ${\displaystyle k}$ pattern di lunghezza ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(n+km)}$. Nel caso i pattern abbiano lunghezza diversa, è possibile porre ${\displaystyle m}$ pari alla lunghezza del pattern più breve e calcolare l'hash su ${\displaystyle m}$ caratteri per tutti i pattern, controllando i restanti caratteri solo alla verifica degli hit.

• (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.

• Rabin–Karp Algorithm/Rolling Hash (PDF), su MIT 6.006: Introduction to Algorithms 2011- Lecture Notes, MIT.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica