改进Boyer-Moore字符串搜索

Question

我一直在玩Boyer叮咬搜索算法，从Shriphani Palakodety的一个基本代码集开始，我创建了另外两个版本(v2和v3) --每个版本都做了一些修改，比如从循环中删除len()函数，而不是重构while/if条件。从v1到v2，我看到了大约10%-15%的改善，从v1到v3有25%-30%的改善(显著)。

我的问题是:是否有任何额外的mods可以更好地提高性能(如果你可以作为一个v4提交)-保持基本的‘算法’真实的博耶-摩尔。

#!/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(键)操作。有两个好处:调用方只有一个API可供使用，您可以避免将bcs作为全局的(可怕的** 2)。

您的缩进在几个地方是不正确的。

更新

这不是Boyer算法(它使用两个查找表)。它看起来更像Boyer Horspool算法，它只使用第一个BM表.

可能的加速:在设置bcsget之后添加'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版有一些bug，您已经将其移植到版本2和3中。

将未找到的响应从“未找到”更改为-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)

运行该程序，修复v1中的错误，继续执行这些修复，再次运行测试，直到它们都正常为止。然后，您可以按照相同的路线整理您的定时线束，并查看性能。然后您可以在这里报告，我将给您一个searchv4函数应该是什么样子的想法;-)