Case study: LCS trong git diff và Huffman trong gzip

TL;DR: Mỗi lần bạn chạy git diff, git merge hay nén file .gz, hai thuật toán cổ điển chạy ngầm. git diff mặc định dùng thuật toán Myers, một biến thể của LCS (Longest Common Subsequence, vốn là bài DP), để tìm danh sách thay đổi ít nhất giữa hai phiên bản. git merge chạy diff hai lần, từ bản gốc sang mỗi nhánh, rồi gộp các thay đổi không chồng nhau. gzip (DEFLATE) dùng Huffman coding, một thuật toán greedy chạy bằng MinHeap, gán mã ngắn cho ký tự xuất hiện nhiều và chỉ truyền độ dài mã thay vì truyền cả cây.

Các bài trước đã xây nền DP và greedy. Bài này không dạy kỹ thuật mới mà cho bạn xem chúng chạy trong công cụ thật. Với mỗi công cụ, hãy hỏi như khi đọc đề bài: input là gì, output là gì, nó đang tối ưu cái gì. Với diff: vào là hai danh sách dòng, ra là danh sách thay đổi, tối ưu là số thay đổi ít nhất.

Phần A: LCS trong git diff và Myers algorithm

1. Vì sao diff = bài toán LCS

git diff đánh dấu dòng bị xoá (-) và dòng được thêm (+). Câu hỏi nền tảng: git quyết định dòng nào là "chung" và dòng nào là "thay đổi" bằng cách nào?

Xét 2 phiên bản file:

-- File A (cũ):          -- File B (mới):
line 1: "apple"          line 1: "apple"
line 2: "banana"         line 2: "cherry"
line 3: "cherry"         line 3: "date"
line 4: "date"

Nếu bạn tìm dãy dòng chung dài nhất (LCS) giữa A và B, kết quả là ["apple", "cherry", "date"] — 3 dòng chung. Từ đó:

• Dòng trong A nhưng không trong LCS → bị xoá (dấu -).
• Dòng trong B nhưng không trong LCS → được thêm (dấu +).

git diff output:
   apple
-  banana
   cherry
   date

LCS là "bộ khung chung" của 2 file; phần thay đổi là các dòng nằm ngoài nó. Diff nhỏ nhất = LCS dài nhất.

2. LCS là DP cổ điển

lcs[i][j] là độ dài LCS của A[0..i-1] và B[0..j-1]. Bảng dựng giống hệt bài 03, chỉ đổi ký tự thành dòng: dòng khớp thì dp[i-1][j-1] + 1, không khớp thì max(dp[i-1][j], dp[i][j-1]), tức bỏ dòng A hoặc dòng B. "Dòng chung" nghĩa là nội dung giống hệt nhau, không cần cùng số thứ tự dòng. Thời gian và bộ nhớ đều O(n×m).

dp[4][3] = 3: LCS là ["apple","cherry","date"], đúng với 3 dòng không đổi.

Hàng "banana" lặp lại y nguyên hàng ngay trên nó, không ô nào tăng: thêm dòng đó vào không làm LCS dài thêm, và đó đúng là định nghĩa của dòng bị xoá trong output.

3. Myers algorithm: git dùng gì thực tế

Git không dùng LCS DP O(n×m) thuần tuý, vì file thực tế có hàng nghìn dòng và O(n×m) quá chậm. Git dùng Myers diff algorithm (1986), tìm danh sách thay đổi ít nhất trên một "edit graph" (đồ thị các bước sửa):

Edit graph: đỉnh (i, j) = đã xét i dòng của A và j dòng của B
  Cạnh ngang (i,j) → (i, j+1): insert dòng B[j]    (cost 1)
  Cạnh dọc  (i,j) → (i+1, j): delete dòng A[i]     (cost 1)
  Cạnh chéo (i,j) → (i+1,j+1): match (A[i]=B[j])   (cost 0)

Diff nhỏ nhất = đường đi từ (0,0) đến (n,m) qua ít cạnh tốn phí nhất.

Myers tìm đường này bằng BFS theo d (số cạnh tốn phí 1), mở rộng theo "snake" (chuỗi cạnh chéo liên tiếp). Độ phức tạp trường hợp xấu nhất là O((n + m) × D) với D là số dòng thêm cộng số dòng xoá, và kỳ vọng cỡ O(n + m + D²) với dữ liệu "bình thường". D thường rất nhỏ so với n, m nên Myers nhanh hơn LCS DP nhiều lần.

Đường đi (0,0) → (1,1) → (2,1) → (3,2) → (4,3) có 1 cạnh dọc (delete "banana") và 3 cạnh chéo (match), nên D=1 và đây là diff nhỏ nhất.

4. Tại sao git diff đôi khi cho kết quả "lạ"

Khi bạn di chuyển một function lớn xuống cuối file, git diff hiện nó thành "xoá ở chỗ cũ, thêm ở chỗ mới", vì LCS/Myers chỉ tối ưu số dòng thay đổi và không có khái niệm "di chuyển". Có thể có nhiều diff cùng nhỏ nhất, và chọn diff nào quyết định chuyện đọc có dễ không. Git cho chọn thuật toán bằng --diff-algorithm=myers|minimal|patience|histogram, mặc định là myers. minimal tốn thêm thời gian để chắc chắn ra diff nhỏ nhất có thể. patience (Bram Cohen) neo theo các dòng xuất hiện đúng một lần ở cả hai file, nên những dòng lặp như } hay dòng trống không kéo diff lệch chỗ. histogram mở rộng patience cho các dòng ít lặp.

5. git merge ba chiều: hai lần diff rồi gộp

Merge hai nhánh cần ba phiên bản: base (tổ tiên chung), ours (nhánh bạn đang đứng), theirs (nhánh được gộp vào). Docs của git merge-file mô tả đúng như vậy: gộp mọi thay đổi dẫn từ base tới theirs vào ours. Git chạy diff hai lần (base sang ours, base sang theirs), mỗi lần ra một danh sách hunk (khối dòng thay đổi), rồi xét từng cặp.

base      ours      theirs
A         A         A
B         B2        B
C         C         C
D         D         D2
E         E         E

Hunk của ours nằm ở dòng 2, hunk của theirs ở dòng 4, giữa hai hunk còn dòng C không ai đổi. Không chồng nhau nên git áp cả hai và ra A, B2, C, D2, E, exit status 0. Hai bên sửa giống hệt nhau (cùng đổi B thành B2) thì git gộp sạch, chạy git merge-file cho exit status 0. Còn nếu theirs đổi B thành B3 thay vì đổi D, hai hunk cùng chạm dòng 2 và git dừng ở conflict.

Khối conflict

Git đặt cả hai phiên bản trong marker (HEAD là nhánh bạn đang đứng, feature là nhánh được gộp vào):

A
<<<<<<< HEAD
B2
=======
B3
>>>>>>> feature
C
D
E

Chạy thử trên git 2.50, hai dòng sát nhau (ours sửa B, theirs sửa C) cũng thành conflict dù không trùng dòng nào: ranh giới là "vùng chạm nhau", không phải "cùng một dòng".

Diff algorithm ảnh hưởng thẳng tới merge

Hunk được cắt ra từ diff, nên chọn thuật toán nào là đổi cách chia hunk. Strategy ort mặc định dùng histogram (khác git diff mặc định myers) và docs ghi lý do: tránh gộp nhầm do những dòng khớp không quan trọng, như dấu } của hai hàm khác nhau.

Thử ngẫmđội bạn hay conflict ở một file cấu hình mà mỗi lần sửa đều đụng cùng một dòng rất dài. Đổi cách định dạng file thế nào để diff cắt hunk nhỏ hơn và giảm conflict?