Algoritmo di Rabin-Karp

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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 in un testo di lunghezza ha una complessità computazionale al caso medio di in tempo e di in spazio, e di 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 opportunamente definita su stringhe, un testo di caratteri e un pattern di caratteri, per ogni shift = 1, ..., l'algoritmo calcola l'hash della sottostringa e lo confronta con l'hash precalcolato di . Se gli hash differiscono il pattern sicuramente non occorre in posizione , mentre nel caso siano uguali viene eseguito un confronto fra e 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 , 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 . Il precalcolo dell'hash del pattern (riga 3) e il confronto in caso di hit (riga 7) hanno un costo 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 è . Denotando come la cardinalità del codominio della funzione hash e assumendo che gli hash siano uniformemente distribuiti, il valore atteso di collisioni spurie sarà . Assumendo un numero costante di occorrenze valide del pattern nel testo, la complessità in tempo attesa al caso medio dell'algoritmo è , che per è pari a .[2]

Scelta della funzione hash

[modifica | modifica wikitesto]

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 può essere interpretata come numero, associando un valore a ogni carattere (e.g. il rispettivo codice ASCII) come cifra e fissando una certa base (tipicamente un numero primo sufficientemente grande), il valore numerico associato a sarà pari a ; nel caso sia maggiore o uguale alla dimensione dell'alfabeto, tale procedimento è formalmente equivalente ad interpretare la stringa come notazione posizionale di un numero in base .

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

Ricerca di pattern multipli

[modifica | modifica wikitesto]

Per la ricerca simultanea di pattern di lunghezza , 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 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 . Nel caso i pattern abbiano lunghezza diversa, è possibile porre pari alla lunghezza del pattern più breve e calcolare l'hash su caratteri per tutti i pattern, controllando i restanti caratteri solo alla verifica degli hit.

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

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica