「图示+代码」一看就懂的字符串匹配算法KMP、BM、Sunday

数据与智能 本公众号关注大数据与人工智能技术。由一批具备多年实战经验的技术极客参与运营管理，持续输出大数据、数据分析、推荐系统、机器学习、人工智能等方向的原创文章，每周至少输出7篇精品原创。同时，我们会关注和分享大数据与人工智能行业动态。欢迎关注。

作者 | yu

校对 | gongyouliu

编辑 | auroral-L

全文共1839字，预计阅读时间20分钟。

字符串模式匹配是NLP领域的基础任务，可以在大量的文本内容中快速找到需要的文本信息，比如在文章中搜索关键词的位置和数量，在现实生活中有较高的使用频率，本文主要介绍几种常见的字符串模式匹配算法：KMP，BM和Sunday。

1. KMP （Kunth-Morris-Pratt-string-searching algorithm）

给定字符串 S：mnmmomnmnomo

待匹配字符 P：mnmno

步骤

1）. 待匹配字符 P的前缀表（prefix table）的生成

step 1 写出该字符串所有的前缀

m

m n

m n m

m n m n

m n m n o

step 2 对于每一个字符串 找出其最长公共前缀后缀长度 注：公共前缀后缀长度小于原始字符串长度

得到到前缀表 （注：最长公共前缀后缀长度右移一位）

2）字符串匹配

step 1 将字符串S，P头部对齐，从左到右依次比较字符

step 2 遇到不同的字符时，获取字符串P对应最长公共前后缀的长度，找到其对应的索引值，将字符串P的索引值与字符串S失配位置对齐，从未匹配位置开始从左到右依次比较。若字符串P对应的索引值为-1，则将字符串P右移一位，比较字符。

step 3 重复step 2 ，直到匹配成功

匹配成功，找到第一个匹配位置！

step 4 若想找到S串中全部的P串则继续重复step2

code

def genPreTable(P):
    '''
    :param P:
    :return: 前缀表
    '''
    preTable = [-1] * (len(P) + 1)
    if len(P) > 1:
        preTable[1] = 0
        i, j = 0, 1
        while j < len(P):
            if i == -1 or P[i] == P[j]:
                i += 1
                j += 1
                preTable[j] = i
            else:
                i = preTable[i]
    return preTable


def kmp(S, P):
    '''
    :param S:
    :param P:
    :return: 返回所有匹配成功的index
    '''
    indices = []
    if not P: return [0]


    preTable = genPreTable(P)


    s = p = 0
    while s < len(S):
        if p == -1 or S[s] == P[p]:
            s += 1
            p += 1
        else:
            p = preTable[p]
        if p == len(P):
            indices.append(s - p)
            p = preTable[p]
    return indices


S = 'mnmmomnmnomo'
P = 'mnmno'
result = kmp(S, P)
print(result)

2. BM （Boyer-Moore）

给定字符串 S：mnommnomn

待匹配字符 P：mnomn

（注：从右向左匹配字符串）

1）坏字符规则 （bad character Heuristics）

字符串S跟字符串P中某个字符不匹配时，称S中的这个失配字符为坏字符，此时P需右移。

右移位数 = 坏字符对应P中的位置 - 坏字符在P中最右出现的位置。若P中不存在坏字符，则最右出现位置置-1。

上图所示字符串S，P头部对齐。从右向左比较字符，若字符不同，则右移字符串P，使P中右侧第一个字符‘m‘与S中失配的'm'对齐（字符串P右移一位）

2） 好后缀规则（Good-Suffix Heuristics）

字符失配时，右移位数 = 好后缀在P中的索引 - 好后缀在P上一次出现的索引。若好后缀在模式串中没有再次出现，则为-1。

如上图所示，好后缀为mn， 字符串P右移3位（如下图所示）

步骤

step1. 字符串S，P头部对齐。

step2. 从右到左比较字符，根据上述规则分别计算移动距离，选择较大的距离进行移动，直至匹配成功。

code

def getBadChar(P):
    '''
    :param P:
    :return: 坏字符表
    '''
    badChar = {}
    for i in range(len(P) - 1):
        char = P[i]
        badChar[char] = i + 1
    return badChar


def getGoodSuffix(P):
    # 预生成好后缀表
    goodSuffix = {}
    goodSuffix[''] = 0


    for i in range(len(P)):
        subString = P[len(P) - i - 1:]
        for j in range(len(P) - i - 1):
            if subString == P[j:j + i + 1]:
                goodSuffix[subString] = len(P) - j - i - 1
    return goodSuffix


def BM(S, P):
    '''
    :param S:
    :param P:
    :return: 返回所有匹配成功的index
    '''
    p, s = len(P), len(S)
    if not P: return [0]
    i, j = 0, p
    indices = []


    badChar = getBadChar(P)
    goodSuffix = getGoodSuffix(P)


    while i < s:
        while (j > 0):
            if i + j > s:
                return indices


            strOfS = S[i + j - 1:i + p]
            strOfP = P[j - 1:]


            if strOfS == strOfP:
                j = j - 1
            else:
                i = i + max(goodSuffix.setdefault(strOfP[1:], p), j - badChar.setdefault(S[i + j - 1], 0))
                j = p
            if j == 0:
                indices.append(i)
                i += 1
                j = len(P)
    return indices


S = "mnommnomn"
P = "mnomn"
result = BM(S, P)
print(result)

3. Sunday

给定字符串 S：mnommpomnomn

待匹配字符 P：mnomn

步骤

step1. 字符串S，P头部对齐。

step2. 从左到右比较字符，在匹配失败时获取字符串S中失败字符的下一位字符，在字符串P中获取该字符。若该字符没有在P中出现则对应的移动位数 = P的长度 + 1；否则，移动位数 = P的长度 - 该字符在P中最右出现的索引 。

code

def move(P, p, char):
    index = p + 1
    if char not in P: return index
    for i in range(p):
        if P[i] == char: index = p - i
    return index


def sunday(S, P):
    if not P: return [0]
    p, s = len(P), len(S)
    temp_index = 0
    indices = []


    while temp_index + p <= s:
        p_head_index = 0
        s_head_index = temp_index
        print(s_head_index, p_head_index)


        while s_head_index < s and p_head_index < p and S[s_head_index] == P[p_head_index]:
            s_head_index += 1
            p_head_index += 1


            if p_head_index == p:
                indices.append(temp_index)
                temp_index += 1


        if temp_index + p >= s: break
        temp_index += move(P, p, S[temp_index + p])
    return indices
S = "mnommpomnomn"
P = "mnomn"
result = sunday(S, P)
print(result)