《演算法》筆記 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	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)
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	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)
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_i表示txt.charAt(i)，則：
x_i=t_iR^M-1+t_i+1R^M-2+...+t_i+M-1R⁰
與得出92653的程序一樣，將模式字串右移一位即等價于將x_i替換為：
x_i+1=(x_i-t_iR^M-1)R+t_i+M

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³¹接近，那么在將模式字串的散列值與文本中M個字符的散列值比較時，產生沖突的概率約為2^-31，這是一個極小的值，所以演算法中的check方法可以省略掉，Rabin-Karp演算法的性能為線性級別，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102319.html

標籤：其他

上一篇：《演算法》筆記 14 - 單詞查找樹

下一篇：Python修改windows注冊表實作封禁usb埠