Bzip: Lời ca cho một thuật toán nén bị lãng quên

Câu chuyện bắt đầu

Câu chuyện bắt đầu như thế này. ComputerCraft là một bản mod thêm lập trình vào Minecraft. Bạn viết mã Lua và nó được thực thi bởi một trình thông dịch riêng có quyền truy cập vào các API của thế giới game, và thế là bạn dành thời gian viết mã thay vì tận hưởng trò chơi. Các máy tính trong game có dung lượng đĩa hạn chế, và thư mục /nix của tôi đang phình to ngoài tầm kiểm soát, vì vậy tôi cần nén mã nguồn lại.

Lựa chọn lười biếng nhất là sử dụng LibDeflate, nhưng bộ giải nén của nó còn lớn hơn cả phần dung lượng tiết kiệm được từ việc nén và cũng vượt quá giới hạn cá nhân của tôi về việc sao chép mã. Vì vậy, câu hỏi đặt ra là: thuật toán nén nào ngắn nhất, đơn giản nhất và có tỷ lệ nén hiệu quả nhất?

Ban đầu, tôi nghĩ đây là một câu hỏi phức tạp với đầy rẫy sự đánh đổi, nhưng hóa ra câu trả lời lại rất rõ ràng. Câu trả lời của tôi là bzip, mặc dù thuật toán này đã bị chỉ trích nhiều lần và dần chìm vào quên lãng kể từ khi xz và zstd trở nên phổ biến.

So sánh ban đầu

Tôi đang nén một tệp 327 KB chứa mã Lua với một ít văn bản tiếng Anh trong các bình luận và tài liệu. Điều này rất quan trọng: bzip vượt trội với dữ liệu dạng văn bản hơn là dữ liệu nhị phân. Tuy nhiên, kết quả của tôi có thể được tái hiện trên các cơ sở mã khác, vì tỷ lệ phần trăm dường như không đổi trong cùng một loại dữ liệu.

Hãy so sánh một số bộ mã hóa nổi tiếng trên dữ liệu này:

• zopfli --i100: 75882
• zstd -22 --long --ultra: 69018
• xz -9: 67940
• brotli -Z: 67859 (biên dịch lại không có từ điển)
• lzip -9: 67651
• bzip2 -9: 63727
• bzip3: 61067

Các thuật toán họ bzip rõ ràng là người chiến thắng với một khoảng cách lớn. Nó thậm chí còn đánh bại lzip, dù tài liệu của lzip ghi rằng "'lzip -9' nén hầu hết các tệp tốt hơn bzip2" (tôi đoán mã nguồn không thuộc "hầu hết các tệp"). Làm thế nào nó đạt được điều này? Hóa ra, bzip không giống những thuật toán khác.

Khác biệt về thuật toán

Bạn thấy đấy, tất cả các thuật toán nén phổ biến khác về cơ bản đều giống nhau. Chúng đều dựa trên LZ77, một lược đồ nén có nguyên tắc là thay thế văn bản lặp lại bằng các liên kết ngắn đến các lần xuất hiện trước đó.

Sự khác biệt chính nằm ở cách các chuỗi ký tự và các tham chiếu ngược (backreferences) được mã hóa thành các luồng bit, và đây là một quá trình không hề tầm thường. Vì các liên kết có thể có độ lệch, độ dài và tần suất khác nhau tùy vị trí, một thuật toán tốt cần phải dự đoán và mã hóa các tham số này một cách ngắn gọn.

Nhưng bzip không sử dụng LZ77. bzip sử dụng Biến đổi Burrows-Wheeler (BWT), một phương pháp sắp xếp lại các ký tự trong văn bản để nhóm chúng theo ngữ cảnh. Vì vậy, thay vì dự đoán các token dựa trên các lần xuất hiện tương tự trước đó, bạn chỉ cần nhìn vào một vài ký tự cuối cùng. Và đáng ngạc nhiên là, với thứ tự BWT, bạn thậm chí không cần lưu trữ vị trí xuất phát của mỗi ký tự!

Ví dụ, nếu từ hello được lặp lại nhiều lần trong văn bản, với LZ77, bạn sẽ cần tìm và chèn các tham chiếu mới ở mỗi lần xuất hiện. Nhưng với BWT, tất cả các ký tự theo sau chuỗi hell sẽ được nhóm lại với nhau, vì vậy bạn có thể sẽ có một chuỗi gồm nhiều chữ o liên tiếp, và tương tự với các ký tự khác, điều mà phương pháp mã hóa độ dài loạt (run-length encoding) đơn giản có thể xử lý dễ dàng.

BWT cũng có một số nhược điểm. Ví dụ, nếu bạn nối hai văn bản bằng các phương ngữ tiếng Anh khác nhau, chẳng hạn như sử dụng color và colour, BWT sẽ trộn lẫn các ký tự tiếp theo của colo theo một thứ tự không thể đoán trước và bạn sẽ phải mã hóa một chuỗi kỳ lạ gồm các chữ r và u, trong khi LZ77 sẽ ưu tiên lịch sử gần nhất. Bạn có thể khắc phục điều này bằng cách tách đầu vào theo định dạng, nhưng đối với dữ liệu nhất quán như mã nguồn, nó hoạt động hoàn hảo.

bzip2 và bzip3 đều dựa trên BWT và chủ yếu khác nhau ở cách đầu ra của BWT được nén. bzip2 sử dụng một biến thể của RLE, trong khi bzip3 cố gắng thông minh hơn. Tôi sẽ tập trung vào bzip2 vì lý do hiệu suất, nhưng hầu hết các kết luận cũng áp dụng cho bzip3.

Ưu điểm về Heuristics

Có một điều thú vị khác về BWT. Bạn có thể đã nhận thấy rằng tôi gọi bzip3 mà không truyền bất kỳ tham số nào như -9. Đó là vì bzip3 không nhận chúng. Thực tế, ngay cả việc gọi bzip2 với -9 cũng không có nhiều tác dụng.

Các phương pháp dựa trên LZ77 hỗ trợ các mức nén khác nhau vì việc tìm kiếm các lần xuất hiện trước đó tốn nhiều thời gian, và đôi khi việc sử dụng một chuỗi ký tự nguyên bản sẽ tốt hơn là một tham chiếu khó mã hóa, vì vậy có một số yếu tố "brute-force". Mặt khác, BWT hoàn toàn có tính xác định và không có các phương pháp phỏng đoán (heuristics).

Ngoài ra, không có sự tự do nào trong việc xác định cách mã hóa hiệu quả độ dài và độ lệch của các tham chiếu ngược, vì chúng không tồn tại. Chỉ có độ dài của các chuỗi lặp lại, nhưng đó chỉ là một con số duy nhất và nó nhỏ hơn các độ lệch thông thường.

Tất cả những điều đó để nói rằng: nếu bạn biết quy trình của bzip2 trông như thế nào, bạn có thể nhanh chóng đạt được tỷ lệ nén tương tự mà không cần tinh chỉnh và lo lắng về các trường hợp đặc biệt. Bộ mã hóa giống bzip2 tự chế, chưa được tối ưu hóa của tôi nén cùng một đầu vào xuống còn khoảng 67 KB – tốt hơn lzip và có nhiều hướng cải tiến rõ ràng.

Kích thước bộ giải nén

Đó là về định dạng nén, nhưng còn kích thước của bộ giải nén thì sao? Việc đo các tệp ELF là vô ích khi nhắm đến Lua, và các thư viện Lua như LibDeflate không tối ưu hóa kích thước mã cho các tệp lưu trữ tự giải nén. Do đó, tôi xin mạo muội ước tính cho mọi thứ trừ bzip2.

Một tệp thực thi tự giải nén không cần phải giải mã mọi loại tệp lưu trữ – chỉ cần một loại. Chúng ta có thể bỏ qua các bước kiểm tra tính toàn vẹn, tiêu đề, nhúng siêu dữ liệu vào mã và điều chỉnh định dạng để giải nén dễ dàng hơn. Vì vậy, tôi sẽ chỉ xem xét các vòng lặp giải nén cốt lõi.

gzip, zstd, xz, brotli, và lzip đều bắt đầu bằng việc thực hiện LZ77. Việc xử lý các token "sao chép" là một vòng lặp đơn giản không tốn nhiều mã. Chúng khác nhau ở cách các token đó được mã hóa thành bit:

• gzip: Áp dụng mã hóa Huffman. Trình phân tích mã Huffman có thể khoảng ~250 byte, cây bit ~700 byte, và phần mã kết nối ~500 byte. Tổng cộng khoảng 1.5 KB.
• xz: Mã hóa token theo từng bit thay vì coi chúng là các đơn vị nguyên tử, cho phép điều chỉnh xác suất một cách linh hoạt. Việc tránh các bảng mã là một lợi thế lớn, vì vậy hãy ước tính khoảng 1 KB.
• lzip: Rất giống với xz, chỉ thay đổi một chút về mã hóa token, vì vậy cũng ước tính là 1 KB.
• zstd: Sử dụng Finite State Entropy (FSE) thay vì Huffman. FSE đơn giản nhưng yêu cầu các bảng lớn, vì vậy ước tính khoảng 3 KB.
• brotli: Giữ lại mã hóa Huffman nhưng chuyển đổi giữa nhiều bảng Huffman tĩnh. Ước tính khoảng 2.2 KB.

Đối với các bộ giải nén bzip:

• bzip2: Nén đầu ra BWT bằng MTF + RLE + Huffman. Với 6 bảng Huffman mặc định, tổng cộng khoảng 1.9 KB.
• bzip3: Sử dụng mã hóa từng bit giống XZ. Ước tính khoảng 1.5 KB.

Vấn đề là: bằng cách bỏ qua khả năng tương thích với các định dạng tệp tiêu chuẩn, bộ giải nén có thể trở nên rất nhỏ. Tôi có thể sai ở một số con số này, nhưng nó có thể sẽ không thay đổi cục diện một cách đáng kể.

Các phương pháp kiểu bzip nằm ở giữa, nhưng điều đó có phần gây hiểu lầm. Mặc dù bzip2 thường sử dụng 6 bảng Huffman, tôi đã đạt được kết quả nén tốt chỉ với một bảng. Với chỉ một bảng, bộ giải nén kiểu bzip của tôi chỉ chiếm 1.5 KB, nhỏ hơn mọi thứ trừ xz và lzip, trong khi lại nhanh hơn đáng kể.