Text search in Python

Question

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:

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?

Answer 1

• 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).