Bản gốc
Tiết kiệm

Phương pháp

Thêm thông tin về nén dữ liệu

Trình minh họa nén dữ liệu

Làm sao một tệp có thể nhỏ đi mà không mất một chữ cái nào? Bằng cách nhận ra rằng nó tự lặp lại. Hãy dán một văn bản hoặc chọn một ví dụ và xem ba phương pháp kinh điển hoạt động: LZ77 trỏ ngược về văn bản đã xuất hiện trước, LZW vừa đọc vừa học một từ điển các chuỗi, còn mã hóa độ dài loạt đếm các loạt ký tự giống nhau. Mỗi phương pháp đều được giải nén lại để cho thấy không có gì bị mất, và một biểu đồ so sánh chúng với ZIP và với giới hạn entropy. Gõ hoặc dán một văn bản, hoặc chọn một ví dụ, rồi chọn một phương pháp. LZ77 thay các đoạn lặp bằng tham chiếu đến văn bản phía trước: hãy nhấp vào một phần được tô sáng để xem nó sao chép gì. LZW vừa đọc vừa xây dựng một từ điển các chuỗi và gửi đi số thứ tự của chúng. RLE ép gọn các loạt ký tự giống nhau. Biểu đồ so sánh mọi phương pháp với ZIP và với giới hạn entropy, và ứng dụng giải nén lại kết quả để kiểm tra rằng không có gì bị mất.

Cách nó hoạt động

  1. Gõ hoặc dán một văn bản, hoặc chọn một ví dụ: 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.
  2. Chọn LZ77, LZW hoặc RLE. Với LZ77, hãy đặt khoảng cách tối đa mà nó được nhìn lại, và nhấp vào một tham chiếu được tô sáng để xem đoạn văn bản trước đó mà nó sao chép.
  3. So sánh kích thước trong các ô và trên biểu đồ với ZIP và với giới hạn entropy; phần kiểm tra bên dưới văn bản xác nhận rằng giải nén cho lại đúng bản gốc.

Sự lặp lại là chìa khóa

Nén không mất dữ liệu hiệu quả vì dữ liệu thực tế tự lặp lại. LZ77 giữ một cửa sổ chứa phần văn bản vừa đọc; mỗi khi các ký tự tiếp theo đã từng xuất hiện trong cửa sổ đó, nó ghi một tham chiếu ngắn, lùi lại chừng này và sao chép chừng ấy ký tự, thay cho chính các ký tự. Một tham chiếu tốn một số bit cố định dù đoạn sao chép dài bao nhiêu, nên các đoạn lặp dài và thường xuyên tiết kiệm nhiều nhất. LZW đạt cùng hiệu quả theo cách khác: nó xây dựng một từ điển gồm mọi chuỗi mới gặp và từ đó trở đi gửi số thứ tự của chuỗi.

Vì sao có dữ liệu không thể nhỏ đi

Một phương pháp làm một số tệp nhỏ đi thì nhất định phải làm những tệp khác lớn lên: số tệp ngắn ít hơn số tệp dài, nên không thể tất cả đều ngắn đi. Nén thắng thế với dữ liệu có quy luật, như văn bản, bảng và hình ảnh đơn giản, và thua với dữ liệu không có quy luật. Chữ cái ngẫu nhiên, dữ liệu đã mã hóa và các tệp đã được nén không cho các phương pháp thứ gì để trỏ ngược về, và đầu ra lớn bằng đầu vào, hoặc lớn hơn. Mã hóa độ dài loạt cho thấy điều này rõ nhất: với văn bản không có loạt nào, nó làm kích thước tăng gấp đôi.

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

Nén không mất dữ liệu và nén mất dữ liệu khác nhau thế nào?

Nén không mất dữ liệu cho lại chính xác bản gốc, từng bit một; nó cần thiết cho văn bản, chương trình và dữ liệu, và trình minh họa này chỉ trình bày các phương pháp không mất dữ liệu. Nén mất dữ liệu, như trong ảnh JPEG, nhạc MP3 và video, bỏ đi những chi tiết mà người ta hầu như không nhận ra và tạo ra các tệp nhỏ hơn nhiều, nhưng không thể khôi phục bản gốc.

ZIP nén tệp như thế nào?

ZIP và gzip dùng deflate, trước hết chạy LZ77 với cửa sổ 32 KB, rồi ghi các ký tự nguyên văn (literal) và tham chiếu bằng mã Huffman: mã ngắn cho các giá trị thường gặp và mã dài cho các giá trị hiếm. Bước thứ hai đó là lý do ZIP thường tốt hơn LZ77 thuần túy được trình bày ở đây, vốn tốn một số bit cố định cho mỗi token.

LZ77 có thể xuống dưới entropy không?

Entropy hiển thị ở đây đếm từng ký tự một, không xét ngữ cảnh. LZ77 và LZW dùng ngữ cảnh, vì một tham chiếu sao chép cả một đoạn văn bản trước đó, nên với văn bản lặp nhiều chúng có thể vượt xa con số đó. Chúng không bao giờ vượt qua được entropy thực sự của nguồn, vốn tính đến toàn bộ ngữ cảnh.

Vì sao kích thước khác với một tệp ZIP thật?

Trình minh họa chỉ đếm các bit của dữ liệu đã mã hóa. Một tệp ZIP thật còn thêm phần đầu (header), tên tệp, mã kiểm tra (checksum) và các bảng Huffman, khiến những tệp rất nhỏ lớn lên thay vì nhỏ đi.

Văn bản của tôi có được gửi đi đâu không?

Không. Mọi phương pháp, kể cả phép so sánh với ZIP, đều chạy trong trình duyệt của bạn, và văn bản của bạn nằm trong bộ nhớ cục bộ của trình duyệt này.

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.

Tới trình chỉnh sửa