設計文本差異比對 — LCS、Myers Diff 演算法與 Patch 生成實戰 | 資料結構與演算法

// ================================================================
// LCS 動態規劃 — Diff 的數學基礎
// ================================================================

/**
 * 計算兩個序列的最長公共子序列（LCS）
 * 時間複雜度：O(N×M)，空間複雜度：O(N×M)
 */
function lcs(a: string[], b: string[]): string[] {
  const N = a.length;
  const M = b.length;

  // dp[i][j] = a[0..i-1] 與 b[0..j-1] 的 LCS 長度
  const dp: number[][] = Array.from({ length: N + 1 }, () =>
    new Array(M + 1).fill(0)
  );

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  // 回溯找出 LCS 序列
  const result: string[] = [];
  let i = N, j = M;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      result.unshift(a[i - 1]);
      i--; j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return result;
}

// ─── 使用範例 ────────────────────────────────────────────
const seqA = ["A", "B", "C", "B", "D", "A", "B"];
const seqB = ["B", "D", "C", "A", "B"];
console.log(lcs(seqA, seqB));
// 輸出：["B", "C", "A", "B"]（長度 4）
// 編輯距離 = 7 + 5 - 2×4 = 4

// ================================================================
// 編輯距離 — 支援插入、刪除、替換三種操作
// ================================================================

function editDistance(a: string, b: string): number {
  const N = a.length;
  const M = b.length;

  // dp[i][j] = a[0..i-1] 轉換為 b[0..j-1] 的最小操作數
  const dp: number[][] = Array.from({ length: N + 1 }, () =>
    new Array(M + 1).fill(0)
  );

  // 基底案例：空字串的轉換
  for (let i = 0; i <= N; i++) dp[i][0] = i; // 刪除 i 個字元
  for (let j = 0; j <= M; j++) dp[0][j] = j; // 插入 j 個字元

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // 字元相同，無需操作
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // 刪除 a[i-1]
          dp[i][j - 1],     // 插入 b[j-1]
          dp[i - 1][j - 1]  // 替換 a[i-1] → b[j-1]
        );
      }
    }
  }

  return dp[N][M];
}

console.log(editDistance("kitten", "sitting"));
// 輸出：3（k→s、e→i、插入 g）

// ================================================================
// Myers Diff Algorithm — TypeScript 完整實作
// 輸出：unified diff 格式（git diff 風格）
// ================================================================

type DiffOperation = "equal" | "insert" | "delete";

interface DiffChange {
  op: DiffOperation;
  line: string;
  lineNumA?: number; // 在 A 中的行號（1-indexed）
  lineNumB?: number; // 在 B 中的行號（1-indexed）
}

interface DiffHunk {
  startA: number;
  startB: number;
  lines: DiffChange[];
}

interface DiffStats {
  additions: number;
  deletions: number;
  unchanged: number;
}

// ────────────────────────────────────────────────────────
// 核心：Myers Diff（行級）
// 時間複雜度：O(N×D)，D = 實際編輯距離
// 空間複雜度：O(N×D)（存 trace 用於回溯）
// ────────────────────────────────────────────────────────
function myersDiff(a: string[], b: string[]): DiffChange[] {
  const N = a.length;
  const M = b.length;

  if (N === 0 && M === 0) return [];
  if (N === 0) {
    return b.map((line, i) => ({ op: "insert" as const, line, lineNumB: i + 1 }));
  }
  if (M === 0) {
    return a.map((line, i) => ({ op: "delete" as const, line, lineNumA: i + 1 }));
  }

  const MAX = N + M;
  // V[k] = 在對角線 k 上能到達的最大 x 座標
  const V: number[] = new Array(2 * MAX + 1).fill(0);
  // 追蹤每個 d 步的 V 快照，用於回溯路徑
  const trace: number[][] = [];

  // Forward pass：找最短編輯距離 D
  for (let d = 0; d <= MAX; d++) {
    trace.push([...V]);

    for (let k = -d; k <= d; k += 2) {
      let x: number;

      // 選擇方向：向下（插入）或向右（刪除）
      if (k === -d || (k !== d && V[k - 1 + MAX] < V[k + 1 + MAX])) {
        x = V[k + 1 + MAX]; // 向下移動（插入 B[y]）
      } else {
        x = V[k - 1 + MAX] + 1; // 向右移動（刪除 A[x]）
      }

      let y = x - k;

      // 沿對角線延伸 snake（連續匹配，cost = 0）
      while (x < N && y < M && a[x] === b[y]) {
        x++;
        y++;
      }

      V[k + MAX] = x;

      // 到達終點 (N, M)
      if (x >= N && y >= M) {
        return backtrack(trace, a, b, N, M, MAX);
      }
    }
  }

  throw new Error("Myers diff failed to converge");
}

// ────────────────────────────────────────────────────────
// 回溯：從 trace 還原編輯腳本
// ────────────────────────────────────────────────────────
function backtrack(
  trace: number[][],
  a: string[],
  b: string[],
  N: number,
  M: number,
  MAX: number
): DiffChange[] {
  const changes: DiffChange[] = [];
  let x = N;
  let y = M;

  for (let d = trace.length - 1; d >= 0; d--) {
    const V = trace[d];
    const k = x - y;

    let prevK: number;
    if (k === -d || (k !== d && V[k - 1 + MAX] < V[k + 1 + MAX])) {
      prevK = k + 1; // 之前是向下移動（插入）
    } else {
      prevK = k - 1; // 之前是向右移動（刪除）
    }

    const prevX = V[prevK + MAX];
    const prevY = prevX - prevK;

    // snake 部分（對角線匹配，倒退還原）
    while (x > prevX && y > prevY && x > 0 && y > 0 && a[x - 1] === b[y - 1]) {
      changes.unshift({
        op: "equal", line: a[x - 1], lineNumA: x, lineNumB: y,
      });
      x--;
      y--;
    }

    // 本次編輯操作
    if (d > 0) {
      if (prevK === k + 1) {
        // 插入：從 B 取一行
        if (y > 0) {
          changes.unshift({ op: "insert", line: b[y - 1], lineNumB: y });
          y--;
        }
      } else {
        // 刪除：從 A 取一行
        if (x > 0) {
          changes.unshift({ op: "delete", line: a[x - 1], lineNumA: x });
          x--;
        }
      }
    }
  }

  return changes;
}

// ────────────────────────────────────────────────────────
// 建構 Hunk（差異區塊）
// ────────────────────────────────────────────────────────
function buildHunks(changes: DiffChange[], contextLines: number): DiffHunk[] {
  // 標記哪些 equal 行需要顯示（作為 context）
  const needed = new Set<number>();
  for (let i = 0; i < changes.length; i++) {
    if (changes[i].op !== "equal") {
      for (
        let j = Math.max(0, i - contextLines);
        j < Math.min(changes.length, i + contextLines + 1);
        j++
      ) {
        needed.add(j);
      }
    }
  }

  const hunks: DiffHunk[] = [];
  let currentHunk: DiffHunk | null = null;
  let lineA = 1;
  let lineB = 1;

  for (let i = 0; i < changes.length; i++) {
    const change = changes[i];

    if (change.op === "equal" && !needed.has(i)) {
      if (currentHunk) {
        hunks.push(currentHunk);
        currentHunk = null;
      }
      lineA++;
      lineB++;
      continue;
    }

    if (!currentHunk) {
      currentHunk = { startA: lineA, startB: lineB, lines: [] };
    }

    currentHunk.lines.push({ ...change, lineNumA: lineA, lineNumB: lineB });

    if (change.op !== "insert") lineA++;
    if (change.op !== "delete") lineB++;
  }

  if (currentHunk) hunks.push(currentHunk);
  return hunks;
}

// ────────────────────────────────────────────────────────
// Unified Diff 格式化器
// ────────────────────────────────────────────────────────
function formatUnifiedDiff(
  changes: DiffChange[],
  fileA: string = "a/file",
  fileB: string = "b/file",
  contextLines: number = 3
): string {
  const hunks = buildHunks(changes, contextLines);
  if (hunks.length === 0) return "";

  const lines: string[] = [`--- ${fileA}`, `+++ ${fileB}`];

  for (const hunk of hunks) {
    const addCount = hunk.lines.filter((l) => l.op !== "delete").length;
    const delCount = hunk.lines.filter((l) => l.op !== "insert").length;
    lines.push(`@@ -${hunk.startA},${delCount} +${hunk.startB},${addCount} @@`);

    for (const change of hunk.lines) {
      if (change.op === "equal") lines.push(` ${change.line}`);
      if (change.op === "delete") lines.push(`-${change.line}`);
      if (change.op === "insert") lines.push(`+${change.line}`);
    }
  }

  return lines.join("\n");
}

// ────────────────────────────────────────────────────────
// 統計函數
// ────────────────────────────────────────────────────────
function getDiffStats(changes: DiffChange[]): DiffStats {
  return {
    additions: changes.filter((c) => c.op === "insert").length,
    deletions: changes.filter((c) => c.op === "delete").length,
    unchanged: changes.filter((c) => c.op === "equal").length,
  };
}

// ────────────────────────────────────────────────────────
// 便利函數：直接比較兩個多行字串
// ────────────────────────────────────────────────────────
function diffStrings(
  textA: string,
  textB: string,
  fileA: string = "a/file",
  fileB: string = "b/file"
): string {
  const linesA = textA.split("\n");
  const linesB = textB.split("\n");
  const changes = myersDiff(linesA, linesB);
  return formatUnifiedDiff(changes, fileA, fileB);
}

// ────────────────────────────────────────────────────────
// Patch 套用器
// ────────────────────────────────────────────────────────
function applyPatch(original: string[], changes: DiffChange[]): string[] {
  const result: string[] = [];
  for (const change of changes) {
    if (change.op === "equal") result.push(change.line);
    if (change.op === "insert") result.push(change.line);
    // delete 的行不加入結果（跳過）
  }
  return result;
}

// ================================================================
// 完整使用示範
// ================================================================

const textA = `function hello() {
  console.log("Hello");
  return true;
}`;

const textB = `function hello(name: string) {
  console.log(\`Hello, \${name}\`);
  console.log("Done");
  return true;
}`;

// 1. 產生 diff
const diff = diffStrings(textA, textB, "a/hello.ts", "b/hello.ts");
console.log("=== Unified Diff ===");
console.log(diff);
// 輸出：
// --- a/hello.ts
// +++ b/hello.ts
// @@ -1,4 +1,5 @@
// -function hello() {
// +function hello(name: string) {
// -  console.log("Hello");
// +  console.log(`Hello, ${name}`);
// +  console.log("Done");
//    return true;
//  }

// 2. 取得統計
const linesA = textA.split("\n");
const linesB = textB.split("\n");
const changes = myersDiff(linesA, linesB);
const stats = getDiffStats(changes);
console.log("\n=== Diff 統計 ===");
console.log(stats);
// 輸出：{ additions: 3, deletions: 2, unchanged: 2 }

// 3. 套用 patch
const patched = applyPatch(linesA, changes);
console.log("\n=== Patch 後的內容 ===");
console.log(patched.join("\n"));
// 輸出：與 textB 相同

// 4. 驗證 patch 正確性
console.log("\nPatch 正確：", patched.join("\n") === textB);
// 輸出：Patch 正確：true

// ================================================================
// Myers Diff Algorithm — C++ 高效實作
// 線性空間分治版：O(N×D) 時間，O(N+D) 空間
// ================================================================

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <tuple>
#include <chrono>

struct DiffChange {
    enum class Op { EQUAL, INSERT, DELETE };
    Op op;
    std::string line;
    int lineNumA = -1; // -1 表示不適用
    int lineNumB = -1;
};

class MyersDiff {
public:
    struct EditScript {
        std::vector<DiffChange> changes;
        int additions = 0;
        int deletions = 0;
        int unchanged = 0;
    };

    // 主要入口：比較兩個字串向量
    static EditScript diff(
        const std::vector<std::string>& a,
        const std::vector<std::string>& b
    ) {
        EditScript result;
        const int N = static_cast<int>(a.size());
        const int M = static_cast<int>(b.size());

        if (N == 0 && M == 0) return result;

        if (N == 0) {
            for (int i = 0; i < M; i++) {
                result.changes.push_back(
                    {DiffChange::Op::INSERT, b[i], -1, i + 1});
                result.additions++;
            }
            return result;
        }

        if (M == 0) {
            for (int i = 0; i < N; i++) {
                result.changes.push_back(
                    {DiffChange::Op::DELETE, a[i], i + 1, -1});
                result.deletions++;
            }
            return result;
        }

        // 分治法計算 diff
        auto changes = computeDiff(a, b, 0, N, 0, M);

        // 填充行號
        int lineA = 1, lineB = 1;
        for (auto& c : changes) {
            c.lineNumA = (c.op != DiffChange::Op::INSERT) ? lineA : -1;
            c.lineNumB = (c.op != DiffChange::Op::DELETE) ? lineB : -1;
            if (c.op != DiffChange::Op::INSERT) lineA++;
            if (c.op != DiffChange::Op::DELETE) lineB++;
        }

        result.changes = std::move(changes);
        for (const auto& c : result.changes) {
            if (c.op == DiffChange::Op::INSERT) result.additions++;
            else if (c.op == DiffChange::Op::DELETE) result.deletions++;
            else result.unchanged++;
        }

        return result;
    }

    // 輸出 unified diff 格式
    static std::string formatUnified(
        const EditScript& script,
        const std::string& fileA = "a/file",
        const std::string& fileB = "b/file",
        int context = 3
    ) {
        std::ostringstream oss;
        oss << "--- " << fileA << "\n";
        oss << "+++ " << fileB << "\n";

        const auto& changes = script.changes;
        std::vector<bool> needed(changes.size(), false);
        for (int i = 0; i < static_cast<int>(changes.size()); i++) {
            if (changes[i].op != DiffChange::Op::EQUAL) {
                for (int j = std::max(0, i - context);
                     j < std::min((int)changes.size(), i + context + 1);
                     j++) {
                    needed[j] = true;
                }
            }
        }

        int lineA = 1, lineB = 1;
        int i = 0;
        while (i < static_cast<int>(changes.size())) {
            if (!needed[i]) {
                if (changes[i].op != DiffChange::Op::INSERT) lineA++;
                if (changes[i].op != DiffChange::Op::DELETE) lineB++;
                i++;
                continue;
            }

            int startA = lineA, startB = lineB;
            std::vector<int> hunkIdx;
            while (i < (int)changes.size() && needed[i]) {
                hunkIdx.push_back(i++);
            }

            int delCount = 0, addCount = 0;
            for (int idx : hunkIdx) {
                if (changes[idx].op != DiffChange::Op::INSERT) delCount++;
                if (changes[idx].op != DiffChange::Op::DELETE) addCount++;
            }

            oss << "@@ -" << startA << "," << delCount
                << " +" << startB << "," << addCount << " @@\n";

            for (int idx : hunkIdx) {
                const auto& c = changes[idx];
                if (c.op == DiffChange::Op::EQUAL) oss << " " << c.line << "\n";
                if (c.op == DiffChange::Op::DELETE) oss << "-" << c.line << "\n";
                if (c.op == DiffChange::Op::INSERT) oss << "+" << c.line << "\n";

                if (c.op != DiffChange::Op::INSERT) lineA++;
                if (c.op != DiffChange::Op::DELETE) lineB++;
            }
        }

        return oss.str();
    }

    // 比較兩個多行字串（便利函數）
    static std::string diffStrings(
        const std::string& textA,
        const std::string& textB,
        const std::string& fileA = "a/file",
        const std::string& fileB = "b/file"
    ) {
        auto script = diff(splitLines(textA), splitLines(textB));
        return formatUnified(script, fileA, fileB);
    }

private:
    // 分治法計算 diff（線性空間）
    static std::vector<DiffChange> computeDiff(
        const std::vector<std::string>& a, const std::vector<std::string>& b,
        int aLo, int aHi, int bLo, int bHi
    ) {
        // 基底情況：一方為空
        if (aLo == aHi) {
            std::vector<DiffChange> result;
            for (int j = bLo; j < bHi; j++) {
                result.push_back({DiffChange::Op::INSERT, b[j], -1, -1});
            }
            return result;
        }
        if (bLo == bHi) {
            std::vector<DiffChange> result;
            for (int i = aLo; i < aHi; i++) {
                result.push_back({DiffChange::Op::DELETE, a[i], -1, -1});
            }
            return result;
        }

        // 找中間蛇（middle snake）
        auto [x, y, u, v] = findMiddleSnake(a, b, aLo, aHi, bLo, bHi);

        // 分治：左半部 + middle snake + 右半部
        auto left = computeDiff(a, b, aLo, x, bLo, y);

        // 中間 snake（equal 部分）
        for (int i = x, j = y; i < u; i++, j++) {
            left.push_back({DiffChange::Op::EQUAL, a[i], -1, -1});
        }

        auto right = computeDiff(a, b, u, aHi, v, bHi);
        left.insert(left.end(), right.begin(), right.end());
        return left;
    }

    // 找中間蛇（Myers 分治核心）
    static std::tuple<int, int, int, int> findMiddleSnake(
        const std::vector<std::string>& a, const std::vector<std::string>& b,
        int aLo, int aHi, int bLo, int bHi
    ) {
        const int N = aHi - aLo;
        const int M = bHi - bLo;
        const int delta = N - M;
        const int MAX = (N + M + 1) / 2 + 1;

        std::vector<int> Vf(2 * MAX + 2, 0); // 前向 V
        std::vector<int> Vr(2 * MAX + 2, 0); // 反向 V
        Vr[MAX + 1] = N;

        for (int d = 0; d <= (N + M + 1) / 2; d++) {
            // 前向搜尋
            for (int k = -d; k <= d; k += 2) {
                int x;
                if (k == -d || (k != d && Vf[k - 1 + MAX] < Vf[k + 1 + MAX])) {
                    x = Vf[k + 1 + MAX];
                } else {
                    x = Vf[k - 1 + MAX] + 1;
                }
                int y = x - k;
                int sx = x, sy = y;
                while (x < N && y < M && a[aLo + x] == b[bLo + y]) {
                    x++; y++;
                }
                Vf[k + MAX] = x;

                if ((delta % 2 != 0) &&
                    (k - delta) >= -(d - 1) && (k - delta) <= (d - 1)) {
                    if (Vf[k + MAX] + Vr[k - delta + MAX] >= N) {
                        return {aLo + sx, bLo + sy, aLo + x, bLo + y};
                    }
                }
            }

            // 反向搜尋
            for (int k = -d; k <= d; k += 2) {
                int x;
                if (k == -d || (k != d && Vr[k - 1 + MAX] > Vr[k + 1 + MAX])) {
                    x = Vr[k + 1 + MAX] - 1;
                } else {
                    x = Vr[k - 1 + MAX];
                }
                int y = x - (k + delta);
                int ex = x, ey = y;
                while (x > 0 && y > 0 &&
                       a[aLo + x - 1] == b[bLo + y - 1]) {
                    x--; y--;
                }
                Vr[k + MAX] = x;

                if ((delta % 2 == 0) &&
                    (k + delta) >= -d && (k + delta) <= d) {
                    if (Vf[k + delta + MAX] + Vr[k + MAX] >= N) {
                        return {aLo + x, bLo + y, aLo + ex, bLo + ey};
                    }
                }
            }
        }

        return {aLo, bLo, aLo, bLo}; // 不應到達
    }

    static std::vector<std::string> splitLines(const std::string& text) {
        std::vector<std::string> lines;
        std::istringstream stream(text);
        std::string line;
        while (std::getline(stream, line)) {
            lines.push_back(line);
        }
        return lines;
    }
};

// ================================================================
// 效能基準測試
// ================================================================

void benchmarkMyersDiff() {
    // 產生測試資料：兩份 5000 行的程式碼，差異約 5%
    std::vector<std::string> fileA, fileB;
    for (int i = 0; i < 5000; i++) {
        fileA.push_back("line " + std::to_string(i) +
                        ": original content here");
    }
    fileB = fileA; // 複製

    // 修改 5% 的行（模擬小幅修改）
    for (int i = 0; i < 5000; i += 20) {
        fileB[i] = "line " + std::to_string(i) + ": MODIFIED content here";
    }
    // 插入 50 行
    for (int i = 0; i < 50; i++) {
        fileB.insert(fileB.begin() + i * 100, "NEW LINE inserted");
    }

    auto t0 = std::chrono::high_resolution_clock::now();
    auto script = MyersDiff::diff(fileA, fileB);
    auto t1 = std::chrono::high_resolution_clock::now();

    double ms = std::chrono::duration_cast<std::chrono::microseconds>(
                    t1 - t0).count() / 1000.0;

    std::cout << "\n=== 效能基準 ===\n";
    std::cout << "檔案 A：" << fileA.size() << " 行\n";
    std::cout << "檔案 B：" << fileB.size() << " 行\n";
    std::cout << "新增：" << script.additions << " 行\n";
    std::cout << "刪除：" << script.deletions << " 行\n";
    std::cout << "未變更：" << script.unchanged << " 行\n";
    std::cout << "耗時：" << ms << " ms\n";
}

// ================================================================
// 主程式示範
// ================================================================

int main() {
    std::cout << "=== Myers Diff C++ 演示 ===\n\n";

    std::string textA = R"(function hello() {
  console.log("Hello");
  return true;
})";

    std::string textB = R"(function hello(name) {
  console.log("Hello, " + name);
  console.log("Done");
  return true;
})";

    std::string result = MyersDiff::diffStrings(
        textA, textB, "a/hello.js", "b/hello.js");
    std::cout << result << std::endl;
    // 輸出：
    // --- a/hello.js
    // +++ b/hello.js
    // @@ -1,4 +1,5 @@
    // -function hello() {
    // +function hello(name) {
    // -  console.log("Hello");
    // +  console.log("Hello, " + name);
    // +  console.log("Done");
    //    return true;
    //  }

    // 效能基準
    benchmarkMyersDiff();
    // 輸出：
    // === 效能基準 ===
    // 檔案 A：5000 行
    // 檔案 B：5050 行
    // 新增：~300 行
    // 刪除：~250 行
    // 未變更：~4750 行
    // 耗時：< 50 ms

    return 0;
}

// 行雜湊優化：將字串比較轉為數字比較
function hashLine(line: string): number {
  // FNV-1a 雜湊
  let hash = 0x811c9dc5;
  for (let i = 0; i < line.length; i++) {
    hash ^= line.charCodeAt(i);
    hash = (hash * 0x01000193) >>> 0;
  }
  return hash;
}

function optimizedDiff(a: string[], b: string[]): DiffChange[] {
  // 第一步：計算每行的雜湊值
  const hashA = a.map(hashLine);
  const hashB = b.map(hashLine);

  // 第二步：用雜湊值做 Myers Diff（數字比較遠快於字串比較）
  // 第三步：碰撞驗證——對 diff 結果中的 equal 行驗證原始字串是否真的相同
  // 略：實作與 myersDiff 類似，但比較 hashA[x] === hashB[y]
  return myersDiff(a, b); // 簡化示範
}

// 生產環境推薦：使用 Yjs CRDT 實現即時協作
import * as Y from "yjs";
import { WebsocketProvider } from "y-websocket";

const doc = new Y.Doc();
const text = doc.getText("content");

// 透過 WebSocket 自動同步（底層使用 CRDT）
const provider = new WebsocketProvider(
  "wss://your-sync-server.com",
  "document-id",
  doc
);

// 本地編輯（自動廣播並合併）
text.insert(0, "Hello, World!");

// 監聽遠端變更
text.observe((event) => {
  console.log("Document changed:", text.toString());
});