5
\$\begingroup\$

Whilst self-studying algorithms, I came across the Karp-Rabin rolling hash search algorithm here. I decided to have a go at implementing it in Python:

For ease of reading; the data-structure description and formulas embedded in append() and skip() are:

enter image description here

import random
from time import process_time

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif (n % 2 == 0) or (n % 3 == 0):
        return False
    i = 5
    while (i*i) <= n:
        if (n % i == 0) or ((n % (i + 2)) == 0):
            return False
        i += 6
    return True

def find_prime_above(x):
    x = int(x)
    if x < 0:
        x = 0
    if x > 100:
        interval = int(x / 10)
    else:
        interval = x + 1
    count = 0
    found = False
    while not found:
        if (x % 2) == 0:
            start = x + 1
        else:
            start = x
        n = random.randrange(start, start + interval, 2)
        if is_prime(n):
            found = True
            return n
        count += 1
        if count > (interval / 2):
            interval *= 2
            count = 0

class hash_div(object):
    def __init__(self, size):
        if not is_prime(size):
            ValueError("Use a prime as the base")
        self.mod = size

    def h(self, num):
        return num % self.mod


class rolling_hash(hash_div):
    # built for strings
    def __init__(self, base, size):
        self.a = base
        self.uModP = 0
        self.size_x = 0
        self.ax = 1
        super(rolling_hash, self).__init__(size)

    def r(self):
        return self.uModP

    def update_ax(self, up_down):
        if up_down == "up":
            self.size_x += 1
        elif up_down == "down":
            self.size_x -= 1
        self.ax = self.h(self.a**(self.size_x - 1))

    def append(self, char):
        self.uModP = self.h((self.uModP*self.a) + ord(char))
        self.update_ax("up")

    def skip(self, char):
        self.uModP = self.h(self.uModP - (ord(char) * self.h(self.ax)))
        self.update_ax("down")

def search_file(fileStr, term):
    size = find_prime_above(len(fileStr))
    rs = rolling_hash(256, size)
    rt = rolling_hash(256, size)

    for c in term:
        rs.append(c)

    for c in fileStr[:len(term)]:
        rt.append(c)

    for i in range(len(term), len(fileStr)):
        rt.skip(fileStr[i - len(term)])
        rt.append(fileStr[i])
        if rs.r() == rt.r():
            # Found 1st instance, now print index of occurance
            print(i)
            # print rest of line
            ind = i - len(term) + 1
            ch = fileStr[ind]
            while ch != '\n':
                print(ch, end = "")
                ind += 1
                ch = fileStr[ind]
            print("\n")
            return i

test = input("Do you want to run in test mode?: ")

if test in ["yes", "y"]:
    fileName = "Shakey.txt"
    searchTerms = []
    with open(fileName, "r") as fp:
        words = fp.read().split()
        for i in range(100):
            searchTerms.append(random.choice(words))
else:
    fileName = input("Type File Name: ")
    searchTerms = [input("Type search term: ")]

total_t = 0

with open(fileName, "r") as fp:
    fileStr = fp.read()
    for term in searchTerms:
        t0 = process_time()
        search_file(fileStr, term)
        t = process_time() - t0
        total_t += t
        print(term, "took:", t, "s")
        print("----")

print("Average Time: ", total_t/len(searchTerms))

I'm using the works of Shakespeare as a test case, and it takes on average 0.5s to find a particular word (based on my test case embedded in code). My is_prime() function is verbatim from here, and I know that my find_prime_above() function is a bit of a dogs dinner.

But I have a few main questions:

  1. Is there anything in my implementation that could be done to improve the constant factors (using the Karp-Rabin algorithm) and make it run faster?
  2. How should I structure my tests (I am self taught, so I don't have anyone to tell me best practices)? Should they be in a separate file?
\$\endgroup\$
3
\$\begingroup\$
  • Computing hash with Python built-in

        pow(self.a, self_size - 1, self.mod)
    

    is much faster than ** and % done separately.

  • I don't see the reason of passing string argument to update_ax. Passing 1 and -1 directly is much cleaner and likely faster:

    def update_ax(self, up_down):
        self.size_x += up_down
        self.ax = self.h(....)
    
  • Finding a prime is indeed unconventional. I recommend to run a standard sieve (Chebyshov' theorem aka Bertrand postulate guarantees a prime in [n, 2n] range).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.