Case Study: LCS trong git diff & Huffman trong gzip

TL;DR: Mỗi lần bạn chạy git diff hay nén file .gz, 2 thuật toán DP chạy ngầm: (A) git diff dùng Myers algorithm — variant của LCS (Longest Common Subsequence) — để tìm dòng chung dài nhất giữa 2 phiên bản file, từ đó tạo minimal edit script hiển thị +/-. (B) gzip (DEFLATE) dùng Huffman coding — cây nhị phân tối ưu theo tần suất ký tự — để gán mã ngắn hơn cho ký tự xuất hiện nhiều, tiết kiệm 40-70% kích thước so với ASCII fixed-width 8-bit.

Module 1 đã xây nền DP: subproblem, memoization, transition. Bài này không dạy thêm kỹ thuật mới — nó cho thấy 2 bài toán production thực tế là DP, giải thích tại sao DP là lựa chọn đúng, và đọc cơ chế đủ sâu để bạn hiểu output hàng ngày (dấu +/- của diff, tỷ lệ nén gzip) xuất phát từ đâu.

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

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

Khi bạn sửa 1 file và chạy git diff, output hiển thị dòng nào bị xoá (-) và dòng nào được thêm (+). Câu hỏi nền tảng: git quyết định dòng nào là "chung" (unchanged) và dòng nào là "thay đổi" như thế 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 ta tìm dãy dòng chung dài nhất (LCS) giữa A và B, ta được ["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 chính là "bộ khung chung" của 2 file — phần không thay đổi. Phần thay đổi (edit) = tổng dòng ngoài LCS. Minimal diff = minimal edit = LCS dài nhất.

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

Subproblem: lcs[i][j] = độ dài LCS của A[0..i-1] và B[0..j-1].

lcs(A, B):
    n <- A.length
    m <- B.length

    -- Khởi tạo bảng (n+1) x (m+1), base case = 0
    dp[0..n][0..m] <- 0

    for i from 1 to n:
        for j from 1 to m:
            if A[i-1] = B[j-1]:
                dp[i][j] <- dp[i-1][j-1] + 1   -- dòng khớp, kéo dài LCS
            else:
                dp[i][j] <- max(dp[i-1][j], dp[i][j-1])  -- bỏ dòng A hoặc dòng B

    return dp[n][m]

-- Time: O(n*m)  Space: O(n*m)

Transition max(dp[i-1][j], dp[i][j-1]) — bỏ dòng A i hoặc dòng B j, chọn cái nào giữ được LCS dài hơn.

Lưu ý quan trọng: "dòng chung" ở đây nghĩa là nội dung dòng giống hệt nhau, không phải vị trí dòng. Git so sánh nội dung text, không phải số thứ tự dòng.

graph LR
    subgraph "Bảng LCS — A=['apple','banana','cherry','date'], B=['apple','cherry','date']"
        R0["  | ε | a | c | d"]
        R1["ε | 0 | 0 | 0 | 0"]
        R2["a | 0 | 1 | 1 | 1"]
        R3["b | 0 | 1 | 1 | 1"]
        R4["c | 0 | 1 | 2 | 2"]
        R5["d | 0 | 1 | 2 | 3"]
    end

dp[4][3] = 3 — LCS là ["apple","cherry","date"], đúng với 3 dòng unchanged.

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

Git không dùng LCS DP O(n×m) thuần túy — file thực tế có hàng nghìn dòng, O(n×m) quá chậm. Git dùng Myers diff algorithm (1986) — tìm minimal edit script trên "edit graph":

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)

Minimal diff = đường đi từ (0,0) đến (n,m) với số cạnh có cost nhỏ nhất.

Myers tìm đường này bằng BFS theo "edit distance" (d = số cạnh cost-1), mở rộng theo diagonal "snake" (chuỗi cạnh chéo liên tiếp). Complexity: O(n + m + D²) với D là edit distance thực tế — thường D rất nhỏ so với n, m → nhanh hơn LCS DP nhiều lần.

graph TD
    subgraph "Edit graph (đơn giản 3 dòng)"
        N00["(0,0)"] -- "chéo: match apple" --> N11["(1,1)"]
        N11 -- "dọc: delete banana" --> N21["(2,1)"]
        N21 -- "chéo: match cherry" --> N32["(3,2)"]
        N32 -- "chéo: match date" --> N43["(3,3) ✓"]
    end

Path (0,0) → (1,1) → (2,1) → (3,2) → (3,3): 1 cạnh dọc (delete "banana"), 3 cạnh chéo (match) → D=1, minimal.

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

Khi bạn di chuyển một function lớn xuống cuối file, git diff có thể hiển thị nó như "xoá ở chỗ cũ, thêm ở chỗ mới" thay vì "moved". Lý do: LCS/Myers tối ưu theo số dòng thay đổi tối thiểu, không có khái niệm "move". Thuật toán nhìn thấy dòng giống nhau ở vị trí mới và cố gắng "match", nhưng với function dài, nhiều dòng khác xung quanh có thể "chen" vào LCS trước — kết quả diff trông rối.

git diff -W (extended context) và git log -S "pattern" (pickaxe search) là công cụ tốt hơn khi cần trace code movement qua history.

Phần B — Huffman coding trong gzip/DEFLATE

5. Vấn đề: ASCII cố định 8 bit, lãng phí

ASCII dùng 8 bit cho mọi ký tự — từ e (xuất hiện ~12% trong tiếng Anh) đến z (dưới 1%). Không ký tự nào được ưu tiên — cùng 8 bit cho dù xuất hiện 1 lần hay 1 triệu lần.

File text 1 MB = 8 triệu bit. Nếu ta dùng mã ngắn hơn cho ký tự phổ biến và mã dài hơn cho ký tự hiếm — tổng bit giảm xuống.

Đây là ý tưởng của Huffman coding (1952): xây cây nhị phân tối ưu theo tần suất, gán mã độ dài biến đổi (variable-length code).

6. Xây cây Huffman — greedy DP bottom-up

Cho tần suất ký tự trong file:

Ví dụ: "aabbbccccdddddd"
  a: 2,  b: 3,  c: 4,  d: 6
  Tổng: 15 ký tự

Thuật toán Huffman:

buildHuffman(frequencies):
    -- Mỗi ký tự là 1 node lá, đặt vào MinHeap theo tần suất
    H <- MinHeap
    for each (char, freq) trong frequencies:
        H.push(LeafNode(char, freq))

    -- Gộp 2 node nhỏ nhất thành node nội cho đến khi còn 1 node (gốc)
    while H.size() > 1:
        left  <- H.pop()    -- node tần suất nhỏ nhất
        right <- H.pop()    -- node tần suất nhỏ thứ hai
        merged <- InternalNode(left, right, left.freq + right.freq)
        H.push(merged)

    return H.pop()          -- gốc của cây Huffman

-- Time: O(n log n)  Space: O(n)  với n là số ký tự phân biệt

Tại sao greedy đúng? Ký tự tần suất nhỏ được gộp trước → nằm sâu hơn trong cây → mã dài hơn. Ký tự tần suất lớn được gộp sau → gần gốc → mã ngắn hơn. Có thể chứng minh bằng exchange argument: bất kỳ swap nào giữa 2 node cũng làm tổng bit tăng lên.

Trace ví dụ:

Bước 1 — MinHeap ban đầu: [a:2, b:3, c:4, d:6]

Bước 2 — Gộp a:2 + b:3 = ab:5
  Heap: [c:4, ab:5, d:6]

Bước 3 — Gộp c:4 + ab:5 = cab:9
  Heap: [d:6, cab:9]

Bước 4 — Gộp d:6 + cab:9 = root:15
  Cây hoàn chỉnh

graph TD
    ROOT["root: 15"] -- "0" --> D["d: 6"]
    ROOT -- "1" --> CAB["cab: 9"]
    CAB -- "0" --> C["c: 4"]
    CAB -- "1" --> AB["ab: 5"]
    AB -- "0" --> A["a: 2"]
    AB -- "1" --> B["b: 3"]

7. Đọc mã từ cây Huffman

Đi từ gốc xuống: rẽ trái = bit 0, rẽ phải = bit 1. Mã của mỗi ký tự:

Tổng bit với Huffman:

d: 6 × 1 = 6 bit
c: 4 × 2 = 8 bit
b: 3 × 3 = 9 bit
a: 2 × 3 = 6 bit
Tổng: 29 bit

So với ASCII 8-bit cố định: 15 × 8 = 120 bit
Tiết kiệm: (120 - 29) / 120 ≈ 76%

Prefix-free property: không mã nào là tiền tố của mã khác (vì mỗi ký tự là node lá, không nằm trên đường đến lá khác). Điều này đảm bảo giải mã không mơ hồ: đọc bit từ trái, mỗi khi match một lá thì đó là ký tự — không cần dấu phân cách.

8. DEFLATE — Huffman trong gzip thực tế

gzip dùng chuẩn DEFLATE (RFC 1951) — kết hợp 2 bước:

Bước 1 — LZ77 (1977): tìm chuỗi lặp lại
  Thay vì lưu "abcabc", lưu "abc" + (offset=3, length=3)
  → giảm entropy (loại bỏ redundancy theo vị trí)

Bước 2 — Huffman coding: nén ký tự theo tần suất
  Áp lên output của LZ77 (ký tự + backreference token)
  → giảm thêm theo tần suất phân phối

DEFLATE không phải thuần Huffman — nó là Huffman trên output của LZ77. LZ77 xử lý redundancy "theo chiều ngang" (chuỗi lặp lại), Huffman xử lý redundancy "theo chiều dọc" (ký tự phổ biến). Kết hợp 2 bước đạt tỷ lệ nén 40-70% cho file text thông thường.

graph LR
    RAW["File gốc<br/>120 KB"] -- "LZ77<br/>loại lặp lại" --> LZ["Sau LZ77<br/>~60 KB"]
    LZ -- "Huffman<br/>nén tần suất" --> GZ["File .gz<br/>~36 KB"]

Tại sao gzip không chỉ dùng Huffman? Huffman một mình không xử lý được chuỗi lặp lại (ví dụ file log với timestamp pattern). LZ77 phá pattern lặp lại trước, sau đó Huffman nén phân phối ký tự của phần còn lại — hiệu quả cộng hưởng.

9. Ứng dụng thực tế Huffman ngoài gzip

HTTP/2 đặc biệt thú vị: HPACK (RFC 7541) dùng Huffman table tĩnh được precompute trên tần suất thống kê của HTTP headers qua hàng triệu request thực tế — không cần truyền cây Huffman trong mỗi connection.

10. Bảng so sánh 2 DP

Tự kiểm tra

Bài tiếp theo: Module 1 — Tổng kết & cheat sheet