文字差異偵測演算法能識別兩個文字版本之間的變更，並為版本控制系統、程式碼審查工具和文件比較應用程式奠定基礎。存在多種演算法方法，它們具有不同的效能特性和輸出格式，各自適用於特定的使用案例。理解這些演算法對於建立有效的文字比較工具至關重要，這些工具可為使用者提供有意義的差異視覺化。 最長共同子序列 (LCS) 演算法用於識別兩個文本中以相同順序出現但不必連續的最長字元序列。LCS 構成了生產系統中許多差異 (diff) 實作的基礎。LCS 長度表示兩個文本的相似程度，提供了一個相似性度量，從完全不同的文本的零到相同文本的完整長度。 動態規劃透過系統地建構表格，實現了高效的最長共同子序列 (LCS) 計算。 會建構一個矩陣，其中每個單元格 `[i,j]` 代表文字 1 的前 `i` 個字元與文字 2 的前 `j` 個字元的最長共同子序列長度。 這些單元格會使用遞迴關係來填充，這些關係會比較字元並建立在先前計算的值之上。 這種方法保證了最佳解，但需要 O(mn) 的時間和空間複雜度，其中 `m` 和 `n` 分別是文字的長度。 編輯距離，又稱萊文斯坦距離（Levenshtein distance），衡量的是將一個文本轉換為另一個文本所需的單字元編輯操作的最小次數。 編輯操作包括插入、刪除和替換，通常每次操作計為一步。 編輯距離提供了一種文本相似度的度量標準，這對於拼寫檢查、模糊匹配和近似字串搜尋應用非常有用。 動態規劃透過系統化的表格建構，以類似於最長共同子序列（LCS）的方式計算編輯距離。 每個儲存格 `[i,j]` 代表著第一個文本的前 `i` 個字元與第二個文本的前 `j` 個字元之間的編輯距離。 遞迴關係式會考量插入、刪除和替換操作，並在每個步驟中選擇成本最低的操作。 這種方法確保了任何文本對都能計算出最佳的編輯距離。 Hunt-McIlroy 演算法透過在計算差異之前識別匹配區塊，從而改進了大型文本的效能。匹配區塊是指兩個文本中以相同順序出現的相同行序列。然後，該演算法會遞迴地計算非匹配區域的差異，從而顯著降低了典型文本檔案（包含許多匹配行）的計算複雜度。 這個演算法是解決最長公共子序列（LCS）問題的方法之一。 它在 1970 年代初期由 James W. Hunt 和 M. Douglas McIlroy 在貝爾實驗室開發，並被用於原始的 Unix `diff` 工具中。 該演算法首先為兩個文本中的每一行創建唯一的雜湊值，以實現快速查找。 接著，它會找出兩個版本中以相同順序出現的最長匹配行序列。 最後，它利用這些資訊來顯示差異。 Hunt-McIlroy 演算法的時間複雜度為 O(N log N)，其中 N 是匹配行的數量。 雖然在某些情況下，它的最壞情況時間複雜度可能達到 O(n^2 log n)，但在實際應用中通常表現為 O(n log n)。 這種演算法的變體至今仍被用於增量版本控制系統、維基引擎和分子系統發育研究軟體中。 Myers 演算法透過不同的方法，為具有許多匹配行的文本提供了高效的差異計算。 該演算法透過在編輯距離矩陣中使用對角線方法，找到將一個文本轉換為另一個文本的最短編輯腳本。 對於典型的文本文件，Myers 演算法比簡單的 LCS 更有效率，特別是當差異相對於文件大小較小時。 Patience diff 演算法首先透過比對獨特的行來識別差異，然後遞迴處理剩餘的行。 這種方法通常比其他演算法產生更直觀的差異，特別是對於程式碼檔案，其中獨特的識別碼和函數名稱有助於錨定比對過程。 Git 和其他現代版本控制系統都使用 Patience diff 來改善差異品質。 三方合併演算法會偵測基準版本與兩個修改版本之間的差異，從而能夠合併來自多個分支的變更。 版本控制系統使用三方合併來自動解決非衝突的變更。 當兩個分支修改相同行時，就會發生衝突，需要開發人員手動解決。 字元級和詞彙級的差異檢測提供了不同粒度的差異偵測，以支援不同的使用情境。行級差異檢測能識別變更的行，適用於程式碼審查。詞彙級差異檢測能識別行內變更的詞彙，適用於文件比較。字元級差異檢測能識別詞彙內變更的字元，適用於精確的變更追蹤。 上下文行透過顯示變更周圍未變更的行，提高了差異輸出的可讀性。統一差異格式包含可配置的上下文行，通常是變更前後各三行，以幫助開發人員理解修改的上下文。上下文行使差異更具可讀性，但會增加輸出大小。 空白字元處理會顯著影響程式碼檔案中的差異結果。有些差異演算法會忽略空白字元變更，而有些則將空白字元視為重要。不同的應用程式對空白字元處理有不同的要求，其中程式碼審查工具通常提供「考量空白字元」和「忽略空白字元」的差異選項。 效能考量包括不同演算法的時間和空間複雜度。LCS（最長共同子序列）演算法的時間複雜度為 O(mn)，其中 m 和 n 是文本長度。 像 Myers 這樣的高效演算法可以降低變化較少文本的複雜度，使其適用於大型檔案。 演算法的選擇取決於檔案大小和預期的差異模式。 時間複雜度衡量演算法完成所需的時間，是輸入大小的函數。 空間複雜度則衡量演算法執行所需的記憶體量，也是輸入大小的函數。 LCS 的蠻力法時間複雜度為 O(n * 2^n)，因為它涉及生成兩個字串的所有可能子序列並檢查它們的共同性，這會隨著字串長度呈指數級增長。 相比之下，動態規劃方法將時間複雜度顯著提高到 O(mn)。 Myers 演算法是一種高效的方法，用於計算兩個序列之間的最短編輯腳本，通常是文本行。 它的時間複雜度通常為 O(ND)，其中 N 是輸入長度的總和，D 是最小編輯腳本的大小。 這使得它在變化較小時速度很快，因此適用於大型檔案。 Myers 演算法是 Git 和大多數版本控制系統中的預設演算法。 穩健的差異演算法之技術實作，需要根據效能要求、輸出格式偏好以及特定使用案例（例如程式碼審查或文件比較）來仔細選擇演算法。 不同的演算法在準確性、效能和輸出品質之間提供了不同的權衡。 例如，Git 預設使用 Myers 演算法，它著重於找出最短的編輯腳本（即最少數量的插入和刪除），但對於人類可讀性而言，Patience 或 Histogram 演算法可能產生更清晰的輸出。 Myers 演算法透過將問題建模為圖形搜尋來實現這一點，目標是從一個序列轉換為另一個序列所需的最小編輯次數。 差異演算法的選擇會影響輸出是易讀還是令人困惑，例如，移動的函式看起來是完全重寫還是清晰的重新定位。 對於程式碼審查，Histogram 演算法通常會產生更清晰的輸出，而 Myers 演算法則適用於機器生成的補丁和自動化處理。 許多程式碼審查工具允許您針對每個檔案或每個差異切換演算法，因為沒有一個「正確」的答案，只有在特定情境下更好或更差的答案。 差異演算法的品質和精確度衡量標準是捕捉到的差異數量越少越好，前提是差異沒有未被檢測到。 錯誤地報告過多的差異（誤報）雖然不如未能檢測到差異（漏報）那麼糟糕，但也會降低精確度。