Data compression · Nén dữ liệu
Why compress data
- Data takes up space to store and time to send.
- Compression makes a file smaller so it is cheaper to save and faster to share.
- There are two kinds: lossless and lossy.
Tại sao nén dữ liệu
- Dữ liệu chiếm không gian để lưu trữ và mất thời gian để truyền tải.
- Nén làm cho tệp nhỏ hơn, giúp tiết kiệm chi phí lưu trữ và tăng tốc độ chia sẻ.
- Có hai loại chính: nén không mất mát và nén có mất mát.
Lossless compression
- Lossless makes a file smaller but keeps every bit of the data.
- When you open the file, you get back the exact original.
- It works by finding patterns and writing them in a shorter way.
Nén không mất mát
- Nén không mất mát làm giảm kích thước tệp nhưng vẫn giữ nguyên toàn bộ dữ liệu gốc.
- Khi mở tệp, bạn sẽ thu được file chính xác như ban đầu.
- Nó hoạt động bằng cách tìm kiếm các mẫu dữ liệu và viết lại chúng theo cách ngắn gọn hơn.
Original: AAAAAAAA-BBB
Shorter: 8A-3B (8 A's, then 3 B's)
Open it: AAAAAAAA-BBB (exactly the same again)
Lossy compression
- Lossy makes a file much smaller by throwing away some data.
- It drops details that people can barely see or hear.
- You cannot get the exact original back — but it is "close enough".
Nén có mất mát
- Nén có mất mát làm giảm kích thước tệp đáng kể bằng cách loại bỏ một phần dữ liệu.
- Nó loại bỏ các chi tiết mà con người khó có thể nhìn thấy hoặc nghe thấy.
- Bạn không thể khôi phục lại file gốc chính xác — nhưng nó đủ gần để sử dụng.
Photo (large) --lossy--> Photo (small)
A few colors and fine details are gone,
but your eye hardly notices.
The trade-off: size vs quality
- Lossless keeps full quality, but the file stays larger.
- Lossy gives a much smaller file, but quality goes down a little.
- You choose based on what matters more: perfect data or small size.
Sự đánh đổi: kích thước vs chất lượng
- Nén không mất mát giữ nguyên chất lượng đầy đủ, nhưng kích thước tệp vẫn lớn.
- Nén có mất mát cung cấp kích thước tệp nhỏ hơn nhiều, nhưng chất lượng bị giảm nhẹ.
- Bạn cần lựa chọn dựa trên yếu tố nào quan trọng hơn: dữ liệu hoàn hảo hay kích thước nhỏ.
When to use each
- Use lossless when every detail must be exact.
- Use lossy when a small drop in quality is fine and small size matters.
Khi nào sử dụng từng loại
- Sử dụng nén không mất mát khi yêu cầu chi tiết phải chính xác tuyệt đối.
- Sử dụng nén có mất mát khi sự sụt giảm nhẹ về chất lượng là chấp nhận được và ưu tiên kích thước nhỏ.
Lossless: text, code, a .zip file, a spreadsheet
Lossy: photos (JPEG), music (MP3), video
Key idea
- Compression trades size against quality (or against work to undo it).
- Lossless = smaller and perfect; lossy = much smaller but not exact.
- Good engineers pick the right kind for the job.
Ý tưởng cốt lõi
- Nén là sự đánh đổi giữa kích thước và chất lượng (hoặc giữa kích thước và nỗ lực để khôi phục lại).
- Nén không mất mát = nhỏ hơn và hoàn hảo; nén có mất mát = nhỏ hơn nhiều nhưng không chính xác.
- Các kỹ sư giỏi sẽ chọn đúng loại nén cho từng nhiệm vụ cụ thể.
Run-length encoding
- Run-length encoding (RLE) is a simple lossless method.
- A run is a stretch of the same character repeated. RLE stores a count instead of the repeats.
- We will store each run as a pair
[character, count]inside a list.
Mã hóa độ dài chuỗi (Run-length encoding)
- Mã hóa độ dài chuỗi (RLE) là một phương pháp nén không mất mát đơn giản.
- Một chuỗi (run) là một dãy các ký tự giống nhau liên tiếp. RLE lưu trữ số lượng thay vì ghi lại các ký tự lặp lại.
- Chúng ta sẽ lưu trữ mỗi lần chạy dưới dạng cặp
[character, count]bên trong một danh sách.
"AAAB" -> [["A", 3], ["B", 1]] (3 A's, then 1 B)
[["A", 3], ["B", 1]] -> "AAAB" (decode it back — exact again)
Common mistakes
- Lossless compression can be reversed exactly; lossy throws away detail.
- More compression can mean lower quality.
Lỗi thường gặp
- Nén không mất mát có thể đảo ngược hoàn toàn; nén có mất mát thì loại bỏ thông tin chi tiết.
- Mức độ nén cao hơn thường dẫn đến chất lượng thấp hơn.
Now you try
- Build RLE yourself: an encoder, a decoder, and a length helper.
- Each task checks your function on several inputs. Press Check answer.
Bây giờ bạn thử
- Tự xây dựng RLE: gồm một bộ mã hóa, một bộ giải mã và một hàm hỗ trợ đo độ dài.
- Mỗi bài kiểm tra sẽ áp dụng hàm của bạn lên nhiều đầu vào khác nhau. Nhấn Kiểm tra đáp án.
Lossless compression · Nén không mất mát
Run-length encoding replaces a run of repeats with count + symbol. · Mã hóa run-length thay thế một chuỗi lặp lại bằng số lượng + ký hiệu.
Write encode(text) for run-length encoding. Return a list of [character, count] pairs, one per run of repeats. Example: encode("AAAB") → [['A', 3], ['B', 1]]. For the empty string return []. · Viết encode(text) cho mã hóa run-length. Trả về một danh sách các cặp [character, count], mỗi cặp tương ứng với một chuỗi lặp lại. Ví dụ: encode("AAAB") → [['A', 3], ['B', 1]]. Đối với chuỗi rỗng, trả về [].
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write decode(pairs) that reverses the encoder: given a list of [character, count] pairs, rebuild the original string. Example: decode([['A', 3], ['B', 1]]) → 'AAAB'. For [] return ''. · Viết decode(pairs) đảo ngược bộ mã hóa: nhận vào một danh sách các cặp [character, count], tái tạo chuỗi gốc. Ví dụ: decode([['A', 3], ['B', 1]]) → 'AAAB'. Đối với [] trả về ''.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Without decoding, write original_length(pairs) that returns how many characters the original text had — just add up the counts. Example: original_length([['A', 3], ['B', 1]]) → 4. · Không cần giải mã, hãy viết original_length(pairs) trả về số lượng ký tự mà văn bản gốc có — chỉ cần cộng tất cả các số lượng lại. Ví dụ: original_length([['A', 3], ['B', 1]]) → 4.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.