Giải thích nén dữ liệu

Mỗi trang web bạn tải, mỗi tệp ZIP và mỗi ảnh PNG đều đã được nén: được làm nhỏ đi mà không mất một bit nào, rồi được giải nén lại khi đến nơi. Các phương pháp đứng sau việc đó đơn giản đến bất ngờ. Chúng tìm những thứ lặp lại, và nói “giống như trước” thay vì nói lại lần nữa. Ý tưởng ấy đi xa đến đâu, và dừng lại ở đâu, là một trong những câu chuyện đẹp nhất của khoa học máy tính.

Một dòng văn bản trong đó các đoạn lặp lại được thay bằng mũi tên trỏ ngược về lần xuất hiện đầu tiên, bên cạnh các cột thể hiện kích thước gốc và kích thước sau khi nén
Một dòng văn bản trong đó các đoạn lặp lại được thay bằng mũi tên trỏ ngược về lần xuất hiện đầu tiên, bên cạnh các cột thể hiện kích thước gốc và kích thước sau khi nén

Không mất dữ liệu và mất dữ liệu

Có hai loại nén. Nén không mất dữ liệu cho lại chính xác bản gốc, điều thiết yếu với văn bản, chương trình, bảng tính và bất cứ thứ gì mà chỉ một bit sai cũng thành vấn đề. Nén mất dữ liệu, dùng cho ảnh, nhạc và video, bỏ đi những chi tiết mà con người khó cảm nhận và đạt kích thước nhỏ hơn nhiều, nhưng bản gốc thì mất vĩnh viễn. Trang này và trình minh họa nói về nén không mất dữ liệu, vốn hoạt động bằng cách tìm và loại bỏ độ dư thừa: những phần của dữ liệu lẽ ra có thể đoán trước được.

Mã hóa độ dài loạt

Phương pháp đơn giản nhất thay một loạt ký hiệu giống hệt nhau bằng một con số đếm và ký hiệu đó: mười hai điểm ảnh trắng trở thành 12W. Máy fax, các định dạng bitmap đời đầu và định dạng ảnh PCX đã dùng nó, vì các trang được quét và hình vẽ đơn giản đầy những loạt dài. Với văn bản thông thường nó vô dụng, thậm chí có hại: loạt rất hiếm, và việc ghi một con số đếm cho từng chữ cái làm kích thước tăng gấp đôi. Mã hóa độ dài loạt vẫn sống tiếp bên trong các phương pháp khác, cho những loạt số 0 còn lại sau một phép biến đổi đầu tiên.

LZ77: trỏ ngược về trước

Năm 1977, Abraham Lempel và Jacob Ziv, hai nhà nghiên cứu tại Technion ở Israel, công bố một phương pháp làm thay đổi cả lĩnh vực. Bộ mã hóa giữ một cửa sổ chứa phần văn bản vừa xử lý. Nếu các ký tự tiếp theo đã từng xuất hiện trong cửa sổ, nó ghi một cặp số: bản sao trước đó bắt đầu lùi lại bao xa và dài bao nhiêu. Nếu không, nó ghi chính ký tự đó. Bộ giải mã hoàn toàn không cần từ điển, chỉ cần phần văn bản nó đã dựng lại. Một tham chiếu thậm chí có thể chồng lên chính phần văn bản nó đang tạo ra, nên một loạt 100 chữ cái giống nhau chỉ là một chữ cái và một tham chiếu.

Abraham Lempel, người cùng Jacob Ziv tại Technion năm 1977 công bố phương pháp cửa sổ và tham chiếu nay gọi là LZ77.
Abraham Lempel, người cùng Jacob Ziv tại Technion năm 1977 công bố phương pháp cửa sổ và tham chiếu nay gọi là LZ77.

LZW: học một từ điển

Phương pháp thứ hai của Lempel và Ziv, LZ78, xây dựng một từ điển thay vì nhìn lại trong một cửa sổ. Bản cải tiến năm 1984 của Terry Welch, LZW, bắt đầu với cả 256 giá trị byte và ở mỗi bước gửi đi số thứ tự của chuỗi dài nhất mà nó đã biết, rồi thêm chuỗi đó cộng với ký tự tiếp theo làm một mục mới. Bộ giải mã dựng lại đúng từ điển ấy chỉ từ các con số. LZW nhanh và đơn giản, và được dùng trong lệnh compress của Unix, định dạng ảnh GIF và các tệp TIFF, cho đến khi các bằng sáng chế về nó gây ra một cuộc tranh chấp kéo dài vào thập niên 1990.

Deflate, ZIP và xa hơn nữa

Phương pháp deflate của Phil Katz, ra mắt cùng PKZIP 2 năm 1993, kết hợp LZ77 với mã hóa Huffman: sau khi tìm ra các đoạn lặp, nó gán mã bit ngắn nhất cho các ký tự nguyên văn, độ dài và khoảng cách phổ biến nhất. Deflate được dùng trong ZIP, gzip, ảnh PNG và việc nén trang web, và đó là phương pháp mà trình minh họa đo bằng bộ nén có sẵn của trình duyệt. Các phương pháp mới hơn như Zstandard, Brotli và xz dùng cửa sổ lớn hơn, cách so khớp thông minh hơn và mã hóa entropy chính xác hơn, và ép các tệp thông thường nhỏ thêm 10 đến 30%.

Vì sao không phải thứ gì cũng nhỏ đi được

Không phương pháp nào có thể làm mọi tệp nhỏ đi. Có 2ⁿ tệp dài n bit nhưng chỉ có 2ⁿ − 1 tệp ngắn hơn thế, nên nếu một phương pháp thu nhỏ tất cả, hai tệp sẽ trở thành giống nhau và không thể khôi phục cả hai: đó là nguyên lý chuồng bồ câu. Vì vậy mọi trình nén đều làm một số đầu vào lớn lên, thường là dữ liệu trông ngẫu nhiên như tệp đã mã hóa, tệp đã được nén và nhiễu. Đó cũng là một phép thử tính ngẫu nhiên: dữ liệu mà không trình nén nào thu nhỏ được thì trông ngẫu nhiên.

Giới hạn entropy

Năm 1948, Claude Shannon chứng minh rằng entropy của một nguồn là số bit trung bình mỗi ký hiệu nhỏ nhất có thể đối với bất kỳ mã không mất dữ liệu nào. Nếu đếm từng chữ cái, văn bản tiếng Anh có entropy khoảng 4 bit mỗi chữ cái, bằng một nửa 8 bit dùng để lưu nó. Các phương pháp dùng ngữ cảnh, như LZ77, xuống dưới con số tính theo từng chữ cái đó với văn bản lặp nhiều, vì một tham chiếu đại diện cho cả một đoạn cùng lúc. Các trình nén hiện đại tốt nhất, dự đoán mỗi chữ cái từ mọi thứ đứng trước nó, đưa tiếng Anh xuống dưới 2 bit mỗi chữ cái.

Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.
Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.

Tự khám phá

Mở trình minh họa nén dữ liệu để chạy LZ77, LZW và mã hóa độ dài loạt trên một đoạn văn, một bài hát có điệp khúc, một hàng điểm ảnh, một bảng dữ liệu, chữ cái ngẫu nhiên hoặc DNA, hay trên chính văn bản của bạn. Nhấp vào bất kỳ tham chiếu LZ77 nào để xem nó sao chép gì, xem từ điển LZW lớn dần, và so sánh mọi phương pháp với ZIP và giới hạn entropy.

Câu hỏi thường gặp

Tỷ lệ nén 3 : 1 có nghĩa là gì?

Nghĩa là bản gốc lớn gấp ba lần bản đã nén, nên tệp nén chiếm một phần ba dung lượng và tiết kiệm được hai phần ba. Văn bản thường đạt 2 : 1 đến 4 : 1 với ZIP; dữ liệu lặp lại nhiều, như các tệp nhật ký (log), thường đạt cao hơn nhiều.

Vì sao nén lại một tệp ZIP không có ích?

Lần nén đầu đã loại bỏ các đoạn lặp, và đầu ra của nó trông gần như ngẫu nhiên. Lần nén thứ hai không tìm thấy gì để trỏ ngược về và chỉ thêm phần chi phí phụ của riêng nó, nên tệp giữ nguyên kích thước hoặc lớn lên đôi chút.

Vì sao cửa sổ LZ77 lớn hơn thì tốt hơn?

Cửa sổ lớn hơn cho phép bộ mã hóa tìm thấy những đoạn lặp nằm xa hơn về phía trước, như một điệp khúc quay lại sau vài đoạn lời. Cái giá phải trả là mỗi khoảng cách cần nhiều bit hơn để ghi và việc tìm kiếm mất nhiều thời gian hơn, vì thế deflate dừng ở 32 KB còn các phương pháp mới hơn cho phép đến hàng megabyte.

Nén có giống mã hóa không?

Không. Nén làm dữ liệu nhỏ đi và ai cũng có thể đảo ngược nó; mã hóa làm dữ liệu không thể đọc được nếu không có khóa. Hai việc này thường được kết hợp, và khi đó dữ liệu phải được nén trước: dữ liệu đã mã hóa trông ngẫu nhiên và không thể nén được nữa.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở trình minh họa nén dữ liệu