improving Boyer-Moore string search

Question

I've been playing around with the Boyer-Moore sting search algorithm and starting with a base code set from Shriphani Palakodety I created 2 additional versions (v2 and v3) - each making some modifications such as removing len() function from the loop and than refactoring the while/if conditions. From v1 to v2 I see about a 10%-15% improvement and from v1 to v3 a 25%-30% improvement (significant).

My question is: does anyone have any additional mods that would improve performance even more (if you can submit as a v4) - keeping the base 'algorithim' true to Boyer-Moore.

---

#!/usr/bin/env python
#original Boyer-Moore implementor (v1): Shriphani Palakodety

import time

bcs = {} #the table

def goodSuffixShift(key):
    for i in xrange(len(key)-1, -1, -1):
    if key[i] not in bcs.keys():
        bcs[key[i]] = len(key)-i-1


#---------------------- v1 ----------------------
def searchv1(text, key):
    #base from Shriphani Palakodety fixed for single char
    i = len(key)-1
    index = len(key) -1
    j = i 

    while True:
        if i < 0:
            return j + 1
        elif j > len(text):
            return "not found"
        elif text[j] != key[i] and text[j] not in bcs.keys():
            j += len(key)
            i = index
        elif text[j] != key[i] and text[j] in bcs.keys():
            j += bcs[text[j]]
            i = index
        else:
            j -= 1
            i -= 1

#---------------------- v2 ----------------------                        
def searchv2(text, key):
    #removed string len functions from loop
    len_text = len(text)
    len_key = len(key)
    i = len_key-1
    index = len_key -1
    j = i

    while True:
    if i < 0:
        return j + 1
    elif j > len_text:
        return "not found"
    elif text[j] != key[i] and text[j] not in bcs.keys():
        j += len_key
        i = index
    elif text[j] != key[i] and text[j] in bcs.keys():
        j += bcs[text[j]]
        i = index
    else:
        j -= 1
        i -= 1                        

#---------------------- v3 ----------------------
def searchv3(text, key):
    #from v2 plus modified 3rd if condition - breaking down the comparison for efficency,
    #modified the while loop to include the first if condition (oppposite of it)
    len_text = len(text)
    len_key = len(key)
    i = len_key-1
    index = len_key -1
    j = i

    while i >= 0 and j <= len_text:
    if text[j] != key[i]:
            if text[j] not in bcs.keys():
                j += len_key
                i = index
            else:
                j += bcs[text[j]]
                i = index
    else:
        j -= 1
        i -= 1

    if j > len_text:
    return "not found"
    else:
        return j + 1


key_list = ["POWER", "HOUSE", "COMP", "SCIENCE", "SHRIPHANI", "BRUAH", "A", "H"]

text = "SHRIPHANI IS A COMPUTER SCIENCE POWERHOUSE"

t1 = time.clock()
for key in key_list:
    goodSuffixShift(key)
    #print searchv1(text, key)
        searchv1(text, key)
    bcs = {}

t2 = time.clock()
print 'v1 took %0.5f ms' % ((t2-t1)*1000.0)

t1 = time.clock()
for key in key_list:
    goodSuffixShift(key)
    #print searchv2(text, key)
        searchv2(text, key)
    bcs = {}

t2 = time.clock()
print 'v2 took %0.5f ms' % ((t2-t1)*1000.0)

t1 = time.clock()
for key in key_list:
    goodSuffixShift(key)
    #print searchv3(text, key)
        searchv3(text, key)
    bcs = {}

t2 = time.clock()
print 'v3 took %0.5f ms' % ((t2-t1)*1000.0)

Answer 1

Not an algorithm improvement, but in goodSuffixShift, you have an extraneous call to keys().

in bcs  # replaces in bcs.keys()

Answer 2

I suggest you profile your code, locate performance bottlenecks and fix them.

Answer 3

Using "in bcs.keys()" is creating a list and then doing an O(N) search of the list -- just use "in bcs".

Do the goodSuffixShift(key) thing inside the search function. Two benefits: the caller has only one API to use, and you avoid having bcs as a global (horrid ** 2).

Your indentation is incorrect in several places.

Update

This is not the Boyer-Moore algorithm (which uses TWO lookup tables). It looks more like the Boyer-Moore-Horspool algorithm, which uses only the first BM table.

A probable speedup: add the line 'bcsget = bcs.get' after setting up the bcs dict. Then replace:

if text[j] != key[i]:
    if text[j] not in bcs.keys():
        j += len_key
        i = index
    else:
        j += bcs[text[j]]
        i = index

with:

if text[j] != key[i]:
    j += bcsget(text[j], len_key)
    i = index

Update 2 -- back to basics, like getting the code correct before you optimise

Version 1 has some bugs which you have carried forward into versions 2 and 3. Some suggestions:

Change the not-found response from "not found" to -1. This makes it compatible with text.find(key), which you can use to check your results.

Get some more text values e.g. "R" * 20, "X" * 20, and "XXXSCIENCEYYY" for use with your existing key values.

Lash up a test harness, something like this:

func_list = [searchv1, searchv2, searchv3]
def test():
    for text in text_list:    
        print '==== text is', repr(text)
        for func in func_list:
             for key in key_list:
                try:
                    result = func(text, key)
                except Exception, e:
                    print "EXCEPTION: %r expected:%d func:%s key:%r" % (e, expected, func.__name__, key)
                    continue
                expected = text.find(key)
                if result != expected:
                    print "ERROR actual:%d expected:%d func:%s key:%r" % (result, expected, func.__name__, key)

Run that, fix the errors in v1, carry those fixes forward, run the tests again until they're all OK. Then you can tidy up your timing harness along the same lines, and see what the performance is. Then you can report back here, and I'll give you my idea of what a searchv4 function should look like ;-)

Answer 4

Have you compared to the algorithm Fredrik Lundh developed for Python 2.5?