En informática , el algoritmo Rabin-Karp o algoritmo Karp-Rabin es un algoritmo de búsqueda de cadenas creado por Richard M. Karp y Michael O. Rabin (1987) que utiliza un algoritmo hash para encontrar una coincidencia exacta de una cadena de patrones en un texto. Utiliza un algoritmo hash continuo para filtrar rápidamente las posiciones del texto que no pueden coincidir con el patrón y luego busca una coincidencia en las posiciones restantes. Se pueden utilizar generalizaciones de la misma idea para encontrar más de una coincidencia de un solo patrón o para encontrar coincidencias para más de un patrón.
Para encontrar una única coincidencia de un único patrón, el tiempo esperado del algoritmo es lineal en la longitud combinada del patrón y el texto, aunque su complejidad temporal en el peor de los casos es el producto de las dos longitudes. Para encontrar múltiples coincidencias, el tiempo esperado es lineal en las longitudes de entrada, más la longitud combinada de todas las coincidencias, que podría ser mayor que lineal. Por el contrario, el algoritmo Aho-Corasick puede encontrar todas las coincidencias de múltiples patrones en el peor de los casos, en un tiempo y espacio lineal en la longitud de entrada y el número de coincidencias (en lugar de la longitud total de las coincidencias).
Una aplicación práctica del algoritmo es la detección de plagio . Dado el material de origen, el algoritmo puede buscar rápidamente en un artículo ejemplos de oraciones del material de origen, ignorando detalles como mayúsculas y minúsculas y puntuación. Debido a la abundancia de cadenas buscadas, los algoritmos de búsqueda de una sola cadena son poco prácticos.
Un algoritmo de comparación de cadenas ingenuo compara el patrón dado con todas las posiciones en el texto dado. Cada comparación lleva un tiempo proporcional a la longitud del patrón, y la cantidad de posiciones es proporcional a la longitud del texto. Por lo tanto, el tiempo en el peor de los casos para un método de este tipo es proporcional al producto de las dos longitudes. En muchos casos prácticos, este tiempo se puede reducir significativamente acortando la comparación en cada posición tan pronto como se encuentre una discrepancia, pero esta idea no puede garantizar ninguna aceleración.
Varios algoritmos de comparación de cadenas, incluidos el algoritmo Knuth–Morris–Pratt y el algoritmo de búsqueda de cadenas Boyer–Moore , reducen el tiempo de comparación de cadenas en el peor de los casos extrayendo más información de cada discrepancia, lo que les permite omitir posiciones del texto que se garantiza que no coinciden con el patrón. El algoritmo Rabin–Karp, en cambio, logra su aceleración utilizando una función hash para realizar rápidamente una verificación aproximada para cada posición y luego realizar una comparación exacta solo en las posiciones que pasan esta verificación aproximada.
Una función hash es una función que convierte cada cadena en un valor numérico, llamado su valor hash ; por ejemplo, podríamos tener hash("hello")=5. Si dos cadenas son iguales, sus valores hash también son iguales. Para una función hash bien diseñada, lo inverso es cierto, en un sentido aproximado: las cadenas que no son iguales tienen muy pocas probabilidades de tener valores hash iguales. El algoritmo Rabin-Karp procede calculando, en cada posición del texto, el valor hash de una cadena que comienza en esa posición con la misma longitud que el patrón. Si este valor hash es igual al valor hash del patrón, realiza una comparación completa en esa posición.
Para que esto funcione bien, la función hash debe seleccionarse aleatoriamente de una familia de funciones hash que es poco probable que produzcan muchos falsos positivos , es decir, posiciones del texto que tienen el mismo valor hash que el patrón pero que en realidad no coinciden con el patrón. Estas posiciones contribuyen al tiempo de ejecución del algoritmo innecesariamente, sin producir una coincidencia. Además, la función hash utilizada debe ser un hash continuo , una función hash cuyo valor se puede actualizar rápidamente de cada posición del texto a la siguiente. Volver a calcular la función hash desde cero en cada posición sería demasiado lento.
El algoritmo es el siguiente:
función RabinKarp ( cadena s [ 1. . n ], cadena patrón [ 1. . m ]) hpattern := hash ( patrón [ 1. . m ]); para i de 1 a n - m + 1 hs := hash ( s [ i .. i + m - 1 ]) si hs = hpattern si s [ i .. i + m - 1 ] = patrón [ 1. . m ] devuelvo yo retorno no encontradoLas líneas 2, 4 y 6 requieren cada una un tiempo de O ( m ). Sin embargo, la línea 2 solo se ejecuta una vez y la línea 6 solo se ejecuta si los valores hash coinciden, lo que es poco probable que suceda más de unas pocas veces. La línea 5 se ejecuta O( n ) veces, pero cada comparación solo requiere un tiempo constante, por lo que su impacto es O( n ). El problema es la línea 4.
Calcular de forma ingenua el valor hash de la subcadena s[i+1..i+m]requiere un tiempo O ( m ) porque se examina cada carácter. Dado que el cálculo hash se realiza en cada bucle, el algoritmo con un cálculo hash ingenuo requiere un tiempo O (mn), la misma complejidad que un algoritmo de comparación de cadenas sencillo. Para lograr velocidad, el hash debe calcularse en tiempo constante. El truco es que la variable hsya contiene el valor hash anterior de s[i..i+m-1]. Si ese valor se puede utilizar para calcular el siguiente valor hash en tiempo constante, entonces el cálculo de valores hash sucesivos será rápido.
El truco se puede aprovechar utilizando un hash continuo . Un hash continuo es una función hash especialmente diseñada para permitir esta operación. Una función hash continua trivial (pero no muy buena) simplemente suma los valores de cada carácter en la subcadena. Esta fórmula hash continua puede calcular el siguiente valor hash a partir del valor anterior en tiempo constante:
s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
Esta función simple funciona, pero dará como resultado que la declaración 5 se ejecute con más frecuencia que otras funciones hash continuas más sofisticadas, como las que se analizan en la siguiente sección.
Un buen rendimiento requiere una buena función hash para los datos encontrados. Si la función hash es deficiente (por ejemplo, si produce el mismo valor hash para cada entrada), entonces la línea 6 se ejecutaría O ( n ) veces (es decir, en cada iteración del bucle). Debido a que la comparación carácter por carácter de cadenas con una longitud m lleva O (m) tiempo, todo el algoritmo lleva un tiempo O ( mn ) en el peor de los casos.
La clave del rendimiento del algoritmo Rabin-Karp es el cálculo eficiente de los valores hash de las subcadenas sucesivas del texto. La huella de Rabin es una función hash rotativa popular y eficaz. La función hash descrita aquí no es una huella de Rabin, pero funciona igualmente bien. Trata cada subcadena como un número en alguna base, siendo la base normalmente el tamaño del conjunto de caracteres.
Por ejemplo, si la subcadena es "hi", la base es 256 y el módulo primo es 101, entonces el valor hash sería
[(104 × 256 ) % 101 + 105] % 101 = 65 ( El ASCII de 'h' es 104 y el de 'i' es 105)
'%' es 'mod' o módulo, o resto después de la división de enteros, operador
Técnicamente, este algoritmo sólo es similar al número verdadero en una representación de sistema no decimal, ya que, por ejemplo, podríamos tener la "base" menor que uno de los "dígitos". Consulte la función hash para obtener una explicación mucho más detallada. El beneficio esencial que se logra al usar un hash continuo como la huella de Rabin es que es posible calcular el valor hash de la siguiente subcadena a partir de la anterior haciendo sólo un número constante de operaciones, independientemente de las longitudes de las subcadenas.
Por ejemplo, si tenemos el texto "abracadabra" y estamos buscando un patrón de longitud 3, el hash de la primera subcadena, "abr", usando 256 como base y 101 como módulo principal es:
// ASCII a = 97, b = 98, r = 114.hash("abr") = [ ( [ ( [ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ] % 101 = 4
Podemos entonces calcular el hash de la siguiente subcadena, "bra", a partir del hash de "abr" restando el número añadido para la primera 'a' de "abr", es decir, 97 × 256 2 , multiplicando por la base y sumando para la última a de "bra", es decir, 97 × 256 0 . De la siguiente manera:
// hash antiguo (evitador -ve)* desplazamiento de base izquierdo antiguo 'a' cambio de base nuevo módulo primo 'a'hash("sujetador") = [ ( 4 + 101 - 97 * [(256%101)*256] % 101 ) * 256 + 97 ] % 101 = 30* (-ve avoider) = "underflow avoider". Necesario si se utilizan números enteros sin signo para los cálculos. Como conocemos todos los hashes para el módulo primo $p$, podemos asegurarnos de que no haya desbordamiento sumando p al hash anterior antes de restar el valor correspondiente al antiguo 'a' (mod p).
El último '* 256' es el desplazamiento del hash restado hacia la izquierda.
Aunque ((256%101)*256)%101 es lo mismo que 256 2 % 101, para evitar desbordar los máximos enteros cuando la cadena de patrón es más larga (por ejemplo, 'Rabin-Karp' tiene 10 caracteres, 256 9 es el desplazamiento sin modulación), el desplazamiento base de la longitud del patrón se precalcula en un bucle, modulando el resultado en cada iteración.
Si buscamos la cadena de búsqueda "bra", utilizando un cálculo similar de hash("abr"),
hash'("sujetador") = [ ( [ ( [ ( 98 × 256) %101 + 114] % 101 ) × 256 ] % 101) + 97 ] % 101 = 30Si las subcadenas en cuestión son largas, este algoritmo consigue grandes ahorros en comparación con muchos otros esquemas de hash.
En teoría, existen otros algoritmos que podrían proporcionar un recálculo conveniente, por ejemplo, multiplicar los valores ASCII de todos los caracteres de modo que el cambio de subcadena solo implique dividir el hash anterior por el valor del primer carácter y luego multiplicarlo por el valor del último carácter nuevo. La limitación, sin embargo, es el tamaño limitado del tipo de datos entero y la necesidad de utilizar aritmética modular para reducir la escala de los resultados del hash (consulte el artículo sobre la función hash ). Mientras tanto, las funciones hash ingenuas no producen números grandes rápidamente, sino que, al igual que la suma de valores ASCII, es probable que provoquen muchas colisiones de hash y, por lo tanto, ralenticen el algoritmo. Por lo tanto, la función hash descrita suele ser la preferida en el algoritmo de Rabin-Karp.
El algoritmo Rabin–Karp es inferior para la búsqueda de patrones únicos al algoritmo Knuth–Morris–Pratt , al algoritmo de búsqueda de cadenas Boyer–Moore y a otros algoritmos de búsqueda de cadenas de patrones únicos más rápidos debido a su comportamiento lento en el peor de los casos. Sin embargo, es un algoritmo útil para la búsqueda de múltiples patrones .
Para encontrar cualquiera de un gran número, digamos k , de patrones de longitud fija en un texto, una variante simple del algoritmo Rabin-Karp utiliza un filtro Bloom o una estructura de datos establecida para verificar si el hash de una cadena dada pertenece a un conjunto de valores hash de los patrones que estamos buscando:
función RabinKarpSet ( cadena s [ 1. . n ] , conjunto de subcadenas , m ) : establecer hsubs := conjunto vacío foreach sub en subs Insertar hash ( sub [ 1. . m ]) en hsubs hs := hash ( s [ 1 . . m ]) para i de 1 a n - m + 1 si hs ∈ hsubs y s [ i .. i + m - 1 ] ∈ subs devuelvo yo hs := hash ( s [ i + 1 . . i + m ]) retorno no encontradoSuponemos que todas las subcadenas tienen una longitud fija m .
Una forma ingenua de buscar k patrones es repetir una búsqueda de un solo patrón que toma O ( n+m ) tiempo, totalizando en O ( (n+m)k ) tiempo. En contraste, el algoritmo anterior puede encontrar todos los k patrones en O ( n + km ) tiempo esperado, suponiendo que una verificación de tabla hash funciona en O (1) tiempo esperado.