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.

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

Đọc bảng theo hàng thì tiêu chí của diff hiện ra thành một quy tắc cơ học: hàng "banana" lặp lại y nguyên hàng ngay trên nó, không ô nào tăng. Không tăng nghĩa là thêm dòng đó vào file không làm LCS dài thêm dòng nào — và đó chính xác 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 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.

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

Chữ "D" chỉ là một chữ cái cho tới khi nhìn thấy đường đi. Bốn cạnh, ba trong số đó đi chéo và không tốn gì, đúng một cạnh dọc phải trả tiền — nên D = 1 cho cặp file này. Vẽ trên mặt phẳng toạ độ thật thì hình dạng đường đi mang thông tin: gần như chéo suốt tức là diff nhỏ, và Myers chỉ mở rộng tìm kiếm tới độ sâu D chứ không điền hết bảng.

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.

Thử ngẫmbạn nhận review một PR mà git diff hiện cả một hàm bị xoá và thêm lại y hệt. Trước khi nghi ngờ đồng nghiệp code ẩu, cơ chế LCS/Myers ở trên gợi ý điều gì đang xảy ra?

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

Phần dưới hình trả lời trước câu hỏi mà mục 7 sẽ đặt ra: vì sao đọc được một dải bit liền tù tì mà không cần dấu phân cách nào. Dải 110111100 cắt được duy nhất một kiểu, vì mọi ký tự đều nằm ở lá nên không mã nào là đoạn đầu của mã khác.

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.

Chỗ vấp nằm ở chữ "khác nhau": vì sao một tầng không làm thay được tầng kia. Với ba dòng log gần như giống hệt ở đầu hình, Huffman một mình chỉ đếm được rằng chữ số 0 hay xuất hiện — nó nhìn từng ký tự rời nên hoàn toàn không biết dòng 2 vừa lặp lại dòng 1. Ngược lại, nén tiếp một file .zip thì gần như không nhỏ thêm: LZ77 hết chuỗi lặp để bắt, Huffman hết chênh lệch tần suất để khai thác.

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.

Thử ngẫmteam bạn định nén thêm bằng Huffman thủ công trước khi lưu ảnh JPEG lên S3. JPEG đã tự dùng Huffman cho hệ số DCT rồi — bước thêm đó có tiết kiệm thêm dung lượng không?

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