Algoritmo de Rabin-Karp

En informática , el algoritmo de Rabin-Karp o Karp-Rabin es un algoritmo de búsqueda de cadenas creado por Richard M. Karp y Michael O. Rabin ( 1987 ) que utiliza funciones hash para encontrar una coincidencia exacta de una cadena de patrón en un texto. Emplea una función hash rotativa para filtrar rápidamente las posiciones del texto que no coinciden con el patrón y, a continuación, busca coincidencias en las posiciones restantes. Se pueden utilizar generalizaciones de esta misma idea para encontrar más de una coincidencia de un mismo patrón, o para encontrar coincidencias de varios patrones. 

Para encontrar una única coincidencia de un único patrón, el tiempo esperado del algoritmo es lineal con respecto a la longitud combinada del patrón y el texto, aunque su complejidad temporal en el peor de los casos es el producto de ambas longitudes. Para encontrar múltiples coincidencias, el tiempo esperado es lineal con respecto a las longitudes de entrada, más la longitud combinada de todas las coincidencias, que podría ser mayor que lineal. En contraste, el algoritmo de Aho-Corasick puede encontrar todas las coincidencias de múltiples patrones en un tiempo y espacio en el peor de los casos lineal con respecto a 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 . A partir del material de origen, el algoritmo puede buscar rápidamente en un documento frases idénticas, sin tener en cuenta detalles como mayúsculas/minúsculas o puntuación. Debido a la gran cantidad de cadenas de caracteres buscadas, los algoritmos de búsqueda de una sola cadena resultan poco prácticos.

Un algoritmo ingenuo de comparación de cadenas compara el patrón dado con todas las posiciones del texto. Cada comparación consume 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 máximo de ejecución de este método es proporcional al producto de ambas longitudes. En muchos casos prácticos, este tiempo puede reducirse significativamente interrumpiendo la comparación en cada posición en cuanto se detecta una discrepancia, pero esta idea no garantiza una mejora en la velocidad.

Varios algoritmos de búsqueda de cadenas, como el algoritmo de Knuth-Morris-Pratt y el algoritmo de búsqueda de cadenas de Boyer-Moore , reducen el tiempo de ejecución en el peor de los casos al extraer más información de cada discrepancia, lo que les permite omitir posiciones del texto que con seguridad no coinciden con el patrón. El algoritmo de Rabin-Karp, en cambio, logra su aceleración mediante el uso de una función hash para realizar rápidamente una comprobación aproximada en cada posición, y luego realiza una comparación exacta solo en las posiciones que superan esta comprobación aproximada.

Una función hash convierte cada cadena en un valor numérico, denominado valor hash ; por ejemplo, podríamos tener hash("hello")=5. Si dos cadenas son iguales, sus valores hash también lo son. En una función hash bien diseñada, ocurre lo contrario, aproximadamente: es muy improbable que cadenas diferentes tengan valores hash iguales. El algoritmo Rabin-Karp calcula, 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 coincide con el del patrón, se realiza una comparación completa en esa posición.

Para que esto funcione correctamente, la función hash debe seleccionarse aleatoriamente de una familia de funciones hash que tengan pocas probabilidades de generar falsos positivos ; es decir, posiciones del texto que tengan el mismo valor hash que el patrón, pero que en realidad no coincidan con él. Estas posiciones contribuyen innecesariamente al tiempo de ejecución del algoritmo, sin producir una coincidencia. Además, la función hash utilizada debe ser una función hash rotativa , cuyo valor se pueda actualizar rápidamente de una posición del texto a la siguiente. Recalcular la función hash desde cero en cada posición sería demasiado lento.

El algoritmo es el que se muestra a continuación:

función RabinKarp ( cadena s [ 1. . n ], cadena patrón [ 1. . m ])patrón_h := hash ( patrón [ 1. . m ]);para i desde 1 hasta n - m + 1hs := hash ( s [ i .. i + m - 1 ])si hs = patrón de hsi s [ i .. i + m - 1 ] = patrón [ 1. . m ]regreso ino se encontró el retorno

Las líneas 2, 4 y 6 requieren un tiempo de O ( m ) cada una. Sin embargo, la línea 2 se ejecuta solo una vez, y la línea 6 solo se ejecuta si los valores hash coinciden, lo cual es improbable que ocurra 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 radica en la línea 4.

Calcular ingenuamente el valor hash de la subcadena s[i+1..i+m]requiere un tiempo de O( m ) porque se examina cada carácter. Dado que el cálculo del hash se realiza en cada iteración del bucle, el algoritmo con un cálculo de hash ingenuo requiere un tiempo de O( mn ), la misma complejidad que un algoritmo de comparación de cadenas directo. Para mayor velocidad, el hash debe calcularse en tiempo constante. El truco consiste en que la variable hsya contiene el valor hash anterior s[i..i+m-1]. Si ese valor se puede usar para calcular el siguiente valor hash en tiempo constante, entonces el cálculo de los valores hash sucesivos será rápido.

Este truco se puede aprovechar utilizando una función hash rodante . Una función hash rodante es una función hash diseñada específicamente para permitir esta operación. Una función hash rodante simple (pero no muy eficiente) simplemente suma los valores de cada carácter de la subcadena. Esta fórmula de hash rodante 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 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.

Para un buen rendimiento, se 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), la línea 6 se ejecutaría O( n ) veces (es decir, en cada iteración del bucle). Dado que la comparación carácter por carácter de cadenas de longitud m requiere un tiempo de O( m ), el algoritmo completo requiere, en el peor de los casos, un tiempo de O( mn ).

La clave del rendimiento del algoritmo Rabin-Karp reside en el cálculo eficiente de los valores hash de las subcadenas sucesivas del texto. La huella digital de Rabin es una función hash rotativa popular y eficaz. La función hash que se describe aquí no es una huella digital de Rabin, pero funciona igual de bien. Trata cada subcadena como un número en una base determinada, que suele ser 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) % [ a ] 101 + 105] % 101 = 65 ( El código ASCII de 'h' es 104 y el de 'i' es 105)

Técnicamente, este algoritmo solo se asemeja al número real en una representación no decimal, ya que, por ejemplo, la base podría ser menor que uno de los dígitos. Consulte la función hash para una explicación mucho más detallada. La principal ventaja de usar una función hash rotativa, como la huella digital de Rabin, es que permite calcular el valor hash de la siguiente subcadena a partir de la anterior con un número constante de operaciones, independientemente de la longitud de las subcadenas.

Por ejemplo, si tenemos el texto "abracadabra" y buscamos 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

Podemos entonces calcular el hash de la siguiente subcadena, "bra", a partir del hash de "abr" restando el número añadido por la primera "a" de "abr", es decir, 97 × 256 ² , multiplicando por la base y sumando por la última "a" de "bra", es decir, 97 × 256 ⁰ . Así:

// hash antiguo (evitador -ve) [ b ] antiguo 'a' desplazamiento de base izquierda desplazamiento de base nuevo 'a' módulo primo hash("bra") = [ ( 4 + 101 - 97 * [(256%101)*256] % 101 [ c ] ) * 256 [ d ] + 97 ] % 101 = 30

Si hacemos coincidir la cadena de búsqueda "bra", utilizando 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 un gran ahorro 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 de modo que el desplazamiento de la subcadena solo implique dividir el hash anterior por el valor del primer carácter y luego multiplicarlo por el valor del nuevo último carácter. Sin embargo, la limitación es el tamaño limitado del tipo de datos entero y la necesidad de usar aritmética modular para reducir el tamaño de los resultados del hash. ^{[ e ]} 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 causen muchas colisiones de hash y, por lo tanto, ralenticen el algoritmo. Por consiguiente, la función hash descrita suele ser la preferida en el algoritmo de Rabin-Karp.

El algoritmo de Rabin-Karp es inferior para la búsqueda de patrones individuales en comparación con el algoritmo de Knuth-Morris-Pratt , el algoritmo de búsqueda de cadenas de Boyer-Moore y otros algoritmos de búsqueda de cadenas de patrones individuales más rápidos , 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 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 de Bloom o una estructura de datos de conjunto para comprobar si el hash de una cadena dada pertenece a un conjunto de valores hash de patrones que estamos buscando:

función RabinKarpSet ( cadena s [ 1. . n ], conjunto de subcadenas s , m ) :establecer hsubs := emptySetpara cada sub en subsinsertar hash ( sub [ 1. . m ]) en hsubshs := hash ( s [ 1. . m ])para i desde 1 hasta n - m + 1si hs ∈ hsubs y s [ i .. i + m - 1 ] ∈ subsregreso ihs := hash ( s [ i + 1. . i + m ])no se encontró el retorno

Suponemos que todas las subcadenas tienen una longitud fija m .

Una forma ingenua de buscar k patrones consiste en repetir una búsqueda de un solo patrón, lo que lleva un tiempo de O( n + m ), resultando en un tiempo total de O(( n + m ) k ). En cambio, el algoritmo anterior puede encontrar los k patrones en un tiempo esperado de O( n + km ), suponiendo que la comprobación de la tabla hash se realiza en un tiempo esperado de O(1).

• "Algoritmo Rabin-Karp/Rolling Hash" (PDF) . MIT 6.006: Introducción a los algoritmos 2011: notas de la conferencia . MIT.