Algoritme Karp-Rabin

És un Algoritme de busca de subcadena simple enunciat per Michael Oser Rabin i Richard Manning Karp en 1987. Este algoritme es basa en tractar cada u dels grups de m caràcters del text (sent m el número de símbols del patró) del text com un índex d'una taula de valors hash (la cridarem taula de dispersió), de manera que si la funció hash dels m caràcters del text coincidix en la del patró és possible que hajam trobat un encert. per a verificar-ho cal comparar el text en el patró, ya que la funció hash elegida pot presentar colisions.

La funció hash té la forma $d(k)=x_{k}modd$ a on $d$ és un número primo gran que serà el tamany de la taula de dispersió i $x_k$ es calcula de la forma indicada més avall.

Per a transformar cada subcadena de $m$ caràcters en un sancer lo que fem és representar els caràcters en una base $B$ que en el plantejament original coincidix en el tamany de l'alfabet. Per tant el sancer $x_i$ corresponent a la subcadena de text $C_i\dots C_{i+m-1}$ seria:

x_i=C_i×B^m-1+C_i-1×B^m-2+...+C_i+m-1

podem calcular el valor de $x_{i+1}$ en funció de $x_i$.

x_i+1=x_i×B-C_i×B^m+C^i+m

És dir, si la cadena és un número en base B, el nou valor serà el resultat de multiplicar per la base el valor anterior eliminat el dígit de major pes (ya que no està en la cadena) i afegint com a component de menor pese el valor del nou símbol.

Seguint este plantejament, i depenent de la llongitut del patró, el $x_i$ podria superar el ranc de sancers representable pel computador. Per a que açò no succeïxca s'usa la funció mòdul (restant de la divisió). Com la funció mòdul és associativa, podem calcular el $x_{i+1}$ incrementalmente a partir de cada $x_i$.

Eixemple d'Implementació

• En el llenguage de programació Julia.

Referències

Sergio Talens-Oliag Anàlisis d'algoritmes de busca d'un sol patró. Proyecte Fi de Carrera 1997. O Politècnica de Valéncia