Nén
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| compression/kəmˈpreʃn/ | nén |
| lossless/ˈlɒsləs/ | không mất dữ liệu |
| lossy/ˈlɒsi/ | mất dữ liệu |
| bandwidth/ˈbændwɪdθ/ | băng thông |
| run-length encoding/rʌn leŋθ enˈkəʊdɪŋ/ | mã hóa theo độ dài chuỗi |
| dictionary coding/ˈdɪkʃənəri ˈkəʊdɪŋ/ | mã hóa bảng tra cứu |
| Huffman coding/ˈhʌfmən ˈkəʊdɪŋ/ | mã hóa Huffman |
| spatial/ˈspeɪʃl/ | theo không gian |
| temporal/ˈtempərəl/ | theo thời gian |
Ba chữ cái đã làm cho internet có thể tồn tại
- Năm 1987, một lập trình viên tên Phil Katz viết một chương trình nén và đưa định dạng tập tin vào phạm vi công cộng. Ông gọi nó là ZIP. Ông lúc ấy 24 tuổi.
- Không có gì trên mạng hoạt động nếu không có ý tưởng đó. Một giây video HD chưa nén mất khoảng 187 MB; một bộ phim hai giờ sẽ cần 1.3 terabytes. Phát trực tuyến qua kết nối gia đình là điều về mặt toán học không thể.
- Những bộ phim bạn xem có lẽ chỉ bằng một phần nghìn khối lượng đó, và chúng vẫn trông bình thường, vì việc nén đã loại bỏ những thứ mắt bạn vốn dĩ sẽ không bao giờ chú ý.
- Bài học này là nén dữ liệu: hai họ phương pháp, ba kỹ thuật không mất dữ liệu, và cách biện minh việc sử dụng một kỹ thuật cho một tập tin cụ thể.
Không mất dữ liệu và mất dữ liệu
- Nén dữ liệu làm giảm kích thước tập tin, tiết kiệm không gian lưu trữ và băng thông truyền dẫn, giúp tải xuống và phát trực tiếp nhanh hơn.
- Nén không mất mát (lossless) là nén mà dữ liệu gốc có thể được khôi phục lại chính xác. ZIP và PNG là nén không mất mát.
- Nén mất mát (lossy) loại bỏ vĩnh viễn một phần dữ liệu, nên dữ liệu gốc không thể được khôi phục. JPEG, MP3 và video phát trực tuyến là nén mất mát.
Khôi phục chính xác, hoặc thu nhỏ nhiều hơn
Nén không mất mát có nghĩa là:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Nén không mất mát cho phép bạn tái tạo chính xác dữ liệu gốc — điều cần thiết cho văn bản, chương trình và ZIP/PNG.
Khớp mỗi khái niệm nén với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Nén không mất mát giữ lại mọi bit (cần thiết cho văn bản/mã); nén mất mát đánh đổi chất lượng lấy kích thước (ảnh, âm thanh).
Nén không mất mát tái tạo chính xác dữ liệu gốc (cần cho văn bản và chương trình), trong khi nén mất mát loại bỏ vĩnh viễn một phần dữ liệu để thu nhỏ file (dùng cho ảnh và âm thanh).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Đó là lý do tại sao chương trình hoặc ZIP phải dùng nén không mất mát, nhưng ảnh hay bài hát có thể dùng nén mất mát.
Ví dụ minh họa: lập luận cho lựa chọn
- Một công ty lưu trữ bảng tính kế toán của mình. Loại nén nào và tại sao? Không mất mát, vì bảng tính phải được khôi phục chính xác; chỉ một giá trị bị thay đổi cũng khiến sổ sách sai lệch.
- Một nhiếp ảnh gia tải lên ảnh kỳ nghỉ vào thư mục điện thoại. Mất mát, vì ảnh được xem trên màn hình nhỏ nơi chi tiết bị loại bỏ không còn nhìn thấy, và file nhỏ hơn tải nhanh hơn cùng dùng ít bộ nhớ hơn.
- Tên loại, sau đó đưa ra lý do từ tình huống. "Mất mát nhỏ hơn" đơn lẻ không phải là lời giải thích hợp lệ.
Tập tin nào nên được nén không mất mát?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Source code phải được khôi phục chính xác — một ký tự thay đổi cũng có thể phá hỏng nó — nên cần nén không mất mát.
Mã hóa độ dài chuỗi
- Mã hóa độ dài chuỗi (RLE) thay thế một chuỗi các giá trị lặp lại bằng một giá trị và một số lượng: thay vì lưu tám điểm ảnh trắng giống nhau, hãy lưu "8, màu trắng".
- Nó rất hiệu quả với dữ liệu có chuỗi dài, chẳng hạn như biểu tượng, sơ đồ, bản quét đen-trắng và các vùng màu đồng nhất.
- Nó vô dụng, và thậm chí có thể làm cho file lớn hơn, với dữ liệu nhiễu như ảnh chụp, nơi hầu như không có hai giá trị lân cận nào bằng nhau.
Mỗi hàng trở thành các cặp số lượng và màu sắc
Mã hóa độ dài chuỗi hoạt động tốt nhất với dữ liệu có:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
RLE thay thế một chuỗi các giá trị giống nhau bằng số đếm + giá trị, nên nó phát huy hiệu quả trên vùng phẳng và vô ích với dữ liệu nhiễu.
Ví dụ minh họa: mã hóa một hàng bằng RLE
- Một hàng của ảnh đen-trắng 8 điểm ảnh đọc là: trắng trắng trắng đen đen trắng trắng trắng. Hãy mã hóa nó bằng RLE.
- Ba trắng, hai đen, ba trắng, nên
3W 2B 3W, hoặc dưới dạng các cặp,(3, 0) (2, 1) (3, 0)nếu màu trắng là 0. - Tám giá trị đã trở thành ba cặp. Bây giờ hãy mã hóa
W B W B W B W B. Tám chuỗi mỗi chuỗi chỉ một giá trị:1W 1B 1W 1B 1W 1B 1W 1B, điều này lưu trữ nhiều hơn so với ban đầu. Đó chính là lý do RLE không được sử dụng cho ảnh chụp.
Mã hóa độ dài chuỗi (phương pháp không mất mát)
Mã hóa độ dài chuỗi thay thế một chuỗi các giá trị lặp lại bằng một giá trị cộng với số đếm. Nó không mất mát — nguyên bản được tái tạo chính xác — nhưng chỉ thu nhỏ dữ liệu có các chuỗi dài.
Viết mã hàng pixel W W W B B W W W bằng mã hóa độ dài chuỗi, sử dụng định dạng 3W 2B 3W.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Ba trắng, hai đen, ba trắng. Tám giá trị trở thành ba cặp, nhưng một hàng xen kẽ sẽ trở thành tám cặp và tăng kích thước.
Mã hóa độ dài chuỗi luôn làm file nhỏ đi.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Trên dữ liệu không có chuỗi nào, chẳng hạn như ảnh chụp hoặc họa tiết xen kẽ, mỗi chuỗi đều có độ dài một và việc mã hóa lưu trữ nhiều hơn bản gốc.
Mã hóa từ điển và mã hóa Huffman
- Mã hóa từ điển, được sử dụng bởi ZIP và PNG, xây dựng một từ điển chứa các chuỗi byte lặp lại và thay thế mỗi lần xuất hiện bằng một chỉ mục ngắn. Nó phù hợp với văn bản và mã nguồn, nơi các từ và mẫu lặp đi lặp lại.
- Mã hóa Huffman gán mã ngắn cho các ký hiệu thường gặp và mã dài cho các ký hiếm, giúp giảm độ dài mã trung bình. Trong từ "BANANA", A xuất hiện nhiều nhất và nhận được mã ngắn nhất.
- Cả hai đều không mất mát: bộ giải mã tái tạo lại byte theo byte dữ liệu gốc.
Mã Huffman giảm kích thước bằng cách:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Huffman gán mã ngắn nhất cho các ký hiệu xuất hiện thường xuyên nhất, làm giảm độ dài mã trung bình.
Ghép mỗi phương pháp nén không mất dữ liệu với cách hoạt động của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Cả ba đều là nén không mất dữ liệu: bộ giải mã tái tạo lại byte gốc từng byte.
Các phương pháp mất mát
- Hình ảnh (JPEG): chi tiết tinh tế và sự khác biệt màu sắc mà mắt người khó nhận ra bị loại bỏ.
- Âm thanh (MP3, AAC): các tần số âm thanh mà tai nghe kém nhạy cảm bị loại bỏ, cùng với những âm thanh nhỏ bị che lấp bởi âm thanh lớn hơn ở cùng thời điểm.
- Video: nén không gian hoạt động bên trong mỗi khung hình, tương tự như JPEG, và nén thời gian lưu trữ hầu hết các khung hình chỉ là sự khác biệt so với khung hình trước, vì các khung hình liên tiếp gần như giống hệt nhau.
Nén theo thời gian của video hoạt động bằng cách:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Nén theo thời gian lưu trữ sự khác biệt của từng khung hình so với khung trước, vì phần lớn hình ảnh giữ nguyên giữa các khung. (Nén không gian xử lý chi tiết trong cùng một khung.)
Ví dụ minh họa: cách từng loại file được nén
- File văn bản: mã hóa từ điển và Huffman biến các từ lặp lại và ký tự thường gặp thành mã ngắn. File này bắt buộc phải giữ nguyên không mất mát, vì chỉ một ký tự bị thay đổi cũng làm thay đổi ý nghĩa.
- Ảnh bitmap: RLE cho các chuỗi điểm ảnh giống nhau trong biểu tượng và sơ đồ; JPEG mất mát cho ảnh chụp; hoặc giảm độ sâu màu hoặc độ phân giải, điều này cũng là nén mất mát.
- Đồ họa vector: danh sách vẽ đã nhỏ rồi. Xóa các đối tượng vẽ không cần thiết, lưu tọa độ với ít chữ số thập phân hơn, hoặc áp dụng phương pháp không mất mát như ZIP cho file.
- File âm thanh: MP3 hoặc AAC mất mát loại bỏ những gì tai không thể nghe thấy; giảm tốc độ lấy mẫu hoặc độ phân giải cũng là mất mát; định dạng không mất mát giữ lại mọi mẫu nhưng thu nhỏ ít hơn nhiều.
Làm thế nào để giảm dung lượng tập tin đồ họa vector? Chọn tất cả các đáp án đúng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Một tập tin vector là danh sách vẽ, không phải điểm ảnh, nên không có độ sâu màu. Độ sâu màu thuộc về bitmap.
Tại sao phát trực tuyến phải là mất mát
- Video HD thô là gigabyte mỗi phút, trong khi kết nối gia đình chỉ truyền vài megabit mỗi giây.
- Nén không mất mát cho video đạt được tỷ lệ khoảng hai lần, chưa đủ nhiều, nên hình ảnh sẽ liên tục dừng lại để đệm.
- Nén mất mát đạt được tỷ lệ trăm lần hoặc hơn bằng cách loại bỏ chi tiết mà người xem không nhận ra ở tốc độ bình thường. Lý do phải nêu rõ băng thông và tốc độ dữ liệu, chứ không chỉ nói "nó nhỏ hơn".
Tại sao phát trực tuyến video thời gian thực lại sử dụng nén mất dữ liệu?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Video HD thô là hàng gigabyte mỗi phút; chỉ có nén mất dữ liệu mới thu nhỏ đủ để phát trực tuyến thời gian thực mà không bị giật.
Điểm số dễ mất
- Không mất mát có nghĩa là dữ liệu gốc được khôi phục chính xác; mất mát có nghĩa là nó không thể được khôi phục. Câu "Mất mát làm giảm chất lượng" chưa nắm được vấn đề, vì dữ liệu đã biến mất mãi mãi.
- RLE có thể làm cho file nhiễu lớn hơn. Hãy chỉ ra nơi nó hoạt động và nơi không hoạt động.
- Nén video là không gian và thời gian; nén thời gian lưu trữ sự khác biệt giữa các khung hình.
- Một câu trả lời "justified" (có căn cứ) gắn phương pháp với việc sử dụng của file: độ chính xác cho sổ sách và ảnh y khoa, kích thước cho phát trực tuyến và thư mục điện thoại.
Bạn đã nắm vững
- Nén tiết kiệm bộ nhớ và băng thông; không mất mát khôi phục lại dữ liệu gốc chính xác, mất mát loại bỏ dữ liệu vĩnh viễn
- Các phương pháp không mất mát: RLE (một giá trị và số lượng, tốt cho chuỗi, xấu cho nhiễu), mã hóa từ điển (chuỗi lặp lại thành chỉ mục ngắn), mã hóa Huffman (mã ngắn cho ký hiệu thường gặp)
- Các phương pháp mất mát loại bỏ những gì mắt hoặc tai bỏ sót; video thêm không gian trong khung hình và thời gian giữa các khung hình
- Justify (căn cứ) từ việc sử dụng: dữ liệu chính xác nghĩa là không mất mát, băng thông giới hạn cho phát trực tuyến nghĩa là mất mát