经典算法之字符串匹配

1、BF算法

BF（Brute Force）算法就是朴素的暴力匹配。BF算法的基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功，则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的子串，则匹配失败。

def BF(s, p):
    '''
   Brute-Force算法实现字符串匹配
    '''
    indies = []
    n = len(s)
    m = len(p)
    for i in range(n - m + 1):
        index = i  
        for j in range(m): 
            if s[index] == p[j]: 
                index += 1
            else: 
                break
        if index - i == m: 
            indies.append(i) 
        
    return indies

print(BF('abcxabcdabcdabcy','abcdabcy'))

2、KMP算法

KMP（Knuth-Morris-Pratt）算法是对BF算法的改进，差别在于KMP算法在出现字符串不相等的情况时，不需要返回到字串的开头重新比较。具体过程就是计算一张部分匹配表来改进移动距离。

def getNextList(s):
    n = len(s)
    nextList = [0, 0]
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = nextList[j]
        if s[i] == s[j]:
            j += 1
        nextList.append(j)
    return nextList

def KMP(s, p):
    '''
    Knuth-Morris-Pratt算法实现字符串匹配
    '''
    n = len(s)
    m = len(p)
    nextList = getNextList(p)
    indies = []
    j = 0
    for i in range(n):
        while s[i] != p[j] and j > 0:
            j = nextList[j]

        if s[i] == p[j]:
            j += 1
            if j == m:
                indies.append(i-m+1)
                j = nextList[j]
    return indies

print(KMP('abcxabcdabcdabcy','abcdabcy'))

3、BM算法

BM（Boyer-Moore）算法是对KMP进一步的改进。总体来说BM算法效率是高于KMP算法的，文本量越大BM算法的效果越明显。BM算法通过两张表来改进移动的距离。

def getBMBC(pattern):
    # 预生成坏字符表
    BMBC = dict()
    for i in range(len(pattern) - 1):
        char = pattern[i]
        # 记录坏字符最右位置（不包括模式串最右侧字符）
        BMBC[char] = i + 1
    return BMBC

def getBMGS(pattern):
    # 预生成好后缀表
    BMGS = dict()

    # 无后缀仅根据坏字移位符规则
    BMGS[''] = 0

    for i in range(len(pattern)):

        # 好后缀
        GS = pattern[len(pattern) - i - 1:]

        for j in range(len(pattern) - i - 1):

            # 匹配部分
            NGS = pattern[j:j + i + 1]

            # 记录模式串中好后缀最靠右位置（除结尾处）
            if GS == NGS:
                BMGS[GS] = len(pattern) - j - i - 1
    return BMGS

def BM(string, pattern):
    '''
    Boyer-Moore算法实现字符串查找
    '''
    m = len(pattern)
    n = len(string)
    i = 0
    j = m
    indies = []
    BMBC = getBMBC(pattern=pattern)  # 坏字符表
    BMGS = getBMGS(pattern=pattern)  # 好后缀表
    while i < n:
        while (j > 0):
            if i + j -1 >= n: # 当无法继续向下搜索就返回值
                return indies

            # 主串判断匹配部分
            a = string[i + j - 1:i + m]

            # 模式串判断匹配部分
            b = pattern[j - 1:]

            # 当前位匹配成功则继续匹配
            if a == b:
                j = j - 1

            # 当前位匹配失败根据规则移位
            else:
                i = i + max(BMGS.setdefault(b[1:], m), j - BMBC.setdefault(string[i + j - 1], 0))
                j = m

            # 匹配成功返回匹配位置
            if j == 0:
                indies.append(i)
                i += 1
                j = len(pattern)

print(BM('abcxabcdabcdabcy','abcdabcy'))

4、sunday算法

sunday算法比BM算法更快，主体思路与BM算法相同，主要区别是模式串与文本串按从前往后顺序匹配比较。

def char_search(char_, str_):
    for c in str_:
        if char_ == c:
            return True
    return False

def sunday_match(s, pattern):
    i = 0
    positions = []

    while i < (len(s)-len(pattern)+1):

        if s[i:i+len(pattern)] == pattern:
            positions.append(i)
            i = i + 1
            print("is  equal, jump 1 step, i: {}, char: {}".format(i, s[i]))
        elif not char_search(s[i+len(pattern)], pattern):
            i = i + len(pattern) + 1
            print("not equal, jump n step, i: {}, char: {}".format(i, s[i]))
        else:
            i = i + 1
            print("not equal, jump 1 step, i: {}, char: {}".format(i, s[i]))

    return positions

print(sunday_match('887abchsabc92abbiabcaabc', 'abc'))

5、Aho-corasick Automaton算法（AC自动机）

AC自动机（Aho-Corasick Automaton）是多模匹配算法的一种。所谓多模匹配，是指在字符串匹配中，模式串有多个。前面所介绍的KMP、BM为单模匹配，即模式串只有一个。

class Node(object):

    def __init__(self):
        self.next = {}
        self.fail = None
        self.isWord = False

class Ahocorasick(object):
    def __init__(self):
        self.__root = Node()

    def addWord(self, word):
        '''
        添加关键词到Tire树中
        '''
        tmp = self.__root
        for i in range(0, len(word)):
            if word[i] not in tmp.next:
                tmp.next[word[i]] = Node()
            tmp = tmp.next[word[i]]
        tmp.isWord = True

    def make(self):
        '''
        构建自动机，失效函数
        '''
        tmpQueue = []
        tmpQueue.append(self.__root)
        while(len(tmpQueue) > 0):
            temp = tmpQueue.pop()
            p = None
            for k, v in temp.next.items():
                if temp == self.__root:
                    temp.next[k].fail = self.__root
                else:
                    p = temp.fail
                    while p is not None:
                        if k in p.next:
                            temp.next[k].fail = p.next[k]
                            break
                        p = p.fail
                    if p is None :
                        temp.next[k].fail = self.__root
                tmpQueue.append(temp.next[k])

    def search(self, content):
        p = self.__root
        result = []
        startWordIndex = 0
        endWordIndex = -1
        currentPosition = 0

        while currentPosition < len(content):
            word = content[currentPosition]
            # 检索状态机，直到匹配
            while word not in p.next and p != self.__root:
                p = p.fail

            if word in p.next:
                if p == self.__root:
                    # 若当前节点是根且存在转移状态，则说明是匹配词的开头，记录词的起始位置
                    startWordIndex = currentPosition
                # 转移状态机的状态
                p = p.next[word]
            else:
                p = self.__root

            if p.isWord:
                # 若状态为词的结尾，则把词放进结果集
                result.append((startWordIndex, currentPosition))

            currentPosition += 1
        return result

    def replace(self, content):
        replacepos = self.search(content)
        result = content
        for i in replacepos:
            result = result[0:i[0]] + (i[1] - i[0] + 1) * u'*' + content[i[1] + 1:]
        return result


if __name__ == '__main__':
    ah = Ahocorasick()
    text = '中国科学技术大学位于安徽合肥，是一所理工科大学，又称为南七技校。'
    patterns = '科学 大学 理工科 技校'
    words = patterns.split(' ')
    for w in words:
        ah.addWord(w)
    ah.make()
    results = ah.search(text)
    print(results)
    if len(results) == 0:
        print('No find.')
    else:
        print(len(results),' matching results are listed below.')
        print('-------' + '-'*len(text) + '-------')
        print(text)
        count = 0
        for site in results:
            w = text[site[0]:site[1]+1]
            count += 1
            print('  '*site[0] + w + '  '*(len(text)-site[1]) + '  ' + str(site[0]) + '  ' + str(count))
        print('-------' + '-'*len(text) + '-------')