python - 改进 Boyer-Moore 字符串搜索

Question

我一直在研究 Boyer-Moore sting 搜索算法，并从 Shriphani Palakodety 的基本代码集开始，我创建了 2 个附加版本(v2 和 v3)——每个版本都进行了一些修改，例如从中删除 len() 函数循环，而不是重构 while/if 条件。从 v1 到 v2，我看到大约有 10%-15% 的改进，从 v1 到 v3 有 25%-30% 的改进(显着)。

我的问题是:是否有人有任何额外的 mod 可以进一步提高性能(如果您可以提交为 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) 操作。两个好处:调用者只有一个 API 可以使用，并且您可以避免将 bcs 作为全局(可怕的 ** 2)。

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

更新

这不是 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。一些建议:

将未找到响应从“未找到”更改为 -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 函数应该是什么样子的想法;-)