Edición de «Algoritmo Karp-Rabin»

Es un [[Algoritmos de búsqueda de subcadenas|Algoritmo de búsqueda de subcadenas]] simple enunciado por  [[Michael Oser Rabin]] y [[Richard Manning  Karp]] en 1987.<ref>Karp, R. M. y Rabin, M. O.. Efficient Randomized Pattern Matching Algorithms. IBM J. Res.Develop.31 (2), 249–260 (1987)</ref> Este algoritmo se basa en tratar cada uno de los grupos de m caracteres del texto (siendo m el número de símbolos del patrón) del texto como un índice de una tabla de valores hash (la llamaremos tabla de dispersión), de manera que si la [[función hash]] de los m caracteres del texto coincide con la del patrón es posible que hayamos encontrado un acierto. para verificarlo hay que comparar el texto con el patrón, ya que la [[función hash]] elegida puede presentar colisiones.

La función hash tiene la forma <math>d(k) = x_k \mod d</math>  donde <math>d</math> es un número primo grande que será el tamaño de la tabla de dispersión y <math>x_k</math> se calcula de la forma indicada más abajo.

Para transformar cada subcadena de <math>m</math> caracteres en un entero lo que hacemos es representar los caracteres en una base <math>B</math> que en el planteamiento original coincide con el tamaño del alfabeto. Por tanto el entero <math>x_i</math> correspondiente a la subcadena de texto <math>C_i \ldots C_{i+m-1}</math> sería:

x<sub>i</sub>=C<sub>i</sub>×B<sup>m-1</sup>+C<sub>i-1</sub>×B<sup>m-2</sup>+...+C<sub>i+m-1</sub>

podemos calcular el valor de <math>x_{i+1}</math> en función de <math>x_i</math>.

x<sub>i+1</sub>=x<sub>i</sub>×B-C<sub>i</sub>×B<sup>m</sup>+C<sup>i+m</sup>

Es decir, si la cadena es un número en base B, el nuevo valor será el resultado de multiplicar por la base el valor anterior eliminado el dígito de mayor peso (ya que no está en la cadena) y añadiendo como componente de menor peso el valor del nuevo símbolo.

Siguiendo este planteamiento, y dependiendo de la longitud del patrón, el <math>x_i</math> podría superar el rango de enteros representable por el computador. Para que esto no suceda se usa la función módulo (resto de la división). Como la función módulo es asociativa, podemos calcular el <math>x_{i+1}</math> incrementalmente a partir de cada <math>x_i</math>.

'''Ejemplo de Implementación'''

* En el lenguaje de programación [https://github.com/camilochs/thinking-algorithms/blob/master/karp-rabin/karp-rabin-algorithm.jl Julia].

== Referencias ==
{{listaref}}
Sergio Talens-Oliag [https://www.uv.es/sto/pfc/mpfc.ps.gz Análisis de algoritmos de búsqueda de un solo patrón]. Proyecto Fin de Carrera 1997. U Politécnica de Valencia

{{Control de autoridades}}
[[Categoría:Algoritmos de búsqueda]]
[[Categoría:Algoritmos epónimos en matemáticas|Karp-Rabin]]
[[Categoría:Introducciones relacionadas a la ciencia de la computación de 1987]]