《算法》笔记 15 - 子字符串查找

《算法》笔记 15 - 子字符串查找

  • 隐式回退

  • 性能

  • 显式回退

  • Knuth-Morris-Pratt算法

  • 确定有限状态自动机

  • DFA的构造

  • 性能

  • Boyer-Moore算法

  • 跳跃表的构建

  • 性能

  • Rabin-Karp指纹字符串算法

  • 关键思想

  • Horner方法

  • 性能

  • 字符串的一种基本操作就是子字符串查找。比如在文本编辑器或是浏览器中查找某个单词时,就是在查找子字符串。子字符串的长度(可能为100或1000)相对于整个文本的长度(可能为100万甚至是10亿)来说一般是很短的,在如此多的字符中找到匹配的模式是一个很大的挑战,为此计算机科学家们发明了多种有趣、经典且高效的算法。

    ### 暴力子字符串查找算法

    要解决这个问题,首先想到的是暴力查找的方法,在文本中模式可能出现匹配的任何地方检查是否匹配。

    #### 隐式回退

    首先是隐式回退的实现方式,之所以叫隐式回退,在与显式回退的实现对比后就明白原因了。

    
    public static int search(String pat, String txt) {
    
    int patL = pat.length();
    
    int txtL = txt.length();
    
      
    
    for (int i = 0; i <= txtL - patL; i++) {
    
    int j;
    
    for (j = 0; j < patL; j++)
    
    if (txt.charAt(i + j) != pat.charAt(j))
    
    break;
    
    if (j == patL)
    
    return i;
    
    }
    
    return txtL;
    
    }
    
    

    用一个索引i跟踪文本,另一个索引j跟踪模式。对于每个i,代码首先将j重置为0,并不断把它加1,直到找到了一个不匹配的字符,或者j增加到patL,此时就找到了匹配的子字符串。

    #### 性能

    在一般情况下,索引j增长的机会很少,绝大多数时候在比较第一个字符是就会产生不匹配。

    在长度为N的文本中,查找长度为M的子字符串时:

    • 在最好情况下,对于每个i,在索引j=0时就发现了不匹配,一共需要进行N次字符比较;

    • 在最坏的情况下,对于前N-1个i,索引j都需要增加到M-1次,才会发现不匹配,最后一次匹配,比如文本和模式都是一连串的A接一个B。这种情况下,对于N-M+1个可能的匹配位置,都需要M次比较,一共需要进行M*(N-M+1)次比较,因为N远大于M,所以忽略小数值后结果为~NM。

    #### 显式回退

    
    public static int search1(String pat, String txt) {
    
    int j, patL = pat.length();
    
    int i, txtL = txt.length();
    
      
    
    for (i = 0, j = 0; i <= txtL && j < patL; i++) {
    
    if (txt.charAt(i) == pat.charAt(j))
    
    j++;
    
    else {
    
    i -= j;
    
    j = 0;
    
    }
    
    }
    
    if (j == patL)
    
    return i - patL;
    
    else
    
    return txtL;
    
    }
    
    

    与隐式回退一样,也使用了索引i和j分别跟踪文本和模式的字符,但这里的i指向的是匹配过的字符序列的末端,所以这里的i相当与隐式回退中的i+j,如果字符不匹配,就需要回退i和j的位置,将j回退为0,指向模式的开头,将i指向本次匹配的开始位置的下一个字符。

    隐式回退的实现方式中,匹配位置的的末端字符是通过i+j指定的,所以只需要将j重新设为0,就实现了文本和模式字符的回退。

    ### Knuth-Morris-Pratt算法

    暴力算法在每次出现不匹配时,都会回退到本次匹配开始位置的下一个字符,但其实在不匹配时,就能知道一部分文本的内容,因此可以利用这些信息减少回退的幅度,Knuth-Morris-Pratt算法(简称KMP算法)就是基于这种思想。

    比如,假设文本只有A和B构成,那么在查找模式字符串为B A A A A A A A时,如果在匹配到第6个字符时出现不匹配,此时可以确定文本中的前6个字符就是B A A A A B,接下来不需要回退i,只需将i+1, j+2后,继续和模式的第二个字符匹配即可,因为模式的第一个字符是B,而上一次匹配失败的末尾字符也是B。

    而对于文本A A B A A B A和模式A A B A A A,在文本的第6个字符处发现不匹配后,应该从第4个字符开始重新匹配,这样就不会错过已经匹配的部分了。

    KMP算法的主要思想就是提前判断如何重新开始查找,而这种判断只取决于模式本身。

    #### 确定有限状态自动机

    KMP算法中不会回退文本索引i,而是使用一个二维数组dfa来记录匹配失败时模式索引j应该回退多远。对于每个字符c,在比较了c和pat.charAt(j)之后,dfa[c][i]表示的是应该和下个文本字符比较的模式字符的位置。

    这个过程实际上是对确定有限状态自动机(DFA)的模拟,dfa数组定义的正是一个确定有限状态自动机。DFA由状态(数字标记的圆圈)和转换(带标签的箭头)组成,模式中的每个字符都对应着一个状态,用模式字符串的索引值表示。

    【DFA】图和数组

    在标记为j的状态中检查文本中的第i个字符时,自动机会沿着转换dfa[txt.charAt(i)][j]前进并继续将i+1,对于一个匹配的转换,就向右移动一位,对于一个不匹配的智慧,就根据自动机的指示回退j。自动机从状态0开始,如果到达了最终的停止状态M,则查找成功。

    #### DFA的构造

    DFA是KMP算法的核心,构造给定模式对应的DFA也是这个算法的关键问题。DFA指示了应该如何处理下一个字符。如果在pat.charAt(j)处匹配成功,DFA应该前进到状态j+1。但如果匹配失败,DFA会从已经构造过的模式中获取到需要的信息,以模式 A B A B A C的构造过程举例:

    下面表格表示dfa[][],横向表头表示模式字符,括号中是当前的状态。

    1.初始状态,各位置都是0:

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|0|0|0|0|0|0|

    B|0|0|0|0|0|0|

    C|0|0|0|0|0|0|

    2.先看字符匹配成功时的情况,这时对应的状态会指向下一个状态:

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|0|3|0|5|0|

    B|0|2|0|4|0|0|

    C|0|0|0|0|0|6|

    3.在状态0,匹配失败时,无论是B还是C都退到初始状态,重新开始;

    4.在状态1,匹配失败时,如果此时的字符为A,则文本为A A,可以跳过状态0,直接到状态1,与A(0)行为一致,所以将A(0)的值复制到B(1),在DFA中对应的值也为1;而对于字符C,文本为A C,只能退回到状态0,重新开始

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|1|||||

    B|0|2|||||

    C|0|0|||||

    5.在状态2,匹配失败时,如果此时的字符为B,则文本为A B B,回到状态0;如果是字符C,文本为A B C,也只能退回到状态0。

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|1|3||||

    B|0|2|0||||

    C|0|0|0||||

    6.在状态3,匹配失败时,如果此时的字符为A,则文本为A B A A,直接到状态1;如果是字符C,文本为A B A C,回到状态0

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|1|3|1|||

    B|0|2|0|4|||

    C|0|0|0|0|||

    7.在状态4,匹配失败时,如果此时的字符为B,则文本为A B A B B,回到状态0;如果是字符C,文本为A B A B C,回到状态0

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|1|3|1|5||

    B|0|2|0|4|0||

    C|0|0|0|0|0||

    8.在状态5,匹配失败时,如果此时的字符为a,则文本为A B A B A A,回到状态1;如果是字符B,文本为A B A B A B,回到状态4,因为前面的A B A B都是匹配的,可以跳过。

    -|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)

    -:|:-:|:-:|:-:|:-:|:-:|:-:

    A|1|1|3|1|5|1|

    B|0|2|0|4|0|4|

    C|0|0|0|0|0|6|

    通过以上过程可知,在计算状态为j的DFA时,总能从尚不完整、已经计算完成的j-1个状态中得到所需的信息。

    
    dfa[pat.charAt(0)][0] = 1;
    
    for (int X = 0, j = 1; j < M; j++) {
    
    for (int c = 0; c < R; c++)
    
    dfa[c][j] = dfa[c][X];
    
    dfa[pat.charAt(j)][j] = j + 1;
    
    X = dfa[pat.charAt(j)][X];
    
    }
    
    

    代码中,用X维护了每次重启时的状态,然后具体的做法是:

    • 匹配失败时,将dfa[][X]复制到dfa[][j];

    • 匹配成功时,将dfa[pat.chatAt(j)][j]的值设为j+1;

    • 将X更新为dfa[pat.charAt(j)][X]

    初始化完成dfa后,查找的代码为:

    
    public int search(String txt) {
    
    int i, j, N = txt.length(), M = pat.length();
    
    for (i = 0, j = 0; i < N && j < M; i++) {
    
    j = dfa[txt.charAt(i)][j];
    
    }
    
    if (j == M)
    
    return i - M;
    
    else
    
    return N;
    
    }
    
    

    #### 性能

    在长度为N的文本中,查找长度为M的子字符串时,KMP算法会先初始化dfa,访问模式字符串中的每个字符一次,查找时在最坏情况下,会把文本中的字符都访问一次,所以KMP算法访问的字符最多为N+M个。

    KMP算法为最坏情况提供线性级别运行时间的保证。虽然在实际应用中,KMP算法相比暴力算法的速度优势并不明显,因为现实情况下的文本和模式一般不会有很高的重复性。

    但KMP算法还有一个非常重要的优点,就是它不需要在输入中回退,这使得KMP算法非常适合在长度不确定的输入流中进行查找,而那些需要回退的算法在处理这种输入时却需要复杂的缓冲机制。

    ### Boyer-Moore算法

    KMP算法不需要在输入中回退,但接下来学习的Boyer-Moore算法却利用回退获得了巨大的性能收益。

    Boyer-Moore算法是从右向左扫描模式字符串的,比如在查找模式字符串B A A B B A A时,如果匹配了第7、第6个字符,然后在第5个字符处匹配失败,那么就可以知道文本中对应的第5 6 7个字符分别是X A A,而X必然不是B,接下来就可以直接跳到第14个字符了。但并不是每次都能前进这么大的幅度,因为模式的结尾部分也可能出现在文本的其他位置,所以和KMP算法一样,这个算法也需要一个记录重启位置的数组。

    #### 跳跃表的构建

    有了记录重启位置的数组,就可以在匹配失败时,知道应该向右跳跃多远了,使用一个right数组记录字母表中的每个字符在模式中出现的最靠右的地方,如果字符在模式中不存在,则表示为-1。right数组又称为跳跃表。

    构建跳跃表时,先将所有元素设为-1,然后对于0到M-1的j,将right[pat.chatAt(j)]设为j。

    
    public BoyerMoore(String pat) {
    
    this.pat = pat;
    
    int M = pat.length();
    
    int R = 256;
    
    right = new int[R];
    
    for (int c = 0; c < R; c++)
    
    right[c] = -1;
    
    for (int j = 0; j < M; j++)
    
    right[pat.charAt(j)] = j;
    
    }
    
    

    模式 N E E D L E对应的跳跃表为

    
    A B C D E ... L M N
    
    -1 -1 -1 3 5 -1 4 -1 0
    
    

    算法会使用一个索引i在文本从左向右移动,用索引j在模式中从右向左移动,然后不断检查txt.charAt(i+j)和pat.charAt(j)是否匹配,如果对于模式中的所有字符都匹配,则查找成功;如果匹配失败,分三种情况处理:

    • 如果造成匹配失败的字符不在模式中,则将模式字符串向右移动j+1个位置,小于这个偏移量都会使模式字符串覆盖的区域中再次包含该字符;
    
    . . . T L E . . .
    
    N E E D L E
    
    ^ ^
    
    i j
    
      
    
    . . . T L E . . .
    
    N E E D L E
    
    ^ ^
    
    i增大j+1 j重置为M-1
    
      
    
    
    • 如果字符在模式中,则根据跳跃表,使该字符和它在模式字符串中对应最右的位置对齐,小于这个偏移量也会使该字符与模式中其它字符重叠;
    
    . . . N L E . . .
    
    N E E D L E
    
    ^ ^
    
    i j
    
      
    
    . . . N L E . . .
    
    N E E D L E
    
    ^
    
    i增大j-right["N"]
    
    
    • 如果根据跳跃表得出的结果,无法使模式字符串向右移动,则将i+1,保证至少向右移动了一个位置。
    
    . . . . . E L E . . .
    
    N E E D L E
    
    ^ ^
    
    i j
    
      
    
    . . . . . E L E . . .
    
    N E E D L E
    
    这种情况会使模式字符串向右移动,只能将i+1
    
      
    
    . . . . . E L E . . .
    
    N E E D L E
    
    ^
    
    i=i+1
    
    

    查找算法的实现为:

    
    public int search(String txt) {
    
    int N = txt.length();
    
    int M = pat.length();
    
    int skip;
    
    for (int i = 0; i <= N - M; i += skip) {
    
    skip = 0;
    
    for (int j = M - 1; j >= 0; j--) {
    
    if (pat.charAt(j) != txt.charAt(i + j)) {
    
    skip = j - right[txt.charAt(i + j)];
    
    if (skip < 1)
    
    skip = 1;
    
    break;
    
    }
    
    }
    
    if(skip==0) return i;
    
    }
    
    return N;
    
    }
    
    

    #### 性能

    最好情况下,每次跳跃的距离都是M,那么最终只需要N/M次比较。

    在最坏的情况下,跳跃失效,等同于暴力算法,比如在一连串A A A A A ...中查找B A A ...,这时需要M*N次比较。

    在实际应用场景中,模式字符串中仅含有字符集中的少量字符是很常见的,因此几乎所有的比较都会使算法跳过M个字符,所以一般来说算法需要~N/M次比较。

    ### Rabin-Karp指纹字符串算法

    M.O.Rabin和R.A.Karp发明的基于散列的字符串查找算法,与前面两种算法的思路完全不同。计算模式字符串的散列值,然后使用相同的散列函数,计算文本逐位计算M个字符的散列值,如果得出的散列值与模式字符串的散列值相同,就再继续逐字符验证一次,确保匹配成功。

    但如果直接按照这种方式,得出的算法效率减比暴力算法还要低很多,而Rabin和Karp发明了一种能够在常数时间内算出M个字符的子字符串散列值的方法,这使得这种算法的运行时间降低到了线性级别。

    ### 关键思想

    散列函数一般使用除留余数法,除数选择一个尽量大的素数。算法的关键在于只要知道上一个位置M个字符的散列值,就能够快速得算出下一个位置M个字符的散列值。以数字字符串来举例:

    
    2   6   5   3   5 %997=613
    
      
    
    5   9   2   6   5   3   5
    
    5   9   2   6   5 %997=442
    
        9   2   6   5   3 %997=929  
    
            2   6   5   3   5 %997=613(匹配)
    
    

    在上面的过程中,模式字符串26535可以看作一个十进制的数字,它要匹配的每M个字符也都可以看作是一个M为的整数,59265用997取余后的结果为442,接下来92653取余时不需要重头计算

    
    59265=5*10000+9265
    
    92653=9265+3*1
    
    所以
    
    92653=(59265-5*10000)*10+3*1
    
    

    而对于普通的字符串,如果它的字符集中有R个字符,则可以把这些字符串看作是R进制的数字,用t<sub>i</sub>表示txt.charAt(i),则:

    x<sub>i</sub>=t<sub>i</sub>R<sup>M-1</sup>+t<sub>i+1</sub>R<sup>M-2</sup>+...+t<sub>i+M-1</sub>R<sup>0</sup>

    与得出92653的过程一样,将模式字符串右移一位即等价于将x<sub>i</sub>替换为:

    x<sub>i+1</sub>=(x<sub>i</sub>-t<sub>i</sub>R<sup>M-1</sup>)R+t<sub>i+M</sub>

    ### Horner方法

    计算散列值时,如果是int值,可以直接取余,但对于一个相当于R进制的数字的字符串,要得出它的余数,就需要用Horner方法,Horner方法的理论依据是,如果在每次算术操作之后都将结果除Q取余,这等价于在完成了所有算术操作之后再将最后的结果除Q取余:

    
    private long hash(String key, int M) {
    
        long h = 0;
    
        for (int j = 0; j < M; j++)
    
            h = (R * h + key.charAt(j)) % Q;
    
        return h;
    
    }
    
    

    对于一个R进制的数字,从左至右,将它的每一位数字的散列值乘以R,加上这个数字,并计算除Q的余数。

    那么随着索引i的增加,逐位计算M个字符的散列值时,就可以利用跟Horner方法相同的原理了:

    
    public class RabinKarp {
    
    private String pat;
    
    private long patHash;
    
    private int M;
    
    private long Q;
    
    private int R = 256;
    
    private long RM;
    
      
    
    public RabinKarp(String pat) {
    
    this.pat = pat;
    
    M = pat.length();
    
    Q = longRandomPrime();
    
    RM = 1;
    
    for (int i = 1; i <= M - 1; i++)
    
    RM = (R * RM) % Q;
    
    patHash = hash(pat, M);
    
    }
    
      
    
    private boolean check(String txt, int i) {
    
    for (int j = 0; j < M; j++)
    
    if (pat.charAt(j) != txt.charAt(i + j))
    
    return false;
    
    return true;
    
    }
    
      
    
    private long hash(String key, int M) {
    
    long h = 0;
    
    for (int j = 0; j < M; j++)
    
    h = (R * h + key.charAt(j)) % Q;
    
    return h;
    
    }
    
      
    
    // a random 31-bit prime
    
    private static long longRandomPrime() {
    
    BigInteger prime = BigInteger.probablePrime(31, new Random());
    
    return prime.longValue();
    
    }
    
      
    
    public int search(String txt) {
    
    int N = txt.length();
    
    long txtHash = hash(txt, M);
    
    if (patHash == txtHash && check(txt, 0))
    
    return 0;
    
    for (int i = M; i < N; i++) {
    
    txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
    
    txtHash = (txtHash * R + txt.charAt(i)) % Q;
    
    if (patHash == txtHash)
    
    if (check(txt, i - M + 1))
    
    return i - M + 1;
    
    }
    
    return N;
    
    }
    
    }
    
    

    #### 性能

    取余所选的Q值是一个很大的素数,这里使用的是使用BigInteger.probablePrime生成的一个31位素数,其大小与2<sup>31</sup>接近,那么在将模式字符串的散列值与文本中M个字符的散列值比较时,产生冲突的概率约为2<sup>-31</sup>,这是一个极小的值,所以算法中的check方法可以省略掉,Rabin-Karp算法的性能为线性级别,