Thuật toán nén tốt nhất cho các tệp 4 KB nhỏ là gì?

Question

Tôi đang cố nén các gói TCP mỗi gói có kích thước khoảng 4   KB. Các gói tin có thể chứa bất kỳ byte nào (từ 0 đến 255). Tất cả các điểm chuẩn trên các thuật toán nén mà tôi tìm thấy dựa trên các tệp lớn hơn. Tôi không tìm thấy bất cứ điều gì so sánh tỷ lệ nén của các thuật toán khác nhau trên các tệp nhỏ, đó là những gì tôi cần. Tôi cần nó để được mã nguồn mở để nó có thể được thực hiện trên C + +, vì vậy không có RAR ví dụ. Thuật toán nào có thể được khuyến nghị cho các tệp nhỏ có dung lượng khoảng 4 kilobyte? LZMA? HACC? ZIP? gzip? bzip2?

Answer 1

Chọn thuật toán nhanh nhất, vì bạn có thể quan tâm đến việc thực hiện điều này trong thời gian thực. Nói chung cho các khối dữ liệu nhỏ hơn, các thuật toán nén về cùng (cung cấp hoặc mất một vài byte) chủ yếu là do các thuật toán cần phải truyền từ điển hoặc cây Huffman ngoài tải trọng.

Tôi khuyên bạn nên Deflate (được sử dụng bởi zlib và Zip) vì một số lý do. Thuật toán khá nhanh, được kiểm tra tốt, BSD được cấp phép, và là nén duy nhất được yêu cầu để được Zip hỗ trợ (theo thông tin Appzip). Ngoài những điều cơ bản, khi nó xác định rằng nén lớn hơn kích thước giải nén, có chế độ STORE chỉ thêm 5 byte cho mỗi khối dữ liệu (khối tối đa là 64k byte). Ngoài chế độ STORE, Deflate hỗ trợ hai loại bảng Huffman khác nhau (hoặc từ điển): động và cố định. Một bảng động có nghĩa là cây Huffman được truyền như là một phần của dữ liệu nén và là linh hoạt nhất (đối với các loại dữ liệu phi thương mại khác nhau). Ưu điểm của một bảng cố định là bảng được biết đến bởi tất cả các bộ giải mã và do đó không cần phải được chứa trong luồng nén. Mã giải nén (hoặc Inflate) là tương đối dễ dàng. Tôi đã viết cả hai phiên bản Java và Javascript dựa trực tiếp từ zlib và chúng hoạt động khá tốt.

Các thuật toán nén khác được đề cập có giá trị của chúng. Tôi thích Deflate vì hiệu suất thời gian chạy của nó trên cả hai bước nén và đặc biệt là trong bước giải nén.

Một điểm làm rõ: Zip không phải là loại nén, nó là vùng chứa. Để thực hiện nén gói, tôi sẽ bỏ qua Zip và chỉ sử dụng API deflate/inflate do zlib cung cấp.

Answer 2

Tất cả các thuật toán đó đều hợp lý để thử. Như bạn nói, chúng không được tối ưu hóa cho các tệp nhỏ, nhưng bước tiếp theo của bạn là chỉ cần thử chúng. Nó có thể sẽ chỉ mất 10 phút để thử nghiệm nén một số gói điển hình và xem những gì kích thước kết quả. (Hãy thử các cờ nén khác nhau). Từ các tệp kết quả, bạn có thể chọn công cụ nào hoạt động tốt nhất.

Các ứng cử viên mà bạn liệt kê đều là những cố gắng tốt đầu tiên. Bạn cũng có thể thử bzip2.

Đôi khi đơn giản "thử tất cả" là một giải pháp tốt khi các bài kiểm tra rất dễ làm .. suy nghĩ quá nhiều đôi khi làm chậm bạn xuống.

Answer 3

Tôi không nghĩ kích thước tệp quan trọng - nếu tôi nhớ chính xác, LZW trong GIF sẽ đặt lại từ điển mỗi 4K.

Answer 4

ZLIB sẽ ổn. Nó được sử dụng trong MCCP.

Tuy nhiên, nếu bạn thực sự cần nén tốt, tôi sẽ làm một phân tích về mô hình phổ biến và bao gồm một cuốn từ điển của họ trên máy tính, mà có thể mang lại mức độ cao hơn của nén.

Answer 5

Tôi đã làm những gì Arno Setagaya gợi ý trong câu trả lời của mình: làm một số xét nghiệm mẫu và so sánh kết quả.

Thử nghiệm nén được thực hiện bằng 5 tệp, mỗi tệp có kích thước 4096 byte. Mỗi byte bên trong 5 tệp này được tạo ngẫu nhiên.

QUAN TRỌNG: Trong cuộc sống thực, dữ liệu sẽ không có khả năng là tất cả ngẫu nhiên, nhưng sẽ có xu hướng có yên tĩnh một chút byte lặp đi lặp lại. Vì vậy, trong ứng dụng thực tế cuộc sống nén sẽ có xu hướng tốt hơn một chút sau đó kết quả sau.

LƯU Ý: Mỗi phòng trong số 5 file được nén bởi chính nó (ví dụ: không cùng với 4 tác phẩm khác, mà sẽ cho kết quả nén tốt hơn). Trong các kết quả sau, tôi chỉ sử dụng tổng kích thước của 5 tệp với nhau để đơn giản.

Tôi đã bao gồm RAR chỉ vì lý do so sánh, mặc dù nó không phải là nguồn mở.

Kết quả: (từ tốt nhất để tồi tệ nhất)

LZOP: 20775/20480 * 100 = 101,44% kích thước ban

RAR: 20825/20480 * 100 = 101,68% kích thước ban

LZMA: 20827/20480 * 100 = 101,69% kích thước ban

Zip: 21020/20480 * 100 = 102,64% kích thước ban

bzip: 22899/20480 * 100 = 111.81% kích thước gốc

Kết luận: Để tôi ngạc nhiên TẤT CẢ các thuật toán được thử nghiệm đã tạo ra kích thước lớn hơn thì bản gốc !!! Tôi đoán chúng chỉ tốt cho việc nén các tệp lớn hơn hoặc các tệp có nhiều byte lặp lại (không phải dữ liệu ngẫu nhiên như ở trên). Vì vậy, tôi sẽ không sử dụng bất kỳ loại nén nào trên các gói TCP của tôi. Có lẽ thông tin này sẽ hữu ích cho những người khác xem xét việc nén các mẩu dữ liệu nhỏ.

EDIT: Tôi quên đề cập đến rằng tôi đã sử dụng tùy chọn mặc định (cờ) cho mỗi thuật toán.

Answer 6

Tôi đã may mắn sử dụng thư viện nén zlib trực tiếp và không sử dụng bất kỳ vùng chứa tệp nào. ZIP, RAR, có phí để lưu trữ những thứ như tên tệp. Tôi đã nhìn thấy nén theo cách này mang lại kết quả tích cực (nén ít hơn kích thước ban đầu) cho các gói tin xuống đến 200 byte.

Answer 7

Bạn có thể thử delta compression. Nén sẽ phụ thuộc vào dữ liệu của bạn. Nếu bạn có bất kỳ đóng gói nào trên tải trọng, thì bạn có thể nén các tiêu đề.

Answer 8

Nếu bạn muốn "nén gói TCP", bạn có thể xem xét sử dụng kỹ thuật chuẩn RFC.

• RFC1978 PPP Predictor nén Nghị định thư
• RFC2394 IP Payload Compression Sử dụng DEFLATE
• RFC2395 IP Payload Compression Sử dụng LZS
• RFC3173 IP Payload Compression Protocol (IPComp)
• RFC3051 IP Payload Compression Sử dụng ITU- TV.44 gói Phương pháp
• RFC5172 đàm phán cho IPv6 Datagram Compression Sử dụng IPv6 Control Protocol
• RFC5112 Các Presence-cụ thể từ điển tĩnh cho hiệu Compression (Sigcomp) Format
• RFC3284 Các VCDIFF Generic Differencing và nén dữ liệu
• RFC2118 Microsoft Point Giao thức nén -To-Point (MPPC)

Có thể có các RFC liên quan khác mà tôi đã bỏ qua.

Answer 9

Bạn có thể thử nghiệm bicom. Thuật toán này bị cấm sử dụng cho mục đích thương mại. Nếu bạn muốn sử dụng chuyên nghiệp hoặc thương mại, hãy xem "thuật toán mã hóa dải ô".