Tôi có thể tìm thuật toán nén không mất dữ liệu ở đâu, tạo ra kết quả đầu ra không có đầu trang?

Question

Có ai trong số các bạn biết một thuật toán nén không mất dữ liệu, thuật toán này tạo ra các đầu ra không đầu không? Ví dụ không lưu trữ cây huffman được sử dụng để nén nó? Tôi không nói về cây huffman mã hóa cứng, nhưng tôi muốn biết nếu có bất kỳ thuật toán có thể nén và giải nén đầu vào mà không lưu trữ một số siêu dữ liệu trong đầu ra của nó. Hay điều này thậm chí về mặt lý thuyết là không thể?

Answer 1

Adaptive Huffman coding thực hiện chính xác điều đó. Nói chung, thuật ngữ adaptive coding được sử dụng để mô tả entropy codes với thuộc tính này. Một số dictionary codes cũng có thuộc tính này, ví dụ: run-length encoding (RLE) và Lempel-Ziv-Welch (LZW).

Answer 2

Run Length Encoding sẽ là một ví dụ

Answer 3

Tất nhiên nó là posible. Trong số những người khác, gia đình máy nén LZ không cần phải xuất ra bất cứ thứ gì ngoài dữ liệu nén, vì từ điển được xây dựng trên mạng dưới dạng tiến trình nén (hoặc giải nén). Bạn có nhiều triển khai tham chiếu cho các thuật toán loại LZ đó. Ví dụ: LZMA, thành phần của 7zip.

Answer 4

lzo lò xo cần lưu ý. nó được sử dụng trong OpenVPN, với kết quả tuyệt vời

Answer 5

Tại sao bạn tìm kiếm thuật toán nén với đầu ra nén không đầu không?

Có lẽ (a) bạn có một hệ thống như điện thoại 2 chiều cần nén/giải nén trực tuyến độ trễ thấp. Danh mục mã hóa thích ứng của thuật toán nén được đề cập bởi Zach Scrivena và họ LZ của dictionary compression thuật toán được đề cập bởi Diego Sevilla và Javier là tuyệt vời cho loại ứng dụng này. Triển khai thực tế các thuật toán này thường là do có một hoặc hai byte siêu dữ liệu ngay từ đầu (làm cho chúng vô ích cho (b) ứng dụng), nhưng điều đó có ít hoặc không ảnh hưởng đến độ trễ.

Có lẽ (b) bạn chủ yếu quan tâm đến mật mã, và bạn nghe rằng việc nén trước mã hóa cung cấp một số thuộc tính bảo mật được cải thiện, miễn là văn bản nén không có tiêu đề siêu dữ liệu cố định "giường cũi". Thuật toán mã hóa hiện đại không phải (như chúng tôi biết) dễ bị tổn thương với "nôi" như vậy, nhưng nếu bạn hoang tưởng, bạn có thể quan tâm đến việc nén nén sinh học (a, b, c, v.v.). Không thể phát hiện lỗi khi truyền (bit lật, bit được chèn, bit đã xóa, vv) khi người nhận nhận được kết quả nén như vậy (làm cho các thuật toán này không đặc biệt hữu ích cho (a) ứng dụng).

Có lẽ (c) bạn quan tâm đến việc nén tiêu đề vì một số lý do khác. Âm thanh hấp dẫn - lý do đó là gì?