Algoritmo de Rabin-Karp

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 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 coincidencias 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 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 duraciones de entrada, más la duración combinada de todas las coincidencias, que podría ser mayor que lineal. Por el contrario, el algoritmo de Aho-Corasick puede encontrar todas las coincidencias de múltiples patrones en el peor de los casos en el tiempo y el espacio lineales 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 fuente, el algoritmo puede buscar rápidamente en un artículo ejemplos de oraciones del material fuente, 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 ingenuo algoritmo de coincidencia de cadenas compara el patrón dado con todas las posiciones en el texto dado. Cada comparación toma 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 peor de los casos para dicho método es proporcional al producto de las dos longitudes. En muchos casos prácticos, este tiempo puede reducirse 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 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 se garantiza que no coinciden 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 valor hash; por ejemplo, podríamos tener hash("hola")=5. Si dos cadenas son iguales, sus valores hash también son iguales. Para una función hash bien diseñada, lo contrario es cierto, en un sentido aproximado: es muy poco probable que las cadenas que son desiguales tengan 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 probablemente no produzcan muchos falsos positivos, es decir, posiciones del texto que tienen el mismo valor hash que el patrón pero en realidad no coincide con el patrón. Estas posiciones contribuyen innecesariamente al tiempo de ejecución del algoritmo, sin producir una coincidencia. Además, la función hash utilizada debe ser un hash rodante, una función hash cuyo valor se pueda 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

El algoritmo es el que se muestra:

función RabinKarp()cuerda s[1..n] cuerda patrón[1..m]) hpattern := hash()patrón[1..m]); para i desde 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 i Regreso 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 tiempo O(mn), la misma complejidad que un algoritmo sencillo de coincidencia de cadenas. Para lograr 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, entonces calcular valores hash sucesivos será rápido.

El truco se puede explotar usando un hash rodante. Un hash rodante es una función hash especialmente diseñada para permitir esta operación. Una función hash rodante trivial (pero no muy buena) simplemente agrega 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 hará que la instrucción 5 se ejecute con más frecuencia que otras funciones hash rodantes 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 el hash es deficiente (como producir 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 ciclo). Debido a que la comparación carácter por carácter de cadenas con una longitud m toma un tiempo O(m), todo el algoritmo toma un tiempo O(mn) en el peor de los casos.

Función hash utilizada

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 digital de Rabin es una función 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, 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 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 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" menos de uno de los "dígitos". Consulte la función hash para obtener una discusión mucho más detallada. El beneficio esencial que se logra al utilizar 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 realizando solo un número constante de operaciones, independientemente de las subcadenas. longitudes.

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 primo 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", a partir del hash de "abr" restando el número agregado para la primera 'a' de "abr", es decir, 97 × 256², multiplicando por la base y sumando para la última a de "bra", es decir, 97 × 256 ⁰. Al igual que:

// viejo hash (-ve avoider)* viejo 'a' base offset cambio de base nuevo 'a' primer módulo
hash("bra") = [ (4 + 101 - 97 * [(256%101)*256] % 101) * 256 + 97 ] % 101 = 30

_{* (-ve avoider) = "evitador de flujo". Necesario si el uso de enteros no firmados para cálculos. Porque sabemos todos los hahes ${displaystyle hleq p}$ para el módulo principal $p$, podemos asegurar que ninguna subfluencia añadiendo 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 hacia la izquierda}

_{aunque ((256%101)*256)%101 es lo mismo que 256² % 101, para evitar que se desborden los máximos de enteros cuando la cadena del patrón es más larga (por ejemplo, 'Rabin-Karp' tiene 10 caracteres, 256⁹ 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 coincidimos con la cadena de búsqueda "bra", usando un cálculo similar de hash("abr"),

hash'("bra") = [[ ([ (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.

En teoría, existen otros algoritmos que podrían proporcionar un recálculo conveniente, p.e. multiplicar los valores ASCII de todos los caracteres para que cambiar la 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 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 causen muchas colisiones hash y, por lo tanto, ralenticen el algoritmo. Por lo tanto, la función hash descrita suele ser la preferida en el algoritmo Rabin-Karp.

Búsqueda de patrones múltiples

El algoritmo Rabin-Karp es inferior para la búsqueda de un solo patrón al algoritmo de Knuth-Morris-Pratt, al algoritmo de búsqueda de cadenas de Boyer-Moore y a otros algoritmos más rápidos de búsqueda de cadenas de un solo patrón debido a su lento comportamiento en el peor de los casos. Sin embargo, es un algoritmo útil para la búsqueda de múltiples patrones.

Para encontrar un número grande, digamos k, 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 El hash de una cadena determinada pertenece a un conjunto de valores hash de patrones que estamos buscando:

función RabinKarpSet()cuerda s[1..n] set de cuerda subs, m): set hsubs := vacío Set en adelante sub dentro subs insertar hash()sub[1..m]) en hsubs hs := hash()s[1..m]) para i desde 1 a n-m+1 si hs ▪ hsubs y s[i..i+m-1] ▪ subs Regreso i hs := hash()s[i+1..i+m]) Regreso no encontrado

Asumimos que todas las subcadenas tienen una longitud fija m.

Una forma ingenua de buscar patrones k es repetir una búsqueda de un solo patrón tomando O(n+m) tiempo, totalizando O((n+m)k) tiempo. Por el contrario, el algoritmo anterior puede encontrar todos los patrones k en el tiempo esperado O(n+km), asumiendo que una verificación de la tabla hash funciona en O(1) tiempo esperado.