技術文章 » 搜尋中常見資料結構與演演算法探究（二）

搜尋中常見資料結構與演演算法探究（二）

2022-10-12 12:00:42

本文介紹了幾個常見的匹配演演算法，通過演演算法過程和演演算法分析介紹了各個演演算法的優缺點和使用場景，併為後續的搜尋文章做個鋪墊；讀者可以通過比較幾種演演算法的差異，進一步瞭解匹配演演算法演進過程以及解決問題的場景；KMP演演算法和Double-Array TireTree是其中演演算法思想的集大成者，希望讀者重點關注。

1 前言

上文探究了資料結構和演演算法的一些基礎和部分線性資料結構和部分簡單非線性資料結構，本文我們來一起探究圖論，以及一些字串模式匹配的高階資料結構和演演算法。【搜尋中常見資料結構與演演算法探究（一）】（https://developer.jdcloud.com/article/2153）

搜尋作為企業級系統的重要組成部分，越來越發揮著重要的作用，ES已經成為每個網際網路企業必備的工具集。而作為搜尋的基礎部分，文字匹配的重要性不言而喻。文字匹配不僅為精確搜尋提供了方法，而且為模糊匹配提供了演演算法依據。比如相似度演演算法，最大搜尋長度演演算法都是在匹配演演算法的基礎上進行了變種和改良。

2 圖論基礎

2.1 圖的基本概念

以我們物流的抽象模型為例：每個配送中心是一個頂點，由兩個頂點表示的配送中心間如果存在一條幹線運輸線，那麼這兩個頂點就用一條邊連線。邊可以由一個權，表示時間、距離和運輸的成本。我們願意迅速確定任何兩個配送中心的最佳線路。這裡的「最佳」可以是指最少邊數的路徑，也即經過的配送中心最少；也可以是對一種或所有權總量度所算出的最佳者。

2.2 圖的表示方法

我們考慮實用情況，以有向圖為例：
我們假設可以以省會城市開始對頂點編號。如下圖

1）鄰接矩陣
表示圖的一種簡單的方法是使用一個二維資料，稱為鄰接矩陣表示法。有一個二維陣列A，對於每條邊（u，v），置A[u][v]等於true；否則陣列元素就是false。如果邊有一個權，那麼可以置A[u][v]等於該權，而使用很大或者很小的權作為標記表示不存在的邊。雖然這種表示方法的優點是簡單，但是，它的空間複雜度為θ（|V|^2）,如果圖的邊不是很多（稀疏的），那麼這種表示的代價就太大了。程式碼如下：

/**
* <p/>
* Description: 使用鄰接矩陣的圖表示法
* <p/>
* Company: <a href=www.jd.com>京東</a>
*
* @author <a href=mailto:[email protected]>pankun8</a>
* @date 2021/11/11 15:41
*/
@Data
@NoArgsConstructor
public class Graph<T extends Node>{
/**
* 圖的節點數
*/
private int n;

/**
* 圖
*/
private T[] data;

/**
* 是否是有向圖
*/
private Boolean directed;

/**
* 鄰接矩陣
*/
private int[][] matrix;

public Graph(T[] data , Boolean directed){
this.n = data.length;
this.data = data;
this.directed = directed;
matrix = new int[n][n];
}


public void init(T[] data , Boolean directed){
this.n = data.length;
this.data = data;
this.directed = directed;
matrix = new int[n][n];
}
/**
*
* @param v 起點
* @param w 終點
* @param value 權重
*/
public void addEdge(int v , int w , int value){
if((v >=0 && v < n) && (w >= 0 && w < n)){
if(hasEdge(v,w) == value){
return;
}
matrix[v][w] = value;
if(!this.directed){
matrix[w][v] = value;
}
n ++;
}
}

//判斷兩個節點中是否以及存在邊
public int hasEdge(int v, int w){
if((v >=0 && v < n) && (w >= 0 && w < n)){
return matrix[v][w];
}
return 0;
}

/**
* 狀態轉移函數
* @param index
* @param value
* @return
*/
public int stateTransfer(int index , int value){
int[] matrix = this.matrix[index];
for (int i = 0; i < matrix.length; i++) {
if(matrix[i] == value){
return i;
}
}
return Integer.MAX_VALUE;
}
}

2）鄰接表
如果圖是稀疏的，那麼更好的解決辦法是使用鄰接表。

2.3 圖的搜尋演演算法

從圖的某個訂單出發，存取途中的所有頂點，並且一個頂點只能被存取一次。圖的搜尋（遍歷）演演算法常見的有兩種，如下：

  • 深度優先搜尋演演算法（DFS）
  • 廣度優先搜尋演演算法（BFS）

3 資料結構與演演算法

3.1 BF（Brute Force）演演算法

3.1.1 演演算法介紹

BF（Brute Force）演演算法也可以叫暴力匹配演演算法或者樸素匹配演演算法。

3.1.2 演演算法過程

在講解演演算法之前，我們先定義兩個概念，方便後面講解。他們分別是主串（S）和模式串（P）。比如說要在字串A中查詢字串B，那麼A就是主串，B就是模式串。我們把主串的長度記作n，模式串的長度記作m，並且n>m。演演算法過程如下圖：

3.1.3 演演算法分析

BF演演算法從很「暴力」，當然也就比較簡單，好懂，但是響應的效能也不高極端情況下時間複雜度函數為O(m*n)。
儘管理論上BF演演算法的時間複雜度很高，但在實際的開發中，它卻是一個比較常用的字串匹配演演算法，主要原因有以下兩點：

  • 樸素字串匹配演演算法思想簡單，程式碼實現也非常簡單，不容易出錯，容易偵錯和修改。
  • 在實際的軟體開發中，模式串和主串的長度都不會太長，大部分情況下，演演算法執行的效率都不會太低。

3.2 RK（Rabin-Karp）演演算法

3.2.1 演演算法介紹

RK演演算法全程叫Rabin-Karp演演算法，是有它的兩位發明者Rabin和Karp的名字來命名，這個演演算法理解並不難，他其實是BF演演算法的升級版。

3.2.2 演演算法過程

3.2.3 演演算法分析

在BF演演算法中當字串不匹配時，需要比對每一個字元，如果不能匹配則重新調整I，J的值重新比對每一個字元，RK的思路是將模式串進行雜湊演演算法得到s=hash(P)，然後將主串分割成n-m+1個子串，分別對其進行hash演演算法，然後逐個和s進行比對，減少逐個字串比對的次數。其中hash函數的具體實現可自行選擇。
整個RK演演算法包含兩部分：

  • 計算模式串雜湊和子串的雜湊；
  • 模式串雜湊和子串雜湊的比較；

第一部分的只需要掃描一遍主串就能計算出所有子串的雜湊值，這部分的時間複雜度是O(n)。模式串雜湊值與每個子串雜湊之間的比較的時間複雜度是O(1)，總共需要比對n-m+1次，所以這部分的時間複雜度為O(n)。所以RK演演算法的整體時間複雜度為O(n)。

3.3 KMP演演算法

3.3.1 演演算法介紹

KMP演演算法是一種線性時間複雜度的字串匹配演演算法，它是對BF(Brute-Force)演演算法的改進。KMP演演算法是由D.E.Knuth與V.R.Partt和J.H.Morris一起發現的，因此人們稱它為Knuth-Morris-Pratt演演算法，簡稱KMP演演算法。

前面介紹了BF演演算法，缺點就是時間消耗很大，KMP演演算法的主要思想就是：在匹配過程中發生匹配失敗時，並不是簡單的將模式串P的下標J重新置為0，而是根據一些匹配過程中得到的資訊跳過不必要的匹配，從而達到一個較高的匹配效率。

3.3.2 演演算法過程

在介紹KMP演演算法之前，首先介紹幾個字串的概念：

  • 字首：不包含最後一個字元的所有以第一個字元開頭的連續子串；
  • 字尾：不包含第一個字元的所有以最後一個字元結尾的連續子串；
  • 最大公共前字尾：字首集合與字尾集合中長度最大的子串；

例如字串abcabc
字首集合是a，ab，abc，abca，abcab
字尾集合為bcabc，cabc，abc，bc，c
最大公共前字尾為abc

KMP演演算法的過程如下圖：

那麼為什麼KMP演演算法會知道在匹配失敗時下標J回溯的那個位置呢？其實KMP演演算法在匹配的過程中將維護一些資訊來幫助跳過不必要的匹配，這個資訊就是KMP演演算法的重點，next陣列也叫做fail資料或者字首資料。下面我們來分析next陣列的由來

對於模式串P的每個元素P[j]，都存在一個實數k，使得模式串P開頭的k個字元(P[0]P[1]…P[k-1])依次於P[j]前面的k(P[j-k]P[j-k+1]…P[j-1])個字元相同。如果這樣的k有多個，則取最大的一個。模式串P中的每個位置j的字元都存在這樣的資訊，採用next陣列表示，即next[j]=MAX{k}。

從上述定義中可看到next(j)的邏輯意義就是求P[0]P[1]…P[j-1]的最大公共前字尾長度。程式碼如下：

public static void genNext(Integer[] next , String p){
int j = 0 , k = -1;
char[] chars = p.toCharArray();
next[0] = -1;
while(j < p.length() - 1){
if(k == -1 || chars[j] == chars[k]){
j++;k++;
next[j] = k;
}else{
k = next[k];//此處為理解難點
}
}
}

下面分析next的求解過程：

1）特殊情況
當j的值為0或者1的時候，它們的k值都為0，即next(0) = 0 、next(1) = 0。為了後面k值計算的方便，我們將next(0)的值設定為-1。
2）當P[j]==P[k]的情況
當P[j]P[k]時，必然有P[0]…P[k-1]P[j-k]…P[j-1]，因此有P[0]…P[k]==P[j-k]…P[j]，這樣就有next(j+1)=k+1。
3）當P[j]!=P[k]的情況
當P[j]!=P[k]時，必然後next(j)=k，並且next(j+1)<k；也就是說P[0]…P[k-1]=P[j-k]…P[j-1]，因此此時k值需要向左移動重新進行匹配，next陣列的作用就是在匹配失敗時進行下標左移，所以k=next(k)進行下一輪迴圈。
4）演演算法優化
上述演演算法有一個小問題就是當P[k]匹配失敗後會跳轉到next(k)繼續進行匹配，但是此時有可能P[k]=P[next(k)]，此時匹配肯定是失敗的所以對上述程式碼進行改進如下：

public void genNext(Integer[] next , String p){
int j = 0 , k = -1;
char[] chars = p.toCharArray();
next[0] = -1;
while(j < p.length() - 1){
if(k == -1 || chars[j] == chars[k]){
j++;k++;
if(chars[j] == chars[k]){
next[j] = next[k];//如果兩個相等
}else{
next[j] = k;
}
}else{
k = next[k];
}
}
}

3.3.3 演演算法分析

KMP演演算法通過消除主串指標的回溯提高匹配的效率，整個演演算法分為兩部分，next資料的求解，以及字串匹配，從上一節的分析可知求解next陣列的時間複雜度為O(m)，匹配演演算法的時間複雜度為O(n)，整體的時間複雜度為O(m+n)。KMP演演算法不是最快匹配演演算法，卻是名氣最大的，使用的範圍也非常廣。

3.4 BM演演算法

3.4.1 演演算法介紹

Boyer-Moore字串搜尋演演算法是一種非常高效的字串搜尋演演算法。它由Bob Boyer和J Strother Moore發明，有實驗統計它的效能是KMP演演算法的3-4倍。

3.4.2 演演算法過程

前面介紹的BF，KMP的演演算法的匹配過程雖然模式串的回溯過程不同，但是相同點都是從左往右逐個字元進行匹配，而BM演演算法則是採用的從右向左進行匹配，藉助壞字元規則（SKip(j)）和好字尾（Shift(j)）規則，能夠進行快速匹配。其中壞字元和好字尾示意如下圖

1）壞字元規則：在BM演演算法從右向左掃描的過程中，若發現某個字元S[i]不匹配時，則按照如下兩種情況進行處理：

  • 如果字元S[i]在模式串P中沒有出現，那麼從字元S[i]開始的m個文字顯然是不可能和P匹配成功，直接全部跳過該區域。
  • 如果字元S[i]在模式串P中出現，則以該字元進行對齊。

2）好字尾規則：在BM演演算法中，若發現某個字元不匹配的同時，已有部分字元匹配成功，則按照如下兩種情況進行處理：

  • 如果已經匹配的子串在模式串P中出現過，且子串的前一個字元和P[j]不相同，則將模式串移動到首次出現子串的前一個位置。
  • 如果已經匹配的子串在模式串P中沒有出現過，則找到已經匹配的子串最大字首，並移動模式串P到最大字首的前一個字元。

BM演演算法過程如下：

3.4.3 演演算法分析

在BM演演算法中，如果匹配失敗則取SKip(j)與Shift(j)中的較大者作為跳躍的距離。BM演演算法預處理階段的複雜度為O(m+n)，搜尋階段的最好的時間複雜度為O(n/m)，最壞的時間複雜為為O(n*m)。由於BM演演算法採用的是字尾匹配演演算法，並且通過壞字元和好字尾共同作用下，可以跳過不必要的一些字元，具體Shift(j)的求解過程可參看KMP演演算法的next()函數過程。

3.5 TireTree

3.5.1 演演算法介紹

在《搜尋中常見的資料結構與演演算法探究（一）》中，我們介紹過一種樹狀的資料結構叫做HashTree，本章介紹的TireTree就是HashTree的一個變種。TireTree又叫做字典樹或者字首樹，典型的應用是用於統計和排序大量的字串，所以經常被搜尋系統用於文字的統計或搜尋。

TireTree的核心思想是空間換時間。TrieTree是一種高效的索引方法，它實際上是一種確定有限自動機(DFA)，利用字串的公共字首來降低查詢時間的開銷以達到提高查詢效率的目的，非常適合多模式匹配。TireTree有以下基本性質：

  • 根節點不包含字元，除根節點外每個節點都包含一個字元。
  • 從根節點到某一個節點，路徑上經過的字元連線起來，為該節點對應的字串。
  • 每個節點對應的所有子節點包含的字元都不相同。

3.5.2 演演算法過程

TireTree構建與查詢
我們以《搜尋中常見的資料結構與演演算法探究（一）》案例二中提到的字謎單詞為例，共包含this、two、fat和that四個單詞，我們來探究一下TireTree的構建過程如下圖：

上述過程描述了that，two，fat，that四個單詞的插入TireTree的過程，其中黃色的節點代表有單詞存在。由於TireTree的構建的過程是樹的遍歷，所以查詢過程和建立過程可以視為一個過程。

3.5.3 演演算法分析

TireTree由於本身的特性非常適合字首查詢個普通查詢，並且查詢的時間複雜度為O(log(n))，和hash比較在一些場景下效能要優於甚至取代hash，例如說字首查詢（hash不支援字首查詢）。

雖然TireTree的查詢速度會有一定的提升但是缺不支援字尾查詢，並且TireTree對空間利用率不高，且對中文的支援有限。

3.6 AC自動機

3.6.1 演演算法介紹

AC自動機（Aho-Corasick automation）該演演算法在1975年產生於貝爾實驗室，是著名的多模匹配演演算法之一。要搞懂AC自動機，先得有TireTree和KMP模式匹配演演算法的基礎知識，上述章節有TireTree和KMP演演算法的詳細介紹。

3.6.2 演演算法過程

AC自動機的構建過程需要如下步驟：

  • TireTree的構建，請參看TireTree章節
  • fail指標的構建 - 使當前字元失配時跳轉到具有最長公共前字尾的字元繼續匹配。如同 KMP演演算法一樣， AC自動機在匹配時如果當前字元匹配失敗，那麼利用fail指標進行跳轉。由此可知如果跳轉，跳轉後的串的字首，必為跳轉前的模式串的字尾並且跳轉的新位置的深度一定小於跳之前的節點。fail指標的求解過程可是完全參照KMP演演算法的next指標求解過程，此處不再贅述。
  • AC自動機查詢 - 查詢過程和TireTree相同，只是在查詢失敗的時候感覺fail指標跳轉到指定的位置繼續進行匹配。

3.6.3 演演算法分析

AC自動機利用fail指標阻止了模式串匹配階段的回溯，將時間複雜度優化到了O(n)。

3.7 Double-Array-TireTree

3.7.1 演演算法介紹

前面提到過TireTree雖然很完美，但是空間利用率很低，雖然可以通過動態分配陣列來解決這個問題。為了解決這個問題我們引入Double-Array-TireTree，顧名思義Double-Array-TireTree就是TireTree壓縮到兩個一維陣列BASE和CHECK來表示整個樹。Double-Array-TireTree擁有TireTree的所有優點，而且刻服了TireTree浪費空間的不足，使其應用範圍更加廣泛，例如詞法分析器，圖書搜尋，拼寫檢查，常用單詞過濾器，自然語言處理 中的字典構建等等。

3.7.2 演演算法過程

在介紹演演算法之前，我們提前簡單介紹一個概念DFA（下一篇詳細介紹）。DFA（Deterministic Finite State）有限自動機，通俗來講DFA是指給定一個狀態和一個輸入變數，它能轉到的下一個狀態也就確定下來，同時狀態是有限的。

Double-Array-TireTree構建
Double-Array-TireTree終究是一個樹結構，樹結構的兩個重要的要素便是前驅和後繼，把樹壓縮在雙陣列中，只需要保持能查到每個節點的前驅和後繼。首先要介紹幾個重要的概念：

  • STATE：狀態，實際是在陣列中的下標
  • CODE：狀態轉移值，實際為轉移字元的值
  • BASE：標識後繼節點的基地址陣列
  • CHECK：標識前驅節點的地址

從上面的概念的可以理解如下規則，假設一個輸入的字元為c，狀態從s轉移到t

  • state[t] = base[state[s]] + code[c]
  • check[state[t]] = state[s]

構建的過程大概也分為兩種：

  • 動態輸入詞語，動態構建雙陣列
  • 已知所有詞語，靜態構建雙陣列

我們以靜態構建過為核心，我們以《搜尋中常見的資料結構與演演算法探究（一）》案例二中提到的字謎單詞為例，共包含this、two、fat和that四個單詞為例，其中涉及都的字元集{a,f,h,i,o,s,t,w}共8個字元，為了後續描述方便，我們對這個八個字元進行編碼，分別是a-1,f-2,h-3,i-4,o-5,s-6,t-7,w-8

構建this，如下圖

構建two，如下圖

構建fat，如下圖

構建that，如下圖

Double-Array-TireTree查詢
驗證this是否在範圍內如下過程
1）state[t] = base[state[null]]+code[t]= 0 + 7=7
check[7]=state[null]=0通過
2）state[th] = base[state[t]]+code[h]=base[7]+3 =2+3=5
check[5]= state[t] = 7通過
3）state[tha] = base[state[th]]+ code[a]=base[5]+1=5+1=6
check[6]=state[th]=5通過
4）state[that] = base[state[tha]]+t = base[6]+7=11
check[11]=state[tha]=6通過

3.7.3 演演算法分析

通過兩個資料base和check將TireTree的資料壓縮到兩個陣列中，既保留了TireTree的搜尋的高效，又充分利用了儲存空間。

3.8 其他資料結構

鑑於篇幅有限，DFA，FSA以及FST將在下一篇文章中再來一起討論，敬請期待！

4 參考資料

參考書籍
《資料結構與演演算法分析：java語言描述》
《自動機理論、語言和計算導論》

本篇文章對本系列的上一篇文章的常見資料結構做了補充，介紹了非線性資料結構的最後一種，圖資料結構作為基本資料結構最複雜的一種，在多種企業級應用中都有使用，如網路拓撲，流程引擎，流程編排；另外本文重點介紹了幾種常見的匹配演演算法，以及演演算法的演進過程和使用場景，為下一篇的主題，也是本系列的重點探究的目標，「搜尋」做一個鋪墊，敬請期待！

作者： 潘坤 鄭冰 曹東傑