開發者工具·文字比較

文字差異如何尋找更改的行：LCS 和 Myers 演演算法

2026年8月12日 · 工作原理

文字差異演演算法開發人員工作流程

解釋了基於行的比較背後的最長公共子序列的想法，以及為什麼邁爾斯演演算法使其足夠快，即使在瀏覽器分頁內也能立即執行。

兩個檔案，一個問題：哪些行存活下來？ — 幀比較是尋找兩個版本共有的最長行，而不是匹配行號

兩個修訂版未附有說明哪些行倖存的標籤。 ToolAcre 首先將每個文字分割成一個有序列表，然後搜尋以相同順序出現在兩個列表中的長子序列。共享脊椎之外的線條成為添加或刪除，而不是猜測的修改。

結果攜帶雙方原始的基於 1 的位置。未更改的行在每一側都有一個數字，僅在左側刪除，僅在右側添加。即使重複的台詞給出了不止一個合理的對齊方式，這種計算也使得所顯示的故事可以審查。

此實作將完整的行視為其比較單元。因此，換行邊界決定了結果：儲存在一行中的段落內的單字編輯會替換整行，而逐句排列的相同散文可以隔離更小的區域。

行比較不是隱藏在不同顯示後面的字元分析。 `splitLines` 建立數組，LCS 表將一個行鍵與另一個行鍵進行比較。這種可預測的粒度適合來源檔案和配置檔案，但它無法突出顯示在匹配的替換中更改的確切字母。

想像左邊的行 A、B、C、D、E 和右邊的行 A、C、E。 A、C 和 E 形成一個有序的公共子序列。 B 和 D 不在其中，因此結果會報告兩個刪除行和三個未更改的行，而無需將刪除的行與替換行配對。

此表記錄了每個剩餘位置對的可用最佳共享長度。重建工作是透過這些價值觀向前推進的。相同的按鍵使雙方都前進；否則，較大的相鄰值決定是否發出左移除或右添加。

工作簿名為 Myers，但 `diff.js` 明確實現普通最長公共子序列動態規劃。它的註釋指出了不同中間的 O(n·m) 時間和記憶體。聲稱 Myers 或最短編輯圖行為將用熟悉的演演算法取代實際發布的程式碼。

ToolAcre 在分配之前限制該成本。相同的前綴和後綴在線性通道中被剝離，並不同的中間最多可以包含 2,000 行。此矩陣是 `Uint32Array`；記錄的最差允許平方大約佔用 16 兆位元組，而不是無界的盒裝值。

將包含「新增的搜尋」、「修復的匯出」和「更新的幫助」的變更日誌與保留第一個和第三個條目但在最後一個條目之前插入「新增的篩選器」的修訂進行比較。公共條目錨定路徑，刪除“固定匯出”，並新增“新增的篩選器”。

此演演算法不會將此對稱為修改行。它的行詞彙只是相等、添加和刪除，因此文字替換顯示為一項刪除後一項添加。摘要單獨對這些操作進行計數，並僅當兩個計數均為零時才將文字標記為相同。

重複或可互換的行可以產生幾個相同長度的公共子序列。 ToolAcre 透過在兩個相鄰表值相等時優先刪除來解決平局問題。另一個正確的實作可以首先選擇添加，並以相同的編輯成本呈現不同外觀的對齊。

這就是為什麼空行或右大括號可能會附加到工具中的不同區塊上。這種差異並不自動意味著比較丟失了內容。在將表示差異視為相互競爭的事實主張之前，請先閱讀原始行號和周圍未更改的行。

此路徑中的任何內容都不會解析語法樹、識別重新命名的識別碼、標記移動的區塊或理解散文的含義。移動的段落違反了共享順序要求，並可能會以刪除的形式出現一次，也可能以添加的形式出現一次。該工具也不計算行內的字元或單字級突出顯示。

這些遺漏是邊界，而不是隱藏模式。使用語言感知審閱者進行語義宣告和合併歷史記錄的版本控制。文字差異回答了兩個有序行序列如何不同的狹義問題，然後讓人們解釋這些文字編輯是否重要。

將綠色和紅色行視為 LCS 派生的解釋，而不是作為作者意圖的證明。前綴和後綴修剪會改變工作量，但不會改變最終的行計數。即使大小寫或空格選項提供了更寬鬆的匹配鍵，原始文字仍保留在每一行中。

比較透過匯入的瀏覽器模組執行並使用 DOM 文字節點進行渲染；刀具路徑中沒有轉換終點。嘗試一個五行範例，交換兩邊，然後下載補丁形狀的輸出，看看方向如何在不發明語義的情況下將添加更改為刪除。