Algoritmo di Rabin-Karp

LTemplate:'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 (n m)$ 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 (m n)$ . 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 $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 + k m)$ . 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

↑ Template:Cita.
↑ Template:Cita.

Bibliografia

Collegamenti esterni

Template:Cita web

Template:Portale

[1] Template:Cita.

[2] Template:Cita.

[1]

[2]