探究字符串模式匹配的高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法

導(dǎo)讀

本文介紹了幾個(gè)常見(jiàn)的匹配算法，通過(guò)算法過(guò)程和算法分析介紹了各個(gè)算法的優(yōu)缺點(diǎn)和使用場(chǎng)景，并為后續(xù)的搜索文章做個(gè)鋪墊；讀者可以通過(guò)比較幾種算法的差異，進(jìn)一步了解匹配算法演進(jìn)過(guò)程以及解決問(wèn)題的場(chǎng)景；KMP算法和Double-Array TireTree是其中算法思想的集大成者，希望讀者重點(diǎn)關(guān)注。

01

前言

上文探究了數(shù)據(jù)結(jié)構(gòu)和算法的一些基礎(chǔ)和部分線性數(shù)據(jù)結(jié)構(gòu)和部分簡(jiǎn)單非線性數(shù)據(jù)結(jié)構(gòu)，本文我們來(lái)一起探究圖論，以及一些字符串模式匹配的高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法。《搜索中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)與算法探究（一）》

搜索作為企業(yè)級(jí)系統(tǒng)的重要組成部分，越來(lái)越發(fā)揮著重要的作用，ES已經(jīng)成為每個(gè)互聯(lián)網(wǎng)企業(yè)必備的工具集。而作為搜索的基礎(chǔ)部分，文本匹配的重要性不言而喻。文本匹配不僅為精確搜索提供了方法，而且為模糊匹配提供了算法依據(jù)。比如相似度算法，最大搜索長(zhǎng)度算法都是在匹配算法的基礎(chǔ)上進(jìn)行了變種和改良。

02 圖論基礎(chǔ)

2.1 圖的基本概念

一個(gè)圖G（V，E）由頂點(diǎn)的集V和邊的集E組成。每一條邊就是一副點(diǎn)對(duì)（v，w），其中v，w∈V。如果點(diǎn)對(duì)是有序的，那么圖就是有向圖。有時(shí)候還有第三種成分，稱作權(quán)。

以物流的抽象模型為例：每個(gè)配送中心是一個(gè)頂點(diǎn)，由兩個(gè)頂點(diǎn)表示的配送中心間如果存在一條干線運(yùn)輸線，那么這兩個(gè)頂點(diǎn)就用一條邊連接。邊可以由一個(gè)權(quán)，表示時(shí)間、距離和運(yùn)輸?shù)某杀??？梢匝杆俅_定任何兩個(gè)配送中心的最佳線路。這里的“最佳”可以是指最少邊數(shù)的路徑，也即經(jīng)過(guò)的配送中心最少；也可以是對(duì)一種或所有權(quán)總量度所算出的最佳者。

2.2 圖的表示方法

考慮實(shí)用情況，以有向圖為例：

假設(shè)可以以省會(huì)城市開(kāi)始對(duì)頂點(diǎn)編號(hào)。如下圖

圖1有向圖圖示

1.鄰接矩陣

表示圖的一種簡(jiǎn)單的方法是使用一個(gè)二維數(shù)據(jù)，稱為鄰接矩陣表示法。有一個(gè)二維數(shù)組A，對(duì)于每條邊（u，v），置A[u][v]等于true；否則數(shù)組元素就是false。

如果邊有一個(gè)權(quán)，那么可以置A[u][v]等于該權(quán)，而使用很大或者很小的權(quán)作為標(biāo)記表示不存在的邊。雖然這種表示方法的優(yōu)點(diǎn)是簡(jiǎn)單，但是，它的空間復(fù)雜度為θ（|V|^2）,如果圖的邊不是很多（稀疏的），那么這種表示的代價(jià)就太大了。代碼如下：

/**
 * 

 * Description: 使用鄰接矩陣的圖表示法
 * 

 * Company: 京東
 *
 * @author pankun8
 * @date 2021/11/11 15:41
 */
@Data
@NoArgsConstructor
public class Graph{
    /**
     * 圖的節(jié)點(diǎn)數(shù)
     */
privateintn;


    /**
     * 圖
     */
privateT[]data;


    /**
     * 是否是有向圖
     */
privateBooleandirected;


    /**
     * 鄰接矩陣
     */
    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 起點(diǎn)
     * @param w 終點(diǎn)
     * @param value 權(quán)重
     */
    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 ++;
        }
    }


    //判斷兩個(gè)節(jié)點(diǎn)中是否以及存在邊
    public int hasEdge(int v, int w){
        if((v >=0 && v < n) && (w >= 0 && w < n)){
            return matrix[v][w];
        }
        return 0;
    }
    /**
     * 狀態(tài)轉(zhuǎn)移函數(shù)
     * @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圖的搜索算法

從圖的某個(gè)訂單出發(fā)，訪問(wèn)途中的所有頂點(diǎn)，并且一個(gè)頂點(diǎn)只能被訪問(wèn)一次。圖的搜索（遍歷）算法常見(jiàn)的有兩種，如下：

深度優(yōu)先搜索算法（DFS）

廣度優(yōu)先搜索算法（BFS）

03

數(shù)據(jù)結(jié)構(gòu)與算法

3.1 BF（Brute Force）算法

3.1.1 算法介紹

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

3.1.2 算法過(guò)程

在講解算法之前，先定義兩個(gè)概念，方便后面講解。他們分別是主串（S）和模式串（P）。比如說(shuō)要在字符串A中查找字符串B，那么A就是主串，B就是模式串。把主串的長(zhǎng)度記作n，模式串的長(zhǎng)度記作m，并且n>m。算法過(guò)程如下圖：

圖2 BF算法過(guò)程圖示

3.1.3 算法分析

BF算法過(guò)程很“暴力”，當(dāng)然也就比較簡(jiǎn)單，好懂，但是響應(yīng)的性能也不高極端情況下時(shí)間復(fù)雜度函數(shù)為O(m*n)。

盡管理論上BF算法的時(shí)間復(fù)雜度很高，但在實(shí)際的開(kāi)發(fā)中，它卻是一個(gè)比較常用的字符串匹配算法，主要原因有以下兩點(diǎn)：

樸素字符串匹配算法思想簡(jiǎn)單，代碼實(shí)現(xiàn)也非常簡(jiǎn)單，不容易出錯(cuò)，容易調(diào)試和修改。

在實(shí)際的軟件開(kāi)發(fā)中，模式串和主串的長(zhǎng)度都不會(huì)太長(zhǎng)，大部分情況下，算法執(zhí)行的效率都不會(huì)太低。

3.2 RK（Rabin-Karp）算法

3.2.1算法介紹

RK算法全程叫Rabin-Karp算法，是有它的兩位發(fā)明者Rabin和Karp的名字來(lái)命名，這個(gè)算法理解并不難，它其實(shí)是BF算法的升級(jí)版。

3.2.2 算法過(guò)程

圖3 RK算法過(guò)程圖示

3.2.3算法分析

在BF算法中當(dāng)字符串不匹配時(shí)，需要比對(duì)每一個(gè)字符，如果不能匹配則重新調(diào)整I，J的值重新比對(duì)每一個(gè)字符，RK的思路是將模式串進(jìn)行哈希算法得到s=hash(P)，然后將主串分割成n-m+1個(gè)子串，分別對(duì)其進(jìn)行hash算法，然后逐個(gè)和s進(jìn)行比對(duì)，減少逐個(gè)字符串比對(duì)的次數(shù)。其中hash函數(shù)的具體實(shí)現(xiàn)可自行選擇。

整個(gè)RK算法包含兩部分：

計(jì)算模式串哈希和子串的哈希；

模式串哈希和子串哈希的比較；

第一部分的只需要掃描一遍主串就能計(jì)算出所有子串的哈希值，這部分的時(shí)間復(fù)雜度是O(n)。模式串哈希值與每個(gè)子串哈希之間的比較的時(shí)間復(fù)雜度是O(1)，總共需要比對(duì)n-m+1次，所以這部分的時(shí)間復(fù)雜度為O(n)。所以RK算法的整體時(shí)間復(fù)雜度為O(n)。

3.3KMP算法

3.3.1算法介紹

KMP算法是一種線性時(shí)間復(fù)雜度的字符串匹配算法，它是對(duì)BF(Brute-Force)算法的改進(jìn)。KMP算法是由D.E.Knuth與V.R.Partt和J.H.Morris一起發(fā)現(xiàn)的，因此人們稱它為Knuth-Morris-Pratt算法，簡(jiǎn)稱KMP算法。

前面介紹了BF算法，缺點(diǎn)就是時(shí)間消耗很大，KMP算法的主要思想就是：在匹配過(guò)程中發(fā)生匹配失敗時(shí)，并不是簡(jiǎn)單的將模式串P的下標(biāo)J重新置為0，而是根據(jù)一些匹配過(guò)程中得到的信息跳過(guò)不必要的匹配，從而達(dá)到一個(gè)較高的匹配效率。

3.3.2算法過(guò)程

在介紹KMP算法之前，首先介紹幾個(gè)字符串的概念：

前綴：不包含最后一個(gè)字符的所有以第一個(gè)字符開(kāi)頭的連續(xù)子串；

后綴：不包含第一個(gè)字符的所有以最后一個(gè)字符結(jié)尾的連續(xù)子串；

最大公共前后綴：前綴集合與后綴集合中長(zhǎng)度最大的子串；

例如字符串a(chǎn)bcabc

前綴集合是a，ab，abc，abca，abcab

后綴集合為bcabc，cabc，abc，bc，c

最大公共前后綴為abc

KMP算法的過(guò)程如下圖：

圖4 KMP算法過(guò)程圖示

那么為什么KMP算法會(huì)知道在匹配失敗時(shí)下標(biāo)J回溯到那個(gè)位置呢？其實(shí)KMP算法在匹配的過(guò)程中將維護(hù)一些信息來(lái)幫助跳過(guò)不必要的匹配，這個(gè)信息就是KMP算法的重點(diǎn)，next數(shù)組也叫做fail數(shù)據(jù)或者前綴數(shù)據(jù)。下面來(lái)分析next數(shù)組的由來(lái)：

對(duì)于模式串P的每個(gè)元素P[j]，都存在一個(gè)實(shí)數(shù)k，使得模式串P開(kāi)頭的k個(gè)字符(P[0]P[1]...P[k-1])依次于P[j]前面的k(P[j-k]P[j-k+1]...P[j-1])個(gè)字符相同。如果這樣的k有多個(gè)，則取最大的一個(gè)。模式串P中的每個(gè)位置j的字符都存在這樣的信息，采用next數(shù)組表示，即next[j]=MAX{k}。

從上述定義中可看到next(j)的邏輯意義就是求P[0]P[1]...P[j-1]的最大公共前后綴長(zhǎng)度。代碼如下：

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];//此處為理解難點(diǎn)
    }
  }
}

下面分析next的求解過(guò)程：

1. 特殊情況

當(dāng)j的值為0或者1的時(shí)候，它們的k值都為0，即next(0) = 0 、next(1)= 0。為了后面k值計(jì)算的方便，我們將next(0)的值設(shè)置為-1。

2. 當(dāng)P[j]==P[k]的情況

當(dāng)P[j]==P[k]時(shí)，必然有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. 當(dāng)P[j]!=P[k]的情況

當(dāng)P[j]!=P[k]時(shí)，必然會(huì)有next(j)=k，并且next(j+1)

4. 算法優(yōu)化

上述算法有一個(gè)小問(wèn)題就是當(dāng)P[k]匹配失敗后會(huì)跳轉(zhuǎn)到next(k)繼續(xù)進(jìn)行匹配，但是此時(shí)有可能P[k]=P[next(k)]，此時(shí)匹配肯定是失敗的所以對(duì)上述代碼進(jìn)行改進(jìn)如下：

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];//如果兩個(gè)相等
      }else{
        next[j] = k;
      }
    }else{
      k = next[k];
    }
  }
}

3.3.3算法分析

KMP算法通過(guò)消除主串指針的回溯提高匹配的效率，整個(gè)算法分為兩部分，next數(shù)據(jù)的求解，以及字符串匹配，從上一節(jié)的分析可知求解next數(shù)組的時(shí)間復(fù)雜度為O(m)，匹配算法的時(shí)間復(fù)雜度為O(n)，整體的時(shí)間復(fù)雜度為O(m+n)。KMP算法不是最快匹配算法，卻是名氣最大的，使用的范圍也非常廣。

3.4BM算法

3.4.1算法介紹

Boyer-Moore字符串搜索算法是一種非常高效的字符串搜索算法。它由BobBoyer和J Strother Moore發(fā)明，有實(shí)驗(yàn)統(tǒng)計(jì)它的性能是KMP算法的3-4倍。

3.4.2算法過(guò)程

前面介紹的BF，KMP的算法的匹配過(guò)程雖然模式串的回溯過(guò)程不同，但是相同點(diǎn)都是從左往右逐個(gè)字符進(jìn)行匹配，而B(niǎo)M算法則是采用的從右向左進(jìn)行匹配，借助壞字符規(guī)則（SKip(j)）和好后綴規(guī)則（Shift(j)），能夠進(jìn)行快速匹配。其中壞字符和好后綴示意如下圖

圖5壞字符和好后綴圖示

1. 壞字符規(guī)則：在BM算法從右向左掃描的過(guò)程中，若發(fā)現(xiàn)某個(gè)字符S[i]不匹配時(shí)，則按照如下兩種情況進(jìn)行處理：

如果字符S[i]在模式串P中沒(méi)有出現(xiàn)，那么從字符S[i]開(kāi)始的m個(gè)文本顯然是不可能和P匹配成功，直接全部跳過(guò)該區(qū)域。

如果字符S[i]在模式串P中出現(xiàn)，則以該字符進(jìn)行對(duì)齊。

2. 好后綴規(guī)則：在BM算法中，若發(fā)現(xiàn)某個(gè)字符不匹配的同時(shí)，已有部分字符匹配成功，則按照如下兩種情況進(jìn)行處理：

如果已經(jīng)匹配的子串在模式串P中出現(xiàn)過(guò)，且子串的前一個(gè)字符和P[j]不相同，則將模式串移動(dòng)到首次出現(xiàn)子串的前一個(gè)位置。

如果已經(jīng)匹配的子串在模式串P中沒(méi)有出現(xiàn)過(guò)，則找到已經(jīng)匹配的子串最大前綴，并移動(dòng)模式串P到最大前綴的前一個(gè)字符。

BM算法過(guò)程如下：

圖6BM算法過(guò)程圖示

3.4.3算法分析

在BM算法中，如果匹配失敗則取SKip(j)與Shift(j)中的較大者作為跳躍的距離。BM算法預(yù)處理階段的復(fù)雜度為O(m+n)，搜索階段的最好的時(shí)間復(fù)雜度為O(n/m)，最壞的時(shí)間復(fù)雜度為O(n*m)。由于BM算法采用的是后綴匹配算法，并且通過(guò)壞字符和好后綴共同作用下，可以跳過(guò)不必要的一些字符，具體Shift(j)的求解過(guò)程可參看KMP算法的next()函數(shù)過(guò)程。

3.5TireTree

3.5.1算法介紹

在搜索中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)與算法探究（一）中，介紹過(guò)一種樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)叫做HashTree，本章介紹的TireTree就是HashTree的一個(gè)變種。TireTree又叫做字典樹(shù)或者前綴樹(shù)，典型的應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串，所以經(jīng)常被搜索系統(tǒng)用于文本的統(tǒng)計(jì)或搜索。

TireTree的核心思想是空間換時(shí)間。TrieTree是一種高效的索引方法，它實(shí)際上是一種確定有限自動(dòng)機(jī)(DFA)，利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高查詢效率的目的，非常適合多模式匹配。TireTree有以下基本性質(zhì)：

根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都包含一個(gè)字符。

從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的所有子節(jié)點(diǎn)包含的字符都不相同。

3.5.2算法過(guò)程

TireTree構(gòu)建與查詢

我們以《搜索中常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)與算法探究（一）》案例二中提到的字謎單詞為例，共包含this、two、fat和that四個(gè)單詞，我們來(lái)探究一下TireTree的構(gòu)建過(guò)程如下圖：

圖7 TireTree算法過(guò)程圖示

上述過(guò)程描述了that，two，fat，that四個(gè)單詞的插入TireTree的過(guò)程，其中黃色的節(jié)點(diǎn)代表有單詞存在。由于TireTree的構(gòu)建的過(guò)程是樹(shù)的遍歷，所以查詢過(guò)程和創(chuàng)建過(guò)程可以視為一個(gè)過(guò)程。

3.5.3算法分析

TireTree由于本身的特性非常適合前綴查找和普通查找，并且查詢的時(shí)間復(fù)雜度為O(log(n))，和hash比較在一些場(chǎng)景下性能要優(yōu)于甚至取代hash，例如說(shuō)前綴查詢（hash不支持前綴查詢）。

雖然TireTree的查詢速度會(huì)有一定的提升但是卻不支持后綴查詢，并且TireTree對(duì)空間利用率不高，且對(duì)中文的支持有限。

3.6 AC自動(dòng)機(jī)

3.6.1算法介紹

AC自動(dòng)機(jī)（Aho-Corasick automation）該算法在1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，是著名的多模匹配算法之一。要搞懂AC自動(dòng)機(jī)，先得有TireTree和KMP模式匹配算法的基礎(chǔ)知識(shí)，上述章節(jié)有TireTree和KMP算法的詳細(xì)介紹。

3.6.2算法過(guò)程

AC自動(dòng)機(jī)的構(gòu)建過(guò)程需要如下步驟：

1. TireTree的構(gòu)建，請(qǐng)參看TireTree章節(jié)

2. fail指針的構(gòu)建

使當(dāng)前字符失配時(shí)跳轉(zhuǎn)到具有最長(zhǎng)公共前后綴的字符繼續(xù)匹配。如同 KMP算法一樣， AC自動(dòng)機(jī)在匹配時(shí)如果當(dāng)前字符匹配失敗，那么利用fail指針進(jìn)行跳轉(zhuǎn)。由此可知如果跳轉(zhuǎn)，跳轉(zhuǎn)后的串的前綴，必為跳轉(zhuǎn)前的模式串的后綴并且跳轉(zhuǎn)的新位置的深度一定小于跳之前的節(jié)點(diǎn)。fail指針的求解過(guò)程可是完全參照KMP算法的next指針求解過(guò)程，此處不再贅述。

3. AC自動(dòng)機(jī)查找

查找過(guò)程和TireTree相同，只是在查找失敗的時(shí)候感覺(jué)fail指針跳轉(zhuǎn)到指定的位置繼續(xù)進(jìn)行匹配。

3.6.3算法分析

AC自動(dòng)機(jī)利用fail指針阻止了模式串匹配階段的回溯，將時(shí)間復(fù)雜度優(yōu)化到了O(n)。

3.7Double-Array-TireTree

3.7.1算法介紹

前面提到過(guò)TireTree雖然很完美，但是空間利用率很低，雖然可以通過(guò)動(dòng)態(tài)分配數(shù)組來(lái)解決這個(gè)問(wèn)題。為了解決這個(gè)問(wèn)題引入Double-Array-TireTree，顧名思義Double-Array-TireTree就是TireTree壓縮到兩個(gè)一維數(shù)組BASE和CHECK來(lái)表示整個(gè)樹(shù)。Double-Array-TireTree擁有TireTree的所有優(yōu)點(diǎn)，而且克服了TireTree浪費(fèi)空間的不足，使其應(yīng)用范圍更加廣泛，例如詞法分析器，圖書搜索，拼寫檢查，常用單詞過(guò)濾器，自然語(yǔ)言處理中的字典構(gòu)建等等。

3.7.2算法過(guò)程

在介紹算法之前，提前簡(jiǎn)單介紹一個(gè)概念DFA（下一篇詳細(xì)介紹）。DFA（DeterministicFinite State）有限自動(dòng)機(jī)，通俗來(lái)講DFA是指給定一個(gè)狀態(tài)和一個(gè)輸入變量，它能轉(zhuǎn)到的下一個(gè)狀態(tài)也就確定下來(lái)，同時(shí)狀態(tài)是有限的。

Double-Array-TireTree構(gòu)建

Double-Array-TireTree終究是一個(gè)樹(shù)結(jié)構(gòu)，樹(shù)結(jié)構(gòu)的兩個(gè)重要的要素便是前驅(qū)和后繼，把樹(shù)壓縮在雙數(shù)組中，只需要保持能查到每個(gè)節(jié)點(diǎn)的前驅(qū)和后繼。首先要介紹幾個(gè)重要的概念：

STATE：狀態(tài)，實(shí)際是在數(shù)組中的下標(biāo)

CODE：狀態(tài)轉(zhuǎn)移值，實(shí)際為轉(zhuǎn)移字符的值

BASE：標(biāo)識(shí)后繼節(jié)點(diǎn)的基地址數(shù)組

CHECK：標(biāo)識(shí)前驅(qū)節(jié)點(diǎn)的地址

從上面的概念的可以理解如下規(guī)則，假設(shè)一個(gè)輸入的字符為c，狀態(tài)從s轉(zhuǎn)移到t

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

check[state[t]] = state[s]

構(gòu)建的過(guò)程大概也分為兩種：

動(dòng)態(tài)輸入詞語(yǔ)，動(dòng)態(tài)構(gòu)建雙數(shù)組

已知所有詞語(yǔ)，靜態(tài)構(gòu)建雙數(shù)組

以靜態(tài)構(gòu)建過(guò)為核心，以《搜索中常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)與算法探究（一）》案例二中提到的字謎單詞為例，共包含this、two、fat和that四個(gè)單詞為例，其中涉及到的字符集{a,f,h,i,o,s,t,w}共8個(gè)字符，為了后續(xù)描述方便，對(duì)這個(gè)八個(gè)字符進(jìn)行編碼，分別是a-1,f-2,h-3,i-4,o-5,s-6,t-7,w-8

構(gòu)建this，如下圖

圖8 構(gòu)建This圖示

構(gòu)建two，如下圖

圖9構(gòu)建two圖示

構(gòu)建fat，如下圖

圖10構(gòu)建fat圖示

構(gòu)建that，如下圖

圖11 構(gòu)建that圖示

Double-Array-TireTree查詢

驗(yàn)證this是否在范圍內(nèi)如下過(guò)程

1. state[t]= base[state[null]]+code[t]= 0 + 7=7

check[7]=state[null]=0 通過(guò)

2. state[th]= base[state[t]]+code[h]=base[7]+3 =2+3=5

check[5]= state[t] = 7 通過(guò)

3. state[tha]= base[state[th]]+ code[a]=base[5]+1=5+1=6

check[6]=state[th]=5 通過(guò)

4. state[that]= base[state[tha]]+t = base[6]+7=11

check[11]=state[tha]=6 通過(guò)

3.7.3算法分析

通過(guò)兩個(gè)數(shù)據(jù)base和check將TireTree的數(shù)據(jù)壓縮到兩個(gè)數(shù)組中，既保留了TireTree的搜索的高效，又充分利用了存儲(chǔ)空間。

3.8其他數(shù)據(jù)結(jié)構(gòu)

鑒于篇幅有限，DFA，F(xiàn)SA以及FST將在下一篇文章中再來(lái)一起討論，敬請(qǐng)期待！

04

總結(jié)

本篇文章對(duì)本系列的上一篇文章的常見(jiàn)數(shù)據(jù)結(jié)構(gòu)做了補(bǔ)充，介紹了非線性數(shù)據(jù)結(jié)構(gòu)的最后一種，圖數(shù)據(jù)結(jié)構(gòu)作為基本數(shù)據(jù)結(jié)構(gòu)最復(fù)雜的一種，在多種企業(yè)級(jí)應(yīng)用中都有使用，如網(wǎng)絡(luò)拓?fù)?，流程引擎，流程編排；另外本文重點(diǎn)介紹了幾種常見(jiàn)的匹配算法，以及算法的演進(jìn)過(guò)程和使用場(chǎng)景，為下一篇的主題，也是本系列的重點(diǎn)探究的目標(biāo)，“搜索”做一個(gè)鋪墊，敬請(qǐng)期待！

審核編輯：劉清