Newtonpedia EN
Inicio › Informática › Algoritmo Karp-Rabin
Informática · 1987

Algoritmo Karp-Rabin

Algoritmo que busca un patrón de caracteres dentro de un texto comparando primero firmas numéricas (funciones hash) y verificando letra a letra solo cuando coinciden.

Año
1987
Protagonistas
Richard Karp, Michael Oser Rabin
Sección
Informática

Historia

El algoritmo de Karp-Rabin localiza un patrón de caracteres dentro de un texto más largo, por ejemplo una palabra en un documento o una frase en un libro. Su interés está en combinar una comprobación rápida, basada en una huella numérica, con una comparación carácter a carácter que solo se ejecuta cuando las huellas coinciden. Fue enunciado en 1987 por Michael Oser Rabin y Richard Manning Karp, y sigue siendo un ejemplo habitual de cómo el hashing acelera las búsquedas.

Antes de este método, la forma más directa de buscar era la comparación ingenua: colocar el patrón en cada posición del texto y comparar letra a letra. Cada comparación cuesta un tiempo proporcional a la longitud del patrón y hay tantas posiciones como longitud tiene el texto, así que en el peor caso el trabajo es el producto de ambas longitudes. Interrumpir cada comparación en cuanto aparece una diferencia ayuda en la práctica, pero no garantiza nada. Otros métodos, como los de Knuth-Morris-Pratt y Boyer-Moore, mejoran el peor caso aprovechando lo que revela cada discrepancia para saltar posiciones que no pueden coincidir.

Karp y Rabin siguieron otro camino. Una función hash convierte cada cadena en un número, de modo que cadenas iguales dan siempre el mismo número y cadenas distintas casi siempre números diferentes. Para ello tratan los caracteres como las cifras de un número escrito en una base, que en el planteamiento original es el tamaño del alfabeto. Cada ventana del texto de tantos caracteres como el patrón recibe así un número, y el patrón también tiene el suyo. Si los números no coinciden, esa ventana no puede ser el patrón. Si coinciden, puede haber un acierto, pero hay que comprobarlo porque dos cadenas distintas pueden compartir número, lo que se llama colisión.

La eficiencia depende de no recalcular el número desde cero en cada posición. Al avanzar una casilla basta con quitar la cifra de mayor peso, multiplicar por la base y añadir el nuevo carácter al final. Una función que se actualiza así, en tiempo constante, a partir del valor anterior se llama hash rodante. Como los números crecen deprisa y superan lo que un ordenador puede almacenar, se toma el resto de dividirlos entre un número primo grande, que además fija el tamaño de la tabla de dispersión. Este resto es compatible con las actualizaciones sucesivas, de modo que el resultado coincide con el de un cálculo completo.

La versión de 1987 está pensada para buscar un patrón en un texto. Su coste medio crece con la suma de ambas longitudes, aunque en el peor caso sigue siendo el producto de las dos. Su ventaja aparece cuando hay muchos patrones: en lugar de compararlos uno a uno, se guardan sus huellas en un conjunto y se consulta si la huella de cada ventana pertenece a él. Para un solo patrón, otros algoritmos suelen ser más rápidos en el peor caso; para varios, este planteamiento resulta práctico. El algoritmo de Aho-Corasick también encuentra todas las coincidencias de varios patrones, con un límite de tiempo garantizado.

Con el tiempo, el hash rodante se convirtió en una técnica de uso común, y la huella de Rabin es una de sus variantes más populares. La función de la descripción original no es exactamente una huella de Rabin, pero funciona de manera muy similar. Su aplicación más conocida hoy es la detección de plagio: dado un texto fuente, el algoritmo puede revisar con rapidez un trabajo en busca de frases copiadas de él, sin tener en cuenta mayúsculas ni signos de puntuación.

Cronología

  • 1987Michael Oser Rabin y Richard Manning Karp presentan el algoritmo.
  • Knuth-Morris-Pratt y Boyer-Moore, más rápidos en el peor caso para un solo patrón (fecha no consignada).
  • Aho-Corasick encuentra todas las coincidencias de varios patrones con límite de tiempo garantizado (fecha no consignada).
  • La detección de plagio se convierte en una de sus aplicaciones prácticas más citadas (fecha no consignada).

Curiosidades y anécdotas

Un ejemplo con abracadabra

La explicación original usa la palabra abracadabra, con un patrón de tres letras, base 256 y módulo 101, para mostrar cómo pasar de abr a bra sin recalcular todo.

Dos nombres para un mismo método

El algoritmo aparece citado indistintamente como Rabin-Karp o Karp-Rabin, según el orden en que se mencionen sus autores.

Protagonistas

Otros hitos de informática