Cụ thể, chương trình nào ở ngoài đó và tỷ lệ nén cao nhất là gì? Tôi đã thử dùng Google, nhưng có vẻ như trải nghiệm sẽ vượt qua kết quả tìm kiếm, vì vậy tôi hỏi.Nén tệp tốt nhất của dữ liệu nhị phân ngẫu nhiên mà bạn có thể đạt được là gì?
Nếu kích thước tệp có thể được chỉ định chính xác cho bit, đối với bất kỳ kích thước tệp N, sẽ có chính xác 2^(N + 1) -1 tệp có thể có của N bit hoặc nhỏ hơn. Để tệp có kích thước X được ánh xạ tới một số kích thước nhỏ hơn Y, một số tệp có kích thước Y hoặc nhỏ hơn phải được ánh xạ tới tệp có kích thước X hoặc lớn hơn. Cách duy nhất nén lossless có thể hoạt động là nếu một số tập tin có thể được xác định là có thể xảy ra nhiều hơn các tệp khác; trong trường hợp đó, các tệp có khả năng sẽ bị thu hẹp và các tệp không chắc sẽ phát triển. Một ví dụ đơn giản, giả sử rằng người ta muốn lưu trữ losslessly một tập tin trong đó các bit là ngẫu nhiên và độc lập, nhưng thay vì 50% của các bit được thiết lập, chỉ có 33% là. Người ta có thể nén một tệp như vậy bằng cách lấy từng cặp bit và ghi "0" nếu cả hai bit đều rõ ràng, "10" nếu bit đầu tiên được đặt và bit thứ hai không phải là "110" nếu thứ hai được đặt và giá trị đầu tiên không hoặc "111" nếu cả hai bit được đặt. Hiệu ứng sẽ là mỗi cặp bit sẽ trở thành một bit 44% thời gian, hai bit 22% thời gian, và ba bit 33% thời gian. Trong khi một số chuỗi dữ liệu sẽ phát triển, các chuỗi khác sẽ thu hẹp; các cặp co lại sẽ - nếu phân bố xác suất như mong đợi - nhiều hơn số lượng phát triển (4/9 tệp sẽ bị thu hẹp một chút, 2/9 sẽ giữ nguyên, và 3/9 sẽ tăng, vì vậy các cặp sẽ bật trung bình co lại 1/9 bit, và các tệp tin trung bình sẽ thu nhỏ 1/18 [vì hình 1/9 là bit trên mỗi cặp]). Lưu ý rằng nếu các bit thực sự có phân phối 50%, thì chỉ 25% các cặp sẽ trở thành một bit, 25% sẽ ở lại hai bit và 50% sẽ trở thành ba bit. Do đó, 25% bit sẽ thu nhỏ và 50% sẽ tăng, vì vậy các cặp trung bình sẽ tăng 25% và các tệp sẽ tăng 12,5%. Điểm hòa vốn sẽ chiếm khoảng 38,2% số bit được thiết lập (hai trừ đi giá trị trung bình của vàng), sẽ mang lại 38,2% các cặp bit co lại và cùng tỷ lệ phần trăm tăng lên.
Tôi lấy nó là một lời giải thích đơn giản về sự phức tạp Kolmogorov. Không tệ. – DieLaughing
Giải thích chi tiết hơn sẽ có xu hướng làm cho mắt của nhiều độc giả sáng hơn. Mặc dù cách tiếp cận của nén hai bit tại một thời điểm để 1-3 bit đầu ra là đơn giản, tôi nghĩ rằng nó truyền tải khá tốt bản chất của thách thức. Nén 1-3 bit đầu vào thành 2 bit đầu ra sẽ là một cách tiếp cận khác, ví dụ: (000, 001, 01, 1) nhưng tính toán xác suất liên quan sẽ khó hơn. – supercat
Giải thích tuyệt vời về "tại sao" nén hoạt động. Tôi đã luôn luôn là một nạn nhân của kính mắt. +1 –
Không có thuật toán nén tốt nhất trên toàn cầu. Các thuật toán khác nhau đã được phát minh để xử lý các dữ liệu khác nhau.
Ví dụ, nén JPEG cho phép bạn nén hình ảnh khá nhiều bởi vì nó không quan trọng quá nhiều nếu màu đỏ trong hình ảnh của bạn là 0xFF hoặc 0xFE (thường). Tuy nhiên, nếu bạn cố gắng nén tài liệu văn bản, những thay đổi như thế này sẽ là thảm họa.
Ngoài ra, ngay cả giữa hai thuật toán nén được thiết kế để hoạt động với cùng một loại dữ liệu, kết quả của bạn sẽ khác nhau tùy thuộc vào dữ liệu của bạn.
Ví dụ: Đôi khi sử dụng tarball gzip nhỏ hơn và đôi khi sử dụng bzip tarball nhỏ hơn.
Cuối cùng, đối với dữ liệu thực sự ngẫu nhiên có độ dài đủ, dữ liệu của bạn có thể sẽ có cùng kích thước với (hoặc thậm chí lớn hơn) dữ liệu gốc.
Phải có một thuật toán nén tốt nhất trên toàn cầu. Tôi nghĩ rằng logic sẽ đòi hỏi đó là sự thật, trừ khi có nhiều thuật toán của các tỷ lệ nén bằng nhau được gắn cho tốt nhất. – DieLaughing
Có rất nhiều phương pháp có thể được coi là "gắn" cho tỷ lệ nén tốt nhất cho một loại dữ liệu cụ thể, cũng như nhiều phương pháp chuyên biệt cho một loại dữ liệu cụ thể mang lại hiệu suất tốt hơn cho các loại dữ liệu này phương pháp (âm thanh, hình ảnh, phim, v.v.). Bạn cần phải xác định những giả định nào bạn có thể thực hiện về dữ liệu của mình, với nhiều giả định hơn (nhưng không phải luôn luôn) dẫn đến tỷ lệ nén cao hơn cho loại dữ liệu cụ thể đó. – helloworld922
Trình lưu trữ tệp 7z sử dụng LZMA (Thuật toán Mark Lempel Ziv) là thuật toán nén trẻ hiện có tỷ lệ nén tốt nhất (xem trang Linux Compression Comparison).
Một lợi thế cạnh tỷ lệ nén cao:
Điều này không trả lời được câu hỏi nào cả, vì LZMA là một coder từ điển, nó thực sự làm cho dữ liệu ngẫu nhiên lớn hơn, không nhỏ hơn! – jleahy
'dd if =/dev/urandom =/dev/stdout bs = 1024 count = 1024 | lzma -c - | wc -c' xuất ra 1048576 byte được sao chép, 1062936. Đó là mức tăng 1,3%. Nó sẽ thay đổi do ngẫu nhiên, nhưng bạn nên mong đợi các con số xung quanh đó. – jleahy
Có bằng chứng khoa học hoặc toán học thực tế nào không thể nén dữ liệu ngẫu nhiên? Với tôi nghe có vẻ rất kỳ quặc khi bạn có thể xem xét một khối byte có thể bằng một phép nhân đơn giản hoặc một tổng của biểu mẫu (x^y) + z hoặc (x^y) - z sẽ làm việc cho một số con số chắc chắn? –
dữ liệu Thực sự ngẫu nhiên không thể được nén. ;-) Câu trả lời hữu ích hơn là dài hơn: các thuộc tính của dữ liệu được nén là gì? (âm thanh, hình ảnh, video, tệp nhị phân có thể thực thi, v.v.) Bạn có thể chịu đựng mất thông tin không? – Throwback1986
Ví dụ, kiểu nén lzw (tức là gif) không làm giảm kích cỡ ảnh cũng như nén jpeg. Mặt khác, nén hình ảnh "nhân tạo" jpeg, giống như một dải truyện tranh, sẽ dẫn đến sự mất chất lượng đáng chú ý. – Throwback1986
Dữ liệu nhị phân ngẫu nhiên là khá rõ ràng định dạng nào. – DieLaughing