Diferencia entre revisiones de «Algoritmo Karp-Rabin»
Contenido eliminado Contenido añadido
m Añadiendo la Categoría:Algoritmos epónimos en matemáticas mediante HotCat |
Sin resumen de edición |
||
Línea 1:
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 d(k)=x<sub>k</sub> mod
Para transformar cada subcadena de m caracteres en un entero lo que hacemos es representar los caracteres en una base B que en el planteamiento original coincide con el tamaño del alfabeto. Por tanto el entero x<sub>i</sub> correspondiente a la subcadena de texto C<sub>i</sub>...C<sub>i+m-1</sub> sería:
| |||