日期：2024年 08月 24日

標籤： Algorithm String Searching Algorithm C# Asp.NET Core

摘要：演算法-字串搜尋

第一部分：有限狀態機 - 介紹

Step 1：簡介

以下截取於Wiki

有限狀態機（英語：finite-state machine，縮寫：FSM）又稱有限狀態自動機（英語：finite-state automaton，縮寫：FSA），
簡稱狀態機，是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學計算模型。

簡言之，搜尋一串字串(文本)，先對查找字串建立每個字元建立 [狀態轉移表]，建立出每個字元的狀態查找後變化，直到找到最後一字元，視為完全匹配。
由於查詢是對每個字元做匹配，最小時間複雜度來到 O(n) ※ m：文本總長度
※來源：Wiki

Step 2：狀態轉移表 - 介紹

下面展示最常見的表示：當前狀態（B）和條件（Y）的組合指示出下一個狀態（C）。
完整的動作資訊可以只使用註腳來增加。包括完整動作資訊的FSM定義可以使用狀態表。

※來源：Wiki

↓ 條件 \ 狀態 →	狀態 A	狀態 B	狀態 C
條件 X	_	_	_
條件 Y	_	狀態 C	_
條件 Z	_	_	_

當前[狀態 B] 如果觸發[條件 Y] 就會進入[狀態 C]，其餘狀態下都會保持不動

Step 3：狀態轉移表 - 應用字串搜尋 - 簡單舉例

狀態轉移表在字串搜尋中，條件會轉為是符合、不符合狀態，以下是舉例
文本：AAAB
搜尋：AAB
AAB 的狀態轉移表會如以下：
其中()是索引的位置

↓ 條件 \ 狀態 →	字元A(1)	字元A(2)	字元B(3)
條件-符合	字元A(2)	字元B(3)	查詢結束-找到字串
條件-不符合	字元A(1)	字元A(1)	字元A(1)

但很顯然的，如果 【字元B(3) + 條件-不符合 也回到第 A(1)字元】肯定會搜尋失誤

Step 4：狀態轉移表 - 應用字串搜尋 - 擴展

如果以上個[文本]、[狀態轉移表]舉例，當搜尋到 AAAB 的 AA”A”B 時，會在重新回到 字元A(1)，查詢 AAA”B” 時就會匹配失誤。
還需實現部分匹配，不符合時要將可回朔的位置找出。
文本：AAAB
搜尋：AAB

↓ 條件 \ 狀態 →	字元A(1)	字元A(2)	字元B(3)
條件-符合	字元A(2)	字元B(3)	查詢結束-找到字串
條件-不符合	字元A(1)	字元A(1)	“產生不匹配狀態轉移表”

“產生不匹配狀態轉移表”，當跑到字元B(3)，會檢查目前匹配的[文本]對象：AA”A”B 與[搜尋]：AA 中是否存在狀態轉移
可視為查詢 AA 時有以下狀態，可以得出當 字元B(3)條件-不符合，且當前對象字元為 A 時，可以跳轉到字元 A(2) 狀態

↓ 條件 \ 狀態 →	字元A(1)	字元A(2)
條件-符合	字元A(2)	_
條件-不符合	字元A(1)	字元A(1)

最終可以得出以下[狀態轉移表]：

↓ 條件 \ 狀態 →	字元A(1)	字元A(2)	字元B(3)
條件-符合	字元A(2)	字元B(3)	查詢結束-找到字串
條件-不符合，且目前匹配文本字元非A	字元A(1)	字元A(1)	字元A(1)
條件-不符合，且目前匹配文本字元為A	字元A(1)	字元A(1)	字元A(2)

上述的狀態轉移表簡化很多，因為目前搜尋：AAB 只有 A、B兩種字元，用 ASCII 碼，實際上需要產生 256 匹配結果
以搜尋 AAB 來看，會產生 256 * 3 = 768 種組合

Step 5：優缺點

優點具有以下：

1. 效率不錯	：	在平均情況下，它的時間複雜度接近於 𝑂(𝑛)，線性時間
2. 簡單	：	搜尋過程與實現很簡單，只要持續對表比對，轉移自身狀態

缺點：

1. 預處理狀態轉移表開銷很高	：	此空間 O(m * Σ) 當搜尋的字串愈長愈耗空間 ※Σ是字符集的大小（例如，ASCII字符集的大小为256）
2. 字符集依赖	：	空間的變化依賴字符集
3. 不能重複使用	：	在每次搜尋不同的字串時，若字符集系統龐大(Unicode)，不可重複使用狀態轉移表(空間占用太大)
4. 搜尋字串不可太長	：	因為狀態轉移表的關係，只適合用於短字串的搜尋

第二部分：有限狀態機-演算法 - 陣列實現

Step 1：建構式 - 進入

進入點為建構式時觸發

public FiniteStateMachineOrigineArrayExample(string text, string pattern)
{
    Console.WriteLine();
    Console.WriteLine(" 1. 陣列 做狀態轉移表 ");
    Console.WriteLine($@"文本：{text}");
    Console.WriteLine($@"查找：{pattern}");
    var patternFound = this.FiniteStateMachineAlgoritSearch(text, pattern);
    if (patternFound)
    {
        Console.WriteLine("文本中[找到了]模式！");
    }
    else
    {
        Console.WriteLine("文本中[沒有找到]模式。");
    }
}

Step 2：主程式

主程式拆成 4 小部分，其中第 2 部分 InitialPatternPreProcess(pattern); 會進行預處理，建立狀態轉移表。

/// <summary>
/// 1. 執行演算法 - 搜尋字串
/// </summary>        
public bool FiniteStateMachineAlgoritSearch(string text, string pattern)
{
    // 2. 初始化狀態轉移表
    var transitionTable = this.InitialPatternPreProcess(pattern);

    // 4. 搜尋字串
    var currentState = 0;
    for (int index = 0; index < text.Length; index++)
    {
        currentState = transitionTable[currentState, text[index]];

        // 4-1. 找到匹配 - 當前狀態達到最終狀態（模式長度）
        if (currentState == pattern.Length)
        {
            return true;
        }
    }

    // 4-2. 沒找到 - 當前狀態未達到最終狀態
    return false;
}

Step 3：子函數 - 建立狀態轉移表

狀態轉移表會依照電腦字元編碼的數量而產生，範例使用 ASCII
3-2. 賦值狀態轉移資料會依照字串長度賦予每個狀態值

/// <summary>
/// 3. 建立 Array[] 的狀態移轉表
/// </summary>        
public int[,] InitialPatternPreProcess(string pattern)
{
    int statesCount = pattern.Length + 1;//狀態數量 = 模式長度 + 1
    int alphabetSize = 256; // 假設現在比對為 Ascii 碼

    // 3-1. 初始化狀態轉移表
    var transitionTable = new int[statesCount, alphabetSize];

    // 3-2. 賦值狀態轉移資料
    for (int state = 0; state < pattern.Length; state++)
    {
        // 3-3. 依照ASCII 碼，將字元對應到狀態
        for (char c = (char)0; c < alphabetSize; c++)
        {
            var getState = GetNextState(pattern, state, c);
            transitionTable[state, c] = getState;
        }                    
    }
    return transitionTable;
}

Step 4：子函數 - 建立狀態轉移表 - 匹配

以搜尋的字串 AAB 為例，會產生 256 * 3 共 768 個狀態轉移：

1. 完全匹配	：	每個字元對應下一個字元的狀態值
2. 部分匹配	：	若匹配失敗，最近的回朔位置

以搜尋字串 AAB
字元 “A”AB 有以下 256 個狀態：
遇到文本 A 時完全匹配進入下一狀態 1

\[\begin{array}{|c|c|c|c|c|c|} \hline ASCII碼 & ... & A & B & C & D & ... & \\ \hline 狀態 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}\]

字元 A”A”B 有以下 256 個狀態：
遇到文本 A 時完全匹配進入下一狀態 2

\[\begin{array}{|c|c|c|c|c|c|} \hline ASCII碼 & ... & A & B & C & D & ... & \\ \hline 狀態 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}\]

字元 AA”B” 有以下 256 個狀態：
遇到文本 B 時完全匹配進入下一狀態 3 ，若為文本 A 則退回 2

\[\begin{array}{|c|c|c|c|c|c|} \hline ASCII碼 & ... & A & B & C & D & ... & \\ \hline 狀態 & 0 & 2 & 3 & 0 & 0 & 0 & 0 \\ \hline \end{array}\]

/// <summary>
/// 3-3. 依照ASCII 碼，將字元對應到狀態
/// </summary>                        
private int GetNextState(string pattern, int state, char c)
{
    // 完全匹配 - 當前 pattern 字元與 ASCII 碼相同
    if (state < pattern.Length && c == pattern[state])
    {
        return state + 1;
    }

    // 部分匹配
    for (int ns = state; ns > 0; ns--)
    {
        // 找到最長的部分匹配
        if (pattern[ns - 1] == c)
        {
            // 檢查是否為部分匹配
            // pattern[0] 開始到 pattern[ns - 1] 為部分匹配
            for (int index = 0; index < ns - 1; index++)
            {
                if (pattern[index] != pattern[state - ns + 1 + index])
                {
                    return 0;
                }
            }
            return ns;                        
        }
    }
    return 0;
}

第三部分：有限狀態機-演算法 - 陣列圖解

Step 1：圖解

以下為舉例說明：

完整文本 ： AAAB

搜尋字串 ： AAB

字串索引 ： 012

第四部分：有限狀態機-演算法 - 哈希實現

Step 1：建構式 - 進入

為了降低空間複雜度，可以採用 Hash 的方式保存完全匹配的轉移狀態，
當觸發不符合條件時才進行上一狀態的匹配，可以有效的將空間複雜度最小到 O(M)
※m：找尋字串總長度
以下進入點為建構式時觸發

public FiniteStateMachineHashExample(string text, string pattern)
{
    Console.WriteLine();
    Console.WriteLine(" 2. Hash 做狀態轉移表 ");
    Console.WriteLine($@"文本：{text}");
    Console.WriteLine($@"查找：{pattern}");
    var patternFound = this.FiniteStateMachineAlgoritSearch(text, pattern);
    if (patternFound)
    {
        Console.WriteLine("文本中[找到了]模式！");
    }
    else
    {
        Console.WriteLine("文本中[沒有找到]模式。");
    }
}

Step 2：主程式

主程式拆成 5 小部分，其中第 2 部分 InitialPatternPreProcess(pattern); 會進行預處理，建立狀態轉移表(只處理完全匹配)。
4-1. 時，若未產生轉移狀態時，才進行部分匹配的查找

/// <summary>
/// 1. 執行演算法 - 搜尋字串
/// </summary>        
public bool FiniteStateMachineAlgoritSearch(string text, string pattern)
{
    // 2. 初始化狀態轉移表
    var transitionTable = this.InitialPatternPreProcess(pattern);
    // 4. 搜尋字串
    var currentState = 0;
    for (int index = 0; index < text.Length; index++)
    {
        char currentChar = text[index];
        // 4-1. 狀態轉移表中沒有對應的狀態，取得部分匹配狀態
        if (!transitionTable.ContainsKey((currentState, currentChar)))
        {
            int partialState = GetPartialState(pattern, currentState, currentChar);
            transitionTable[(currentState, currentChar)] = partialState;
        }
        currentState = transitionTable[(currentState, currentChar)];
        
        // 5-1. 找到匹配 - 當前狀態達到最終狀態（模式長度）
        if (currentState == pattern.Length)
        {
            return true;
        }
    }
    // 5-2. 沒找到 - 當前狀態未達到最終狀態
    return false;
}

Step 3：子函數 - 建立狀態轉移表

狀態轉移表會依照 pattren 的長度建立，因為只建立完全匹配

/// <summary>
/// 3. 建立 Hash 的狀態移轉表
/// </summary>        
public Dictionary<(int, int), int> InitialPatternPreProcess(string pattern)
{
    var transitionTable = new Dictionary<(int, int), int>();
    // 3-1. 為完全匹配的字符建立狀態轉移
    for (int state = 0; state < pattern.Length; state++)
    {
        transitionTable[(state, pattern[state])] = state + 1;
    }
    return transitionTable;
}

Step 4：子函數 - 未達到條件時 - 部分匹配

以搜尋的字串 AAB 為例，會產生 256 * 3 共 768 個狀態轉移：

完整文本 ： AAAB

搜尋字串 ： AAB

字串索引 ： 012

/// <summary>
/// 4-2. 取得部分匹配狀態
/// </summary>            
private int GetPartialState(string pattern, int state, char c)
{
    // 尋找匹配的最長前綴
    for (int ns = state; ns > 0; ns--)
    {
        if (pattern[ns - 1] == c && 
            pattern.Substring(0, ns - 1) == pattern.Substring(state - ns + 1, ns - 1))
        {
            return ns;
        }
    }
    return 0;
}

第五部分：有限狀態機-演算法 - 哈希圖解

Step 1：圖解

以下為舉例說明：

完整文本 ： AAAB

搜尋字串 ： AAB

字串索引 ： 012