Tại sao dữ liệu được mã hóa base64 nén quá tệ?

Question

Gần đây tôi đã nén một số tệp và tôi nhận thấy rằng dữ liệu được mã hóa base64 dường như thực sự bị nén. Dưới đây là một ví dụ:

• gốc file: 429,7 MiB
• nén qua xz -9:
  13,2 MiB/429,7 MiB = 0,0314,9 MiB/s1:28
• base64 nó và nén qua xz -9:
  26,7 MiB/580,4 MiB = 0,0462,6 MiB/s3:47
• base64 tệp nén xz gốc:
  17,8 MiB trong thời gian hầu như không có = dự kiến ​​1.33x gia tăng kích thước

Vì vậy, những gì có thể được quan sát là:

• xz nén ☺ thực sự tốt
• dữ liệu base64 mã hóa không nén tốt, nó lớn hơn 2 lần so với tệp nén chưa được mã hóa
• base64-then-compress là tồi tệ hơn và chậm hơn đáng kể so với comp ress-then-base64

Đây có thể là gì? Base64 là một thuật toán không thể đảo ngược, có thể đảo ngược, tại sao nó ảnh hưởng đến nén quá nhiều? (Tôi đã thử với gzip là tốt, với kết quả tương tự).

Tôi biết điều này không có ý nghĩa đối với base64-then-compress một tệp, nhưng phần lớn thời gian không có quyền kiểm soát tệp nhập và tôi đã nghĩ rằng vì mật độ thông tin thực tế (hoặc bất cứ điều gì nó được gọi) của một tập tin mã hóa base64 sẽ gần giống với phiên bản không mã hóa, và do đó được nén tương tự.

Answer 1

Nén nhất thiết là một thao tác hoạt động trên nhiều bit. Không thể đạt được trong cố gắng để nén một cá nhân "0" và "1". Mặc dù vậy, nén thường hoạt động trên một tập hợp các bit giới hạn tại một thời điểm. Thuật toán LZMA trong xz sẽ không xem xét tất cả 3,6 tỷ bit cùng một lúc. Nó xem xét các chuỗi nhỏ hơn nhiều (< 273 byte).

Bây giờ hãy xem mã hóa cơ sở 64 làm gì: Nó thay thế từ 3 byte (24 bit) bằng từ 4 byte, chỉ sử dụng 64 trong số 256 giá trị có thể. Điều này mang lại cho bạn sự tăng trưởng x1.33.

Bây giờ nó khá rõ ràng rằng sự tăng trưởng này phải làm cho một số chất nền phát triển vượt quá kích thước chuỗi con tối đa của bộ mã hóa. Điều này khiến chúng không còn được nén dưới dạng một chuỗi con duy nhất, nhưng thực sự là hai phân đoạn riêng biệt.

Vì bạn có lô nén (97%), bạn dường như có tình huống mà các đầu vào rất dài được nén toàn bộ. điều này có nghĩa rằng bạn cũng sẽ có nhiều nền tảng được base-64 mở rộng qua độ dài tối đa mà bộ mã hóa có thể xử lý.

Answer 2

Hầu hết các thuật toán nén chung đều hoạt động với độ chi tiết một byte một byte.

Hãy xem xét các chuỗi sau:

"XXXXYYYYXXXXYYYY" 

• Một thuật toán Run-Length-Encoding sẽ nói: "đó là 4 'X', tiếp theo là 4 'Y', tiếp theo là 4 'X' , tiếp theo là 4 'Y' "
• Thuật toán Lempel-Ziv sẽ nói: " Đó là chuỗi 'XXXXYYYY', tiếp theo là cùng một chuỗi: vì vậy hãy thay thế chuỗi thứ hai bằng tham chiếu đến giá trị đầu tiên. "
• Thuật toán mã hóa Huffman sẽ cho biết: "Chỉ có 2 ký tự trong chuỗi đó, vì vậy tôi chỉ có thể sử dụng một bit cho mỗi biểu tượng".

Bây giờ, hãy mã hóa chuỗi của chúng tôi trong Base64. Dưới đây là những gì chúng tôi nhận được:

"WFhYWFlZWVlYWFhYWVlZWQ==" 

Tất cả các thuật toán hiện đang nói: "Loại lộn xộn đó là gì?". Và họ không có khả năng nén chuỗi đó rất tốt.

Như một lời nhắc nhở, Base64 về cơ bản hoạt động bằng cách mã hóa lại các nhóm 3 byte trong (0 ... 255) thành các nhóm 4 byte trong (0 ... 63):

Input bytes : aaaaaaaa bbbbbbbb cccccccc 
6-bit repacking: 00aaaaaa 00aabbbb 00bbbbcc 00cccccc 

Mỗi đầu ra byte sau đó được chuyển thành ký tự ASCII có thể in được. Theo quy ước, những nhân vật này là (ở đây với một dấu ấn mỗi 10 ký tự):

0   1   2   3   4   5   6 
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz/ 

Ví dụ, chuỗi ví dụ của chúng tôi bắt đầu với một nhóm ba byte bằng 0x58 trong hệ thập lục phân (mã ASCII của kí tự "X") . Hoặc ở dạng nhị phân: 01011000. Hãy áp dụng Base64 mã hóa:

Input bytes  : 0x58  0x58  0x58 
As binary  : 01011000 01011000 01011000 
6-bit repacking : 00010110 00000101 00100001 00011000 
As decimal  : 22  5  33  24 
Base64 characters: 'W'  'F'  'h'  'Y' 
Output bytes  : 0x57  0x46  0x68  0x59 

Về cơ bản, mô hình "3 lần so với 0x58 byte", mà là rõ ràng trong dòng dữ liệu ban đầu là không rõ ràng nữa trong dòng dữ liệu được mã hóa bởi vì chúng tôi đã chia các byte thành các gói 6 bit và ánh xạ chúng thành các byte mới mà bây giờ xuất hiện là ngẫu nhiên.

Hay nói cách khác: chúng tôi đã phá vỡ căn chỉnh byte ban đầu mà hầu hết các thuật toán nén dựa vào.

Bất kể phương thức nén nào được sử dụng, nó thường có tác động nghiêm trọng đến hiệu suất thuật toán. Đó là lý do tại sao bạn nên luôn luôn nén đầu tiên và mã hóa thứ hai.

Điều này thậm chí còn đúng hơn cho mã hóa: nén trước, mã hóa thứ hai.

EDIT - Một lưu ý về LZMA

Như MSalters nhận thấy, LZMA - mà xz đang sử dụng - đang làm việc trên suối chút chứ không phải là con suối byte.

Tuy nhiên, thuật toán này cũng sẽ bị ảnh hưởng từ mã hóa Base64 theo một cách mà chủ yếu là phù hợp với mô tả trước đây của tôi:

Input bytes  : 0x58  0x58  0x58 
As binary  : 01011000 01011000 01011000 
(see above for the details of Base64 encoding) 
Output bytes  : 0x57  0x46  0x68  0x59 
As binary  : 01010111 01000110 01101000 01011001 

Thậm chí bằng cách làm việc ở cấp độ bit, nó dễ dàng hơn để nhận ra một mô hình trong chuỗi nhị phân đầu vào so với chuỗi nhị phân đầu ra.