En informática , el algoritmo de Rabin-Karp o el algoritmo de Karp-Rabin es un algoritmo de búsqueda de cadenas creado por Richard M. Karp y Michael O. Rabin ( 1987 ) que utiliza hash para encontrar una coincidencia exacta de una cadena de patrón en un texto. Utiliza un hash rodante 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. Las generalizaciones de la misma idea se pueden utilizar 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 sola coincidencia de un solo patrón, el tiempo esperado del algoritmo es lineal en la longitud combinada del patrón y el texto, aunque su complejidad de tiempo 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 el tiempo y el 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 casos de oraciones del material de origen, ignorando detalles como el caso y la puntuación. Debido a la abundancia de cadenas buscadas, los algoritmos de búsqueda de una sola cadena no son prácticos.
Descripción general
Un algoritmo de coincidencia 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 el número de posiciones es proporcional a la longitud del texto. Por lo tanto, el tiempo en el peor de los casos para tal método 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 coincidencia de cadenas, incluido el algoritmo de Knuth-Morris-Pratt y el algoritmo de búsqueda de cadenas de Boyer-Moore , reducen el tiempo del peor de los casos para la coincidencia de cadenas al extraer más información de cada falta de coincidencia, lo que les permite omitir posiciones del texto que están garantizados para no coincidir con el patrón. En cambio, el algoritmo Rabin-Karp logra su aceleración mediante el uso de una función hash para realizar rápidamente una verificación aproximada para cada posición, y luego solo realiza una comparación exacta 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: es muy poco probable que las cadenas que son desiguales tengan valores hash iguales. El algoritmo de 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 , 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 rodante , una función hash cuyo valor se puede actualizar rápidamente desde 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
El algoritmo es como se muestra:
función RabinKarp ( cadena s [ 1 .. n ], patrón de cadena [ 1 .. m ]) hpatrón : = 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 ] regreso yo retorno no encontrado
Las líneas 2, 4 y 6 requieren cada una de O ( m ) tiempo. 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 ingenuamente el valor hash para la subcadena s[i+1..i+m]
requiere O ( m ) tiempo 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 los algoritmos sencillos de coincidencia de cadenas. Para la velocidad, el hash debe calcularse en tiempo constante. El truco es que la variable hs
ya 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, el cálculo de los valores hash sucesivos será rápido.
El truco se puede aprovechar utilizando un hash rodante . Un hash rodante es una función hash especialmente diseñada para permitir esta operación. Una función de hash rodante trivial (pero no muy buena) simplemente agrega los valores de cada carácter en la subcadena. Esta fórmula hash rodante puede calcular el siguiente valor hash 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 instrucción 5 se ejecute con más frecuencia que otras funciones hash rodantes más sofisticadas, como las que se describen en la siguiente sección.
Un buen rendimiento requiere una buena función hash para los datos encontrados. Si el hash es deficiente (como producir el mismo valor hash para cada entrada), entonces la línea 6 se ejecutará O ( n ) veces (es decir, en cada iteración del ciclo). Debido a que la comparación carácter por carácter de cadenas con longitud m toma O (m) tiempo, todo el algoritmo toma un tiempo O ( mn ) en el peor de los casos .
Función hash utilizada
La clave del rendimiento del algoritmo de Rabin-Karp es el cálculo eficiente de los valores hash de las subcadenas sucesivas del texto. La huella dactilar de Rabin es una función de hash rodante popular y eficaz. La función hash descrita aquí no es una huella digital de Rabin, pero funciona igualmente bien. Trata cada subcadena como un número en alguna base, la base suele ser el tamaño del conjunto de caracteres.
Por ejemplo, si la subcadena es "hi", la base es 256 y el módulo principal es 101, entonces el valor hash sería
[(104 × 256)% 101 + 105]% 101 = 65 ( ASCII de 'h' es 104 y de 'i' es 105)
'%' es 'mod' o módulo, o el resto después de la división de enteros, operador
Técnicamente, este algoritmo solo 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 una discusión mucho más detallada. El beneficio esencial que se logra al usar un hash rodante como la huella digital de Rabin es que es posible calcular el valor hash de la siguiente subcadena a partir de la anterior haciendo solo un número constante de operaciones, independientemente de la longitud 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
Luego podemos calcular el hash de la siguiente subcadena, "bra", del hash de "abr" restando el número agregado para la primera 'a' de "abr", es decir, 97 × 256 2 , multiplicando por la base y sumando para la última a de "sujetador", es decir, 97 × 256 0 . Al igual que:
// antiguo hash (-ve evitador) * antiguo 'a' desplazamiento base izquierda desplazamiento base nuevo 'a' módulo principalhash ("sostén") = [(4 + 101 - 97 * [(256% 101) * 256]% 101) * 256 + 97]% 101 = 30
* (-ve evitador) = "evitador de subdesbordamiento". Necesario si se utilizan enteros sin signo para los cálculos. Porque conocemos todos los hashes para el módulo principal $ p $, podemos asegurar que no haya subdesbordamiento agregando p al antiguo hash antes de restar el valor correspondiente a la antigua 'a' (mod p).
el último '* 256' es el desplazamiento del hash restado a la izquierda
aunque ((256% 101) * 256)% 101 es lo mismo que 256 2 % 101, para evitar el desbordamiento de los máximos enteros cuando la cadena del 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 calcula previamente en un bucle, modulando el resultado en cada iteración
Si estamos haciendo coincidir 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 = 30
Si las subcadenas en cuestión son largas, este algoritmo logra grandes ahorros en comparación con muchos otros esquemas de hash.
Teóricamente, existen otros algoritmos que podrían proporcionar un recálculo conveniente, por ejemplo, multiplicar los valores ASCII de todos los caracteres para 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. Sin embargo, la limitación es el tamaño limitado del tipo de datos enteros y la necesidad de utilizar aritmética modular para reducir los resultados hash (consulte el artículo sobre la función hash ). Mientras tanto, las funciones hash ingenuas no producen grandes números rápidamente, pero, al igual que agregar valores ASCII, es probable que provoquen muchas colisiones hash y, por lo tanto, ralenticen el algoritmo. Por tanto, la función hash descrita suele ser la preferida en el algoritmo de Rabin-Karp.
Búsqueda de múltiples patrones
El algoritmo de Rabin-Karp es inferior para la búsqueda de un solo patrón que el algoritmo Knuth-Morris-Pratt , el algoritmo de búsqueda de cadenas de Boyer-Moore y otros algoritmos de búsqueda de cadenas de un solo patrón más rápidos debido a su comportamiento lento en el peor de los casos. Sin embargo, es un algoritmo de elección [¿ según quién? ] para la búsqueda de múltiples patrones .
Para encontrar cualquiera de un gran número, digamos k , patrones de longitud fija en un texto, una variante simple del algoritmo Rabin-Karp usa un filtro Bloom o una estructura de datos de conjunto 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 cadenas subs , m ) : set hsubs : = emptySet 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 regreso yo hs : = hash ( s [ i + 1 .. i + m ]) retorno no encontrado
Suponemos que todas las subcadenas tienen una longitud fija m .
Una forma ingenua de buscar k patrones es repetir una búsqueda de patrón único que toma O ( n + m ) tiempo, totalizando O ( (n + m) k ) tiempo. Por el contrario, el algoritmo anterior puede encontrar todos los k patrones en el tiempo esperado O ( n + km ), asumiendo que una verificación de la tabla hash funciona en el tiempo esperado O (1).
Referencias
- Karp, Richard M .; Rabin, Michael O. (marzo de 1987). "Algoritmos de coincidencia de patrones aleatorios eficientes". Revista de investigación y desarrollo de IBM . 31 (2): 249–260. CiteSeerX 10.1.1.86.9502 . doi : 10.1147 / rd.312.0249 .
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (1 de septiembre de 2001) [1990]. "El algoritmo de Rabin-Karp". Introducción a los algoritmos (2ª ed.). Cambridge, Massachusetts : MIT Press. págs. 911–916. ISBN 978-0-262-03293-3.
- Candan, K. Selçuk; Sapino, Maria Luisa (2010). Gestión de datos para recuperación multimedia . Prensa de la Universidad de Cambridge. págs. 205–206. ISBN 978-0-521-88739-7. (para la extensión del filtro Bloom)
enlaces externos
- "Algoritmo Rabin-Karp / Rolling Hash" (PDF) . MIT 6.006: Introducción a los algoritmos 2011- Notas de la conferencia . MIT.