aibiology

Artificial intelligence in biology

0%

字符串匹配-KMP算法

Posted on Edited on

字符串

  • 子串 substring 字符串中任意个连续的字符组成的子序列称为该字符串的子串(Substring) \(S[i..j], i<=j\)

  • 子序列 subsequence 字符串\(S\)的子序列是从\(S\)中将若干元素提取出来并不改变相对位置形成的序列, \(S[p_1], S[p_2], .. S[p_k], 1<=p_1< p_2< p_k <= |S|\)。

  • 子串一定是子序列，但是子序列不一定是子串

  • 后缀 suffix
    后缀 是指从某个位置 i 开始到整个串末尾结束的一个特殊子串, \(suffis(S,i) = S[i..|S|-1]\)

  • 前缀 prefix
    前缀 是指从串首开始到某个位置 i 结束的一个特殊子串, \(prefix(S, i) = S[0..i], i<=|S|-1\)。

字符串匹配就是给定文本字符串(String)是一个长度为\(n\)的数组\(S[1..n]\), 模式(Pattern)是一个长度为\(m\)且\(m<=n\)的数组\(P[1..m]\)，在string中寻找 pattern的过程。

KMP算法

KMP (Knuth-Morris-Pratt) 字符串匹配算法，利用模式串的重复出现的字符实现跳跃，避免主串指针的回溯，仅仅后移模式串。 KMP 算法的核心是PMT(Partial Match Table)部分匹配表数组，PMT的值就是最长公共前后缀的长度，即字符串的前缀组合和后缀组合的交集中最长元素的长度。 在模式串中出现前后缀相同时候，在匹配的时候可以实现跳跃，

  • 利用PMT数组减少重复匹配的次数，提升效率。
  • 时间复杂度\(O(n+m)\)
  • Next 数组将PTM数组整体右移动一位，原先第一位为-1

第一步，PTM表格的制作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

def get_prefix(s: str) -> set:
    if len(s) == 1:
        return set()
    else:
        prefix = set()
        for i in range(1, len(s)):
            prefix.add(s[:i])
        return prefix

def get_suffix(s: str) -> set:
    if len(s) == 1:
        return set()
    else:
        suffix = set()
        for i in range(len(s)):
            suffix.add(s[i:])
        return suffix

def longest_prefix_suffix(suffix: set, prefix: set) -> int:
    inter = suffix & prefix
    if len(inter) == 0:
        return 0
    else:
        return max([len(i) for i in inter])

def getPTM(pat: str) -> list:
    ptm = [0 for i in range(len(pat))]
    for i in range(len(pat)):
        suffix = get_suffix(pat[:i+1])
        prefix = get_prefix(pat[:i+1])
        ptm[i] = longest_prefix_suffix(suffix, prefix)
    return ptm

a = 'abababca'
getPTM(a)
# [0, 0, 1, 2, 3, 4, 0, 1]

# p模式字符串 a b a b a b c a
# 下标        0 1 2 3 4 5 6 7
# PTM         0 0 1 2 3 4 0 1

# PTM[0], p[0]        即"a"的最长公共前后缀，显然为0, 前后缀均不包括字符串本身
# PTM[1], p[0] ~ p[1] 即"ab"的最长公共前后缀，显然为0
# PTM[2], p[0] ~ p[2] 即"aba"的最长公共前后缀，即"a", 长度为1
# PTM[3], p[0] ~ p[3] 即"abab"的最长公共前后缀，即"ab", 长度为2
# PTM[4], p[0] ~ p[4] 即"ababa"的最长公共前后缀，即"aba", 长度为3
# PTM[5], p[0] ~ p[5] 即"ababab"的最长公共前后缀，即"abab", 长度为4
# PTM[6], p[0] ~ p[6] 即"abababc"的最长公共前后缀, 显然为0, 后缀一定含c, 前缀一定含a
# PTM[7], p[0] ~ p[7] 即"abababca"的最长公共前后缀, 即"a", 长度为1,

第二步，Next数组生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 根据PTM去求 next 数组：next 数组相当于“PTM” 整体向右移动一位，然后初始值赋为-1。
# Next 数组就可以看成字符串匹配的过程，即，以模式字符串为主串，以模式字符串的前缀为目标字符串，
# 一旦字符串匹配成功，那么Next的值就是匹配成功的字符串的长度
# 这里最核心的点就是j的回溯。
# getNext的时间复杂度是 O(m)
def getNext(p):
    Next = [0 for i in range(len(p))]
    Next[0] = -1 
    i = 0
    j = -1
    while i < len(p)-1:
        # 匹配或者j跳到了最开始
        if j == -1 or p[i] == p[j]:
            i += 1
            j += 1
            Next[i] = j
        # 匹配不成功则在前面的子串中继续搜索
        else:
            j = Next[j]
    return Next

# 若字符串只有一个元素，不执行while，Next[0] = -1
# 如字符串有多个元素,如a='abababca'
# i=0, j=-1; 执行一次while，执行if，i=1,j=0, Next[1] = 0;
# i=1, j=0; 执行while, 如果p[2]=p[0]=a匹配，i=2,j=1, Next[2] = 1; 
#                      如果不匹配，j=Next[0]=-1

a = 'abababca'
getNext(a)
# [-1, 0, 0, 1, 2, 3, 4, 0]

第三步，KMP匹配算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def KMP(pat:str, target:str) -> int:
    i, j = 0, 0
    Next = getNext(pat) # O(m)
    # O(n)
    while i < len(target) and j < len(pat):
        if j == -1 and target[i] == pat[j]:
            i += 1
            j += 1
        else:
            j = Next[j]
    if j == len(pat):
        return i - j
    else:
        return -1 
    
p = "ATG"
t = "ATCGATCGATG"
KMP(t, p)
# 8