# Text search in Python

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
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:
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:
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?

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