Algoritmo de Rabin-Karp en Python

Presentaremos el algoritmo de Rabin-Karp en Python y discutiremos cómo podemos usarlo en nuestros programas de Python.

Algoritmo de Rabin-Karp en Python

El algoritmo de Rabin-Karp encuentra números, letras o patrones específicos a partir de una entrada o valor dado. Los algoritmos de aprendizaje automático suelen ser la solución preferida en la ciencia de datos cuando necesita extraer información de los datos, pero no todos los algoritmos se crean de la misma manera.

Algunos son mejores que otros para encontrar la información correcta y algunos son mejores que otros para evitar falsos positivos. Uno de los algoritmos de aprendizaje automático más potentes para encontrar la información adecuada es el algoritmo de Rabin-Karp.

El algoritmo de Rabin-Karp se utiliza para encontrar la mejor coincidencia entre un conjunto de texto y posibles contraseñas. Se utiliza principalmente en software para ayudar a los usuarios a encontrar sus contraseñas cuando las han olvidado.

Inicialmente se desarrolló para encontrar direcciones de correo electrónico en texto y, desde entonces, se ha utilizado en muchas otras aplicaciones, como encontrar números de teléfono, extraer texto de archivos PDF y mucho más. Fue diseñado por Richard M. Rabin y Abraham S. Karp.

Complejidad del Algoritmo de Rabin-Karp en Python

El algoritmo de Rabin-Karp es un método para encontrar un número mínimo de valores distintos en una matriz de manera eficiente. Se ha demostrado que es asintóticamente más rápido que otros algoritmos comunes de búsqueda de mínimos, como la búsqueda binaria, el sondeo cuadrático y la búsqueda secuencial.

Sin embargo, el algoritmo de Rabin-Karp suele ser mucho más complejo que su complejidad teórica en el peor de los casos de (O(n)), donde n es el número de valores distintos en la matriz de búsqueda. Tenemos esta complejidad porque el algoritmo de Rabin-Karp debe visitar repetidamente cada valor en la matriz de búsqueda hasta que encuentre el valor requerido.

Implementar el Algoritmo de Rabin-Karp en Python

Ahora, comprendamos cómo implementar el algoritmo Rabin-Karp en nuestros ejemplos de Python.

Daremos un patrón de caracteres y luego comprobaremos la posibilidad del patrón dado a los elementos existentes. Si se encuentra el patrón, indíquelo como salida.

Primero, asignaremos el valor de la cantidad de caracteres agregados como entrada. En nuestro caso, le asignaremos 15, como se muestra a continuación.

# python
numOfChar = 15

Definiremos una función como searchPattern que tomará tres argumentos. El primer argumento será el patrón que queremos encontrar usando el algoritmo de Rabin-Karp.

El segundo argumento será el texto en el que buscaremos un patrón. Y el último argumento será el número primo.

Asignaremos la longitud del patrón y el texto a las variables para poder usar la longitud más adelante. También estableceremos el valor hash para el patrón y el texto.

Definiremos las variables a y b en los bucles for.

# python
def searchPattern(pattern, text, primeNum):
    patLen = len(pattern)
    txtLen = len(text)
    a = 0
    b = 0
    p = 0  # hash value for pattern
    t = 0  # hash value for txt
    h = 1

Del algoritmo de Rabin-Karp, primero encontraremos el valor de h usando la fórmula pow(numOfChar, patLen-1)% primeNum, como se muestra a continuación.

# python
for a in xrange(patLen - 1):
    h = (h * numOfChar) % primeNum

Ahora, encontraremos el valor hash del patrón y la primera ventana del texto, como se muestra a continuación.

# python
for a in xrange(patLen):
    p = (numOfChar * p + ord(pattern[a])) % primeNum
    t = (numOfChar * t + ord(text[a])) % primeNum

Crearemos otro bucle for para deslizar el patrón sobre el texto uno a uno. Dentro de este bucle for, comprobaremos el valor hash de la ventana actual de texto y patrón.

Si los valores hash coinciden, verificaremos los caracteres uno por uno, como se muestra a continuación.

# python
for a in range(txtLen - patLen + 1):

    if p == t:
        for b in range(patLen):
            if text[a + b] != pattern[b]:
                break

        b += 1
        if b == patLen:
            print("Pattern found at index " + str(a))

    if a < txtLen - patLen:
        t = (numOfChar * (t - ord(text[a]) * h) + ord(text[a + patLen])) % primeNum

        if t < 0:
            t = t + primeNum

Ahora, asignemos valores a los parámetros y llamemos a la función para verificar cómo funciona, como se muestra a continuación.

# python
text = "ABBAABCDEAABBDCAABB"
pattern = "ABB"
primeNum = 101
searchPattern(pattern, text, primeNum)

Producción:

Como puede ver, nuestro patrón se encontró en tres lugares diferentes. Usando el algoritmo de Rabin-Karp, podemos encontrar patrones en un texto dado en múltiples ubicaciones.