.jpg)
diff算法的核心思想是找出兩個(gè)序列的最長(zhǎng)公共子序列（lcs），從而確定最小編輯操作。1.讀取文件內(nèi)容，按行分割構(gòu)建二維數(shù)組；2.使用動(dòng)態(tài)規(guī)劃計(jì)算lcs；3.回溯路徑找出差異位置；4.輸出或標(biāo)記差異。實(shí)現(xiàn)時(shí)需注意效率、內(nèi)存占用和行匹配精度等問題。
在處理文本文件比較時(shí)，比如版本控制系統(tǒng)、文檔差異分析等場(chǎng)景，我們經(jīng)常需要用到類似 diff 的算法來找出兩個(gè)文件之間的差異。c++作為一門性能較強(qiáng)的編程語言，非常適合實(shí)現(xiàn)這類底層邏輯。那么，怎么用C++實(shí)現(xiàn)一個(gè)基本的文件差異比較呢？核心在于理解并應(yīng)用 diff 算法的基本思路。
什么是diff算法的核心思想？
diff 算法的目標(biāo)是找出兩個(gè)序列之間的最小編輯操作（插入、刪除、修改），使得其中一個(gè)可以轉(zhuǎn)換成另一個(gè)。最常見的實(shí)現(xiàn)方式是基于最長(zhǎng)公共子序列（LCS）問題的動(dòng)態(tài)規(guī)劃解法。
舉個(gè)例子：
有兩個(gè)字符串 A = “abcde”，B = “acefg”。它們的最長(zhǎng)公共子序列是 “ace”。通過找出這個(gè)子序列的位置，就可以確定哪些部分是新增的，哪些是被刪除的。
在文件比較中，我們可以將每一行為一個(gè)元素，構(gòu)建兩個(gè)行數(shù)組，然后對(duì)這兩個(gè)數(shù)組進(jìn)行 LCS 比較，從而得到差異信息。
立即學(xué)習(xí)“C++免費(fèi)學(xué)習(xí)筆記（深入）”；
如何用C++實(shí)現(xiàn)diff功能？
要實(shí)現(xiàn)一個(gè)基礎(chǔ)的 diff 功能，可以按以下步驟來做：
- 讀取文件內(nèi)容，按行分割
- 構(gòu)建二維數(shù)組用于動(dòng)態(tài)規(guī)劃計(jì)算LCS
- 回溯路徑找出差異位置
- 輸出或標(biāo)記出不同之處
下面是一個(gè)簡(jiǎn)化的實(shí)現(xiàn)思路：
#include <iostream> #include <fstream> #include <vector> #include <string> using namespace std; // 讀取文件到行列表 vector<string> readLines(const string& filename) { ifstream file(filename); vector<string> lines; string line; while (getline(file, line)) { lines.push_back(line); } return lines; } // 構(gòu)建LCS的DP表 vector<vector<int>> buildLcsTable(const vector<string>& a, const vector<string>& b) { int m = a.size(), n = b.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp; } // 回溯找出差異 void findDiff(const vector<string>& a, const vector<string>& b, const vector<vector<int>>& dp) { int i = a.size(), j = b.size(); while (i > 0 || j > 0) { if (i > 0 && j > 0 && a[i - 1] == b[j - 1]) { cout << " " << a[i - 1] << endl; // 相同行 --i; --j; } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) { cout << "+ " << b[j - 1] << endl; // 新增行 --j; } else { cout << "- " << a[i - 1] << endl; // 刪除行 --i; } } }
當(dāng)然，這只是一個(gè)簡(jiǎn)化版本。實(shí)際項(xiàng)目中還需要考慮：
- 行內(nèi)容空格/大小寫是否敏感
- 大文件處理（分塊加載、內(nèi)存優(yōu)化）
- 性能優(yōu)化（如使用 Myers 差異算法）
實(shí)際使用中需要注意的問題
- 效率問題：標(biāo)準(zhǔn)的 LCS 動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度是 O(n*m)，對(duì)于大文件來說可能不夠高效。這時(shí)候可以考慮更高效的算法，比如 Myers’差分算法，它能在 O(ND) 時(shí)間內(nèi)找到差異。
- 內(nèi)存占用：如果文件非常大，一次性讀入所有行可能導(dǎo)致內(nèi)存不足。建議按需讀取或使用流式處理。
- 行匹配精度：有時(shí)候兩行內(nèi)容略有不同但語義相同（比如空格不同），這時(shí)候需要做預(yù)處理或模糊匹配。
小結(jié)一下
實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 diff 功能并不難，關(guān)鍵在于理解 LCS 的原理和如何將其應(yīng)用于行級(jí)別的比較。用 C++ 來寫的好處是可以精細(xì)控制內(nèi)存和性能，適合嵌入系統(tǒng)或高性能工具開發(fā)。
如果你只是想快速實(shí)現(xiàn)，也可以參考現(xiàn)有的開源庫(kù)，比如 google-diff-match-patch 或者直接調(diào)用系統(tǒng)的 diff 命令，但在需要定制化功能的時(shí)候，自己實(shí)現(xiàn)還是很有必要的。
基本上就這些了。 diff 的核心不復(fù)雜，但細(xì)節(jié)容易忽略。
.png)
