高效的字符串匹配方法--BM算法

提起BM算法，就不得不说，在作者还是个弱鸡的时候，我怀着好奇心的看了2个晚上，愣是没有看懂。这几天，重温了一下此算法，发现自己开窍了，于是决定分享出自己的心得。

一、一般情况下的字符串匹配
先说下要解决的问题，假设有2个字符串a和b，我想知道字符串a中是否包含字符串b，如果包含就返回b在a中的开始位置，如果不包含就返回-1。
为了后面方便说明，先对上面提到的a、b字符串进行命名，我们称a为“文本”，b为“模式串”。
不妨举个例子：

text = "abcdefgh"
str_a = "def"
str_b = "static"

那我们明眼就能看出来，match_str中包含str_a，应该返回3，不包含str_b，应该返回-1，一般的方法是一位位的进行比较，发现字符不匹配的时候，就将模式串后移一位，然后再逐位进行比较，一直到完全匹配或者模式串移到了文本的末尾。下面看下一般方法的匹配图示：

image.png

图中可以看出，字符串a共挪动了3次，最终匹配成功，字符串b挪动了2次，最终匹配失败。
如果用程序来写的话，一般会像下面这样写：

def match(text, match_str):
    match_len = len(text) - len(match_str) + 1
    for i in range(match_len):
        for j in range(len(match_str)):
            if match_str[j] != text[i+j]:
                break
            if j == len(match_str)-1:
                return i
    return -1

但是这种匹配方法效率是比较低下的，因为每次只位移一位，会发生很多不必要的比较，而BM算法就是为了解决这个问题的。

二、BM算法的匹配方式
其实BM方法有2种模式相结合来提高匹配效率，分别是“坏字符”和“好后缀”，下面分别进行介绍：
1、坏字符
坏字符指的是模式串和文本匹配时出现的不相同的字符，当出现不同时，坏字符的移动规则如下：

image.png

像上图这样，当文本和模式串对齐后，从模式串的末位开始从后往前比较，当发现文本中的某个字符不匹配的时候，直接将该字符与模式串中最后出现该字符的位置对齐，如果模式串中没有出现该字符，则将模式串整体挪到该字符之后。通过这样的操作，就可以一次移动多个字符，但是也有可能出现倒退的情况，比如下图：

image.png
像上面这样，匹配不仅会倒退，还会进入死循环，使匹配一直无法结束。先别急，这个问题会在结合了第二种模式后，得到解决。

2、好后缀
好后缀又分3种情况
①好的后缀可以在模式串的后缀之前位置的字符串中找到

image.png

如上图，第一步时模式串末尾的ef和文本中是匹配的，但是倒数第三位开始不匹配了，此时ef就称为是“好后缀”，此时我们将模式串去掉最后一个字母，变成aefce，看是否存在好的后缀ef，显然是存在的，那就将此ef与文本进行对齐，当没有好的后缀的时候，就停止挪动了，就会一直停在原地，聪明的人应该已经想到了，这种情况下，一定出现了坏字符，而坏字符正式上面的匹配模式。

②好后缀的的后缀子串是模式串的前缀
先来解释下什么时候好后缀的后缀子串，比如abcd的后缀子串有bcd,cd,d,注意bc这种可以不是后缀子串，明白这个定义后，来看下面这张图：

image.png

③模式串中找不到子串和好后缀子串前缀
什么都找不到的，直接全部跳过就好了，如下图：

image.png

3、总体的位移
因为要基于坏字符和好后缀的两种模式，所以我们需要计算出坏字符产生的位移和好后缀产生的位移，取2值中的较大值做为当前的实际位移。

4、代码实现
我们用bc表表示每个字符最后一次在模式串中出现的位置，用gs表表示好后缀产生的位移，为了生成gs表，我们还需要一个suffix表作为过渡，suffix表主要存储从模式串的索引位置开始往前与模式串后缀所能匹配的最长的长度。

# bc表
# 生成坏字符bc表，这里吧每个字符都转成了ascii码表示
def get_bc(match_str):
    result = {}
    str_len = len(match_str)
    for i in range(256):
        result[i] = str_len
    for i in range(len(match_str)):
        result[ord(match_str[i])] = i
    return result

# suffix表
# 判断每个位置能向前匹配多少个后缀
def get_suffix(match_str):
    str_len = len(match_str)
    last_index = str_len - 1
    # 最后一位开始，肯定是完全匹配的，所以直接赋值为字符串长度
    result = [0] * (str_len - 1) + [str_len]
    for i in range(last_index):
        _sum = 0
        for j in range(i, -1, -1):
            if match_str[j] == match_str[last_index - (i - j)]:
                _sum += 1
            else:
                break
        result[i] = _sum
    return result

# gs表
def get_gs(match_str):
    str_len = len(match_str)
    last_index = str_len - 1

    # 当什么都匹配不到的情况，就直接移动字符串的长度
    result = [str_len] * str_len
    suffix = get_suffix(match_str)

    # 找最大前缀，把后缀长度比最大前缀长的gs表位置都置成last_index - i，为了防止覆盖，加上了if result[i] == str_len:
    for i in range(last_index, -1, -1):
        if suffix[i] == i+1:
            # 如果满足前缀要求，则后缀长度只要大于等于前缀长度，都进行位移
            for j in range(last_index-i):
                if result[j] == str_len:
                    result[j] = last_index - i
    # 找匹配后缀
    for i in range(last_index):
        result[last_index - suffix[i]] = last_index - i
    return result

# 主程序
def bm_match(text, match_str):
    text_len = len(text)
    mat_len = len(match_str)
    mat_last_index = mat_len - 1
    assert(0 < mat_len <= text_len)
    # 模式串和文本对齐的位置
    pth_at = 0
    bc = get_bc(match_str)
    gs = get_gs(match_str)
    # 当模式串与文件对齐位置 + 模式串的长度 > 文本长度 时，就停止匹配
    while pth_at + mat_len <= text_len:
        for i in range(mat_last_index, -1, -1):
            if match_str[i] == text[pth_at + i]:
                if i == 0:
                    return pth_at
            else:
                move_len = max(i - bc[ord(text[i])], gs[i])
                pth_at += move_len
                break
    return -1
        

qq:270239148，欢迎咨询。