Algoritmo de Rabin-Karp

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de junio de 2021; las comprobaciones requieren 3 ediciones .

El algoritmo de Rabin-Karp es un algoritmo de búsqueda de cadenas que busca un patrón, es decir, una subcadena, en un texto usando hashing . Fue diseñado en 1987 por Michael Rabin y Richard Karp . [una]

El algoritmo rara vez se usa para la coincidencia de un solo patrón, pero tiene una importancia teórica considerable y es muy eficiente en la coincidencia de múltiples patrones de la misma longitud. Para un texto de longitud n y un patrón de longitud m , su tiempo de ejecución promedio y mejor es O ( n ) con la elección correcta de la función hash (ver más abajo), pero en el peor de los casos tiene una eficiencia de O ( nm ) , que es una de las razones por las que no se usa mucho. Para aplicaciones donde la búsqueda de falsos positivos es aceptable, es decir, donde algunas de las ocurrencias encontradas de un patrón pueden no coincidir con el patrón, el algoritmo de Rabin-Karp se ejecuta en un tiempo garantizado de O( n) y con una elección adecuada de la función hash aleatoria (ver más abajo), la probabilidad de error puede hacerse muy pequeña. Además, el algoritmo tiene una característica única para encontrar cualquiera de las k cadenas dadas de la misma longitud en promedio (con la elección correcta de la función hash) en tiempo O( n ), independientemente del tamaño de k .

Una de las aplicaciones prácticas más simples del algoritmo de Rabin-Karp es detectar plagio. Digamos, por ejemplo, que un estudiante está escribiendo un artículo sobre Moby Dick . El profesor intrigante encuentra varios materiales fuente de Moby Dick y extrae automáticamente una lista de oraciones en esos materiales. Luego, el algoritmo de Rabin-Karp puede encontrar rápidamente ejemplos de ocurrencias de algunas oraciones de los materiales de origen en el artículo que se está verificando. Para hacer que el algoritmo sea menos sensible a las pequeñas diferencias, se pueden ignorar detalles como el caso o la puntuación eliminándolos. Dado que el número de cadenas que estamos buscando, k , es muy grande, los algoritmos habituales de búsqueda de una sola cadena se vuelven ineficaces.

Búsqueda de subcadenas por turno y algoritmos competitivos

La tarea principal del algoritmo es encontrar una cadena de longitud m , llamada patrón , en un texto de longitud n . Uno de los algoritmos más simples para esta tarea simplemente busca la subcadena en todos los lugares posibles:

1 función NaiveSearch( cadena s[1..n], cadena sub[1..m]) 2 para i de 1 a n-m+1 3 para j de 1 a m 4 si s[i+j-1] ≠ sub[j] 5 ir a la siguiente iteración del bucle exterior 6 volver i 7 volver no encontrado

Este algoritmo funciona bien en muchos casos prácticos, pero es completamente ineficiente, por ejemplo, al encontrar una cadena de 10 mil caracteres "a" seguida de "b" en una cadena de 10 millones de caracteres "a". En este caso muestra su peor tiempo de ejecución Θ ( mn ).

El algoritmo de Knuth-Morris-Pratt reduce este tiempo a Θ( n ), utilizando el cálculo previo una vez para cada carácter del texto; El algoritmo de Boyer-Moore omite no solo un carácter, sino tantos como sea posible para que la búsqueda tenga éxito, lo que reduce efectivamente la cantidad de iteraciones a través del ciclo externo, por lo que la cantidad de caracteres con los que comparar puede ser comparable a n/m a lo mejor. En cambio, el algoritmo de Rabin-Karp se enfoca en acelerar las líneas 3-6, que se discutirán en la siguiente sección.

Usar hashing para encontrar subcadenas cambiando

En lugar de utilizar saltos más inteligentes, el algoritmo de Rabin-Karp intenta acelerar la comprobación de equivalencia de patrones con subcadenas en el texto mediante una función hash . Una función hash es una función que convierte cada cadena en un valor numérico llamado valor hash (hash) ; por ejemplo, podemos tener el hash de la cadena "hola" igual a 5. El algoritmo utiliza el hecho de que si dos cadenas son iguales, sus valores hash también son los mismos. Por lo tanto, todo lo que necesitamos es calcular el valor hash de la subcadena buscada y luego encontrar la subcadena con el mismo valor hash.

Sin embargo, hay dos problemas asociados con esto. La primera es que, dado que hay tantas cadenas diferentes, puede ocurrir una colisión entre dos cadenas diferentes: la coincidencia de sus valores hash. En tales casos, es necesario verificar la coincidencia de las subcadenas carácter por carácter, lo que lleva mucho tiempo si estas subcadenas son largas (esta verificación no es necesaria si su aplicación permite falsos positivos). Con funciones hash razonablemente buenas (ver más abajo), las colisiones son extremadamente raras y, como resultado, el tiempo promedio de búsqueda es corto.

Ejemplo de algoritmo (código fuente de la aplicación):

1 función RabinKarp( cadena s[1..n], cadena sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 for i from 1 to (n-m+1) 5 if hs = hsub 6 if s[i..i+m-1] = sub 7 return i 8 hs := hash(s[i+1..i +m]) 9 retorno no encontrado

Las líneas 2, 3 y 6 tardan cada una en ejecutarse . Sin embargo, las líneas 2 y 3 solo se ejecutan una vez, y la línea 6 solo se ejecuta cuando los valores hash coinciden, lo que ocurre con poca frecuencia. La línea 5 se ejecuta una vez, pero siempre toma un tiempo constante. ${\ estilo de visualización \ Omega (m)}$ $norte$

El segundo problema es el recálculo de hash. s[i+1..i+m]Se necesita tiempo para recalcular ingenuamente el valor hash de una subcadena , y dado que esto se hace en cada ciclo, el algoritmo gastará tiempo , que es el mismo que gastan la mayoría de los algoritmos simples. La solución a este problema es asumir que la variable ya contiene el valor hash de la subcadena . Si lo usa para calcular el siguiente valor hash en tiempo constante, entonces el problema está resuelto. $O(m)$ ${\ estilo de visualización \ Omega (mn)}$ hss[i..i+m-1]

Esto se logra utilizando lo que se conoce como hash de anillo . El ejemplo más simple de un hash de anillo es agregar los valores de cada carácter subsiguiente en una subcadena y luego usar esta fórmula para calcular cada valor de hash subsiguiente en una cantidad fija de tiempo:

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Tal fórmula no ofrece ninguna garantía de que las colisiones no ocurrirán con frecuencia, y es realmente fácil asegurarse de que en la mayoría de las aplicaciones, cuando se usa, la expresión en la línea 6 se ejecutará con más frecuencia que cuando se usan otras aplicaciones más "inteligentes". ” funciones hash de anillo.

Tenga en cuenta que si tenemos muy mala suerte o tenemos una función hash muy mala, como una función constante (hash=const), es muy probable que la línea 6 se ejecute una vez, es decir, en cada iteración del ciclo. Dado que lleva tiempo , el algoritmo en sí mismo llevará tiempo . $norte$ ${\ estilo de visualización \ Omega (m)}$ ${\ estilo de visualización \ Omega (mn)}$

La función hash utilizada

Las claves del rendimiento del algoritmo de Rabin-Karp son la baja probabilidad de colisiones y el cálculo eficiente del valor hash de sucesivas subcadenas de texto. Rabin y Karp [1] sugirieron usar un hash polinomial (aunque cualquier otro hash de anillo también funcionaría). Para una plantilla dada , dicho hash se define de la siguiente manera: $pag[1..m]$

hash(p[1..m])=\left(\sum _{i=1}^{m}p[i]x^{mi}\right){\bmod {q)),

donde es un número primo, y es un número de a . Los valores hash de subcadenas consecutivas y para un hash polinomial se calculan de la siguiente manera (tenga en cuenta que para mayor eficiencia, el número se cuenta antes del procedimiento de búsqueda principal de Rabin-Karp): $q$ $X$ ${\ estilo de visualización 0}$ $q-1$ $s[i..i+m-1]$ $s[i+1..i+m]$ $x^{m-1}{\bmod {q))$

hash(s[i+1..i+m])=\left((hash(s[i..i+m-1])-s[i]\cdot x^{m-1} )\cdot x+s[i+m]\right){\bmod {q))

Por ejemplo, let , arbitrariamente, y tenemos el texto "abracadabra" y buscamos un patrón de longitud 3. Podemos calcular el hash de la subcadena "bra" a partir del hash de la subcadena "abr" (subcadena anterior) mediante restando el número agregado para la primera letra 'a' de "abr", es decir ( -ASCII para 'a'), multiplicando por la base y finalmente sumando el último número para "bra", es decir . Para evitar el desbordamiento de enteros, en la mayoría de las implementaciones, después de cada una de estas cuatro operaciones (la multiplicación en el cálculo es una operación separada), debe tomar el módulo de resultado . ${\ estilo de visualización x = 101}$ $q$ ${\ estilo de visualización 97 \ veces 101 ^ {2}}$ ${\ estilo de visualización 97}$ $101$ $97\times 101^{0}=97$ ${\ estilo de visualización 97 \ veces 101 ^ {2}}$ $q$

Rabin y Karp demostraron que si (es decir, fijo) y se elige aleatoriamente un número primo del rango , entonces la probabilidad de una colisión al buscar un patrón en un texto de longitud no excede . Pero dicha función hash tiene dos inconvenientes significativos: en primer lugar, el algoritmo para elegir un número primo aleatorio es bastante engorroso y, en segundo lugar, la aritmética modular hace que dicho hash sea muy lento en la práctica (tenga en cuenta que toda la aritmética en la fórmula para hash de subcadenas sucesivas debe ser módulo , es decir, la toma del módulo se realizará cuatro veces). $x=2$ $X$ $q$ ${\ estilo de visualización [2..n^{3}]}$ $norte$ ${\ estilo de visualización O (1/n)}$ $q$

La modificación moderna del hash polinomial propuesta por Ditzfelbinger y otros [2] no tiene estas deficiencias. La diferencia de esta opción es que el número primo es fijo y el número se selecciona aleatoriamente del rango desde hasta antes de que comience el algoritmo ( no tiene que ser primo en absoluto). Se ha probado [2] que para tal función hash la probabilidad de colisión al buscar un patrón en una cadena para algunos no excede , bajo la condición natural de que para todos . Para acelerar la aritmética modular , puede elegir igual a una potencia de dos menos uno (los llamados primos de Mersenne ): para máquinas de 32 bits es más adecuado , para máquinas de 64 bits - ; el módulo para dichos valores se calcula utilizando operaciones bit a bit rápidas [3] . Otra opción posible son los valores o , para los que también existen algoritmos rápidos para tomar el resto de la división por [4] (el rango de valores aceptables se estrecha ligeramente). Puede elegir solo una vez al inicio del programa y luego usarlo en todos los hashes. $q$ $X$ ${\ estilo de visualización 0}$ $q-1$ $X$ $s[1..n]$ $q>n^{c}$ ${\ estilo de visualización c> 2}$ ${\ estilo de visualización 1/n^{c-2}}$ $0\leq s[i]<q$ $i=1,2,\ldots,n$ $q$ ${\ estilo de visualización q = 2 ^ {31} -1}$ ${\ estilo de visualización q = 2 ^ {61} -1}$ $q$ $q$ ${\ estilo de visualización q = 2 ^ {32} -5}$ ${\ estilo de visualización q = 2 ^ {64} -59}$ $q$ $X$ $X$

Conceptos erróneos sobre hashes polinómicos

Una vez más, observamos que las garantías de ausencia de colisiones proporcionadas por el hash polinomial son muy sólidas: incluso si alguien, sabiendo pero sin saber , seleccionará específicamente el patrón y la cadena de longitud para la búsqueda de modo que el algoritmo de Rabin-Karp con un hash polinomial da tantas colisiones como sea posible, de todos modos, para algunas (es decir, para un tamaño suficientemente grande y no muy grande ) y si se elige realmente al azar, la probabilidad de una sola colisión no será más que , que es muy pequeño. Para conseguirlo es importante el resultado, que es un número primo. Por ejemplo, un error común es asumir o (es decir, no usar aritmética modular en absoluto); un ejemplo de una cadena en la que uno puede encontrar muchas colisiones hash polinómicas para tales , e independientemente de la elección del número , es la secuencia de Morse-Thue . [5] $q$ $X$ $norte$ $q>n^{c}$ ${\ estilo de visualización c> 2}$ $q$ $norte$ $X$ ${\ estilo de visualización 1/n^{c-2}}$ $q$ ${\ estilo de visualización q = 2 ^ {32}}$ ${\ estilo de visualización q = 2 ^ {64}}$ ${\ estilo de visualización q = 2 ^ {k}}$ $X$

La siguiente interpretación de un hash polinomial es popular: cada cadena está representada por un número con una base , y luego este número se toma módulo . Tal interpretación no agrega claridad a la naturaleza de la efectividad de un hash dado, mientras que la interpretación de un hash polinomial como un polinomio propio con coeficientes iguales a los valores de los símbolos simplemente conduce a la prueba de una baja probabilidad. de una colisión con una elección aleatoria [2] : considere dos cadenas diferentes y ; los hashes polinómicos de estas cadenas son iguales si y solo si ; pero del teorema de Bezout se sigue que un polinomio de grado que no es idéntico a cero en el campo de residuos módulo ( se elige simple, precisamente para convertir el anillo de residuos en un campo) tiene como máximo raíces, lo que significa que la probabilidad de una colisión no excede incluso con una elección aleatoria ; por lo tanto, si para algunos , la probabilidad de colisión de dos cadenas de diferente longitud no supera (de ahí, en particular, la probabilidad de error al buscar un patrón en una cadena). $X$ $q$ $X$ $p_{1}[1..m]$ $p_{2}[1..m]$ $\sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi}\equiv 0{\pmod {q))$ ${\displaystyle \sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi))$ $m-1$ $q$ $q$ $m-1$ $p_{1}$ $p_{2}$ $X$ ${\ estilo de visualización (m-1)/q}$ $q>n^{c}\geq m^{c}$ ${\ estilo de visualización c> 1}$ $metro$ ${\ estilo de visualización (m-1)/q<n/q<1/n^{c-1))$ ${\ estilo de visualización 1/n^{c-2}}$

A veces también es posible encontrar una recomendación para usar un número primo como , pero, aparentemente, aparte de las observaciones empíricas sobre algunas cantidades muy limitadas de datos, tal consejo ya no está fundamentado. $X$

Rabin-Karp y la búsqueda de muchos especímenes

Debido a su lento comportamiento en el peor de los casos, el algoritmo de Rabin-Karp es peor que el algoritmo de Knuth-Morris-Pratt , el algoritmo de Boyer-Moore y otros algoritmos de búsqueda rápida de cadenas . Sin embargo, el algoritmo de Rabin-Karp se puede usar para encontrar un conjunto de muestras en tiempo lineal en el mejor de los casos y en tiempo cuadrático en el peor de los casos más difíciles de lograr; aunque aquí también pierde en el peor de los casos frente al algoritmo de Aho-Korasik , que tiene un tiempo de ejecución lineal.

Si queremos encontrar cualquier patrón en un texto dado de un gran conjunto de, digamos, k patrones fijos de igual longitud, podemos modificar el algoritmo de Rabin-Karp usando una tabla hash o cualquier otra estructura de datos para comprobar que el hash de un cadena dada pertenece al conjunto hash valores de muestra que estamos buscando:

función RabinKarpSet( cadena s[1..n], conjunto de subs de cadena , m) { set hsubs := para cada sub en subs

\varnada

hsubs := hsubs {hash(sub[1..m])}

\taza

hs := hash(s[1..m]) for i from 1 to (n-m+1) if hs ∈ hsubs if s[i..i+m-1] = string from subs with hash hs return i hs := hash(s[i+1..i+m]) devolución no encontrada }

Otros algoritmos pueden buscar una sola muestra en el tiempo O( n ) y, por lo tanto, pueden usarse para buscar k muestras en el tiempo O( n k ). Por el contrario, la variante del algoritmo de Rabin-Karp anterior puede encontrar todas las k muestras en el tiempo esperado O( n + k ), porque la tabla hash utilizada para probar el caso en el que el hash de una subcadena es igual al hash de cualquiera de las muestras utiliza el tiempo O(1). En la práctica, debido a la relativa facilidad de implementación y velocidad de operación, esta opción a menudo puede ser preferible al algoritmo de Aho-Korasik .

Véase también

Notas

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matías, Pippinger, 1992 .
↑ SE Anderson. Pequeños trucos de jugueteo. Archivado el 1 de junio de 2020 en Wayback Machine .
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Literatura

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construcción y análisis = Introducción a los algoritmos / ed. S. N. Triguba ; por. De inglés. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2ª ed. - M. : Williams, 2005. - 801 p. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Algoritmos eficientes de coincidencia de patrones aleatorios // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , N° 2 . — S. 249–260 . -doi : 10.1147/ rd.312.0249.
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Las funciones hash polinómicas son fiables // Actas del 19º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP'92) . — Londres, Reino Unido: Springer-Verlag, 1992. — págs. 235–246 . -doi : 10.1007 / 3-540-55719-9_77 .
Krovetz T., Rogaway P. Hashing universal rápido con claves pequeñas y sin preprocesamiento: la construcción PolyR // Actas de la Conferencia internacional sobre seguridad de la información y criptología. - Berlín, Alemania: Springer-Verlag, 2000. - págs. 73–89 . -doi : 10.1007/ 3-540-45247-8_7 .
Pachocki J., Radoszewski J. Dónde usar y cómo no usar el hashing de cadenas polinómicas // Olimpiadas en Informática. - Vilnus, Lituania: Universidad de Vilnus, 2013. - V. 7 . — S. 90–100 .

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitud de Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común