改进Boyer-Moore字符串搜索

Question

我最近在玩一个叫做Boyer-Moore字符串搜索算法的东西。起初，我从Shriphani Palakodety那里拿到了一些基础代码，然后我又创建了两个版本（v2和v3），在这些版本中我做了一些修改，比如在循环中去掉了len()这个函数，然后重新整理了while和if的条件。从v1到v2，我看到性能提升了大约10%-15%；而从v1到v3，性能提升了25%-30%（这个提升很明显）。

我想问的是：有没有人有其他的修改建议，可以让性能进一步提升（如果可以的话，请提交一个v4），同时保持算法的基本结构不变，依然遵循Boyer-Moore的原理。

---

#!/usr/bin/env python
import time

bcs = {} #the table

def goodSuffixShift(key):
    for i in range(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 efficiency,
    modified the while loop to include the first
    if condition (opposite 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

使用 "in bcs.keys()" 这个写法会先创建一个列表，然后再进行 O(N) 的查找，直接用 "in bcs" 就可以了。

把 goodSuffixShift(key) 的功能放在搜索函数里面。这样有两个好处：调用者只需要一个接口就行了，而且你可以避免把 bcs 设为全局变量（这样做很糟糕）。

你的缩进在好几个地方不对。

更新

这不是 Boyer-Moore 算法（它使用两个查找表）。这更像是 Boyer-Moore-Horspool 算法，它只用第一个 BM 表。

可能的加速方法：在设置 bcs 字典后，加上这一行 'bcsget = bcs.get'。然后把：

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

替换成：

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

更新 2 -- 回到基础，先把代码写对再优化

版本 1 有一些错误，这些错误在版本 2 和 3 中也保留了。这里有一些建议：

把找不到的响应从 "not found" 改成 -1。这样就和 text.find(key) 兼容了，你可以用它来检查你的结果。

再准备一些文本值，比如 "R" * 20, "X" * 20，还有 "XXXSCIENCEYYY"，用来和你现有的键值一起测试。

搭建一个测试框架，像这样：

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)

运行这个，修复版本 1 中的错误，把这些修复带到后面的版本，再次运行测试，直到所有测试都通过。然后你可以整理一下你的计时框架，看看性能如何。最后你可以在这里反馈结果，我会告诉你我认为 searchv4 函数应该是什么样子的 ;-)