Trạng thái hiện tại của thuật toán nén chỉ văn bản là gì?

Question

Để vinh danh Hutter Prize, các thuật toán hàng đầu (và mô tả nhanh về từng thuật toán) cho nén văn bản là gì?

Lưu ý: Mục đích của câu hỏi này là để có được một mô tả về thuật toán nén, không phải của các chương trình nén.

Answer 1

Máy nén đẩy biên giới kết hợp các thuật toán cho kết quả điên rồ. thuật toán phổ biến bao gồm:

• Các Burrows-Wheeler Transform và here - ký tự ngẫu nhiên (hoặc khối chút khác) với một thuật toán dự đoán để tăng khối lặp đi lặp lại mà làm cho mã nguồn dễ dàng hơn để nén. Giải nén xảy ra như bình thường và kết quả là un-xáo trộn với biến đổi ngược lại. Lưu ý: BWT không thực sự nén bất cứ thứ gì. Nó chỉ làm cho nguồn dễ nén hơn.
• Prediction by Partial Matching (PPM) - sự phát triển của arithmetic coding nơi mô hình dự đoán (ngữ cảnh) được tạo bằng cách thu thập số liệu thống kê về nguồn so với sử dụng xác suất tĩnh. Mặc dù gốc của nó nằm trong mã hóa số học, kết quả có thể được biểu diễn bằng mã hóa Huffman hoặc từ điển cũng như mã hóa số học.
• Bối cảnh trộn - Mã hóa số học sử dụng ngữ cảnh tĩnh để dự đoán, PPM tự động chọn một ngữ cảnh đơn, Trộn ngữ cảnh sử dụng nhiều ngữ cảnh và cân nhắc kết quả của chúng. PAQ sử dụng trộn ngữ cảnh. Here's tổng quan cấp cao.
• Dynamic Markov Compression - liên quan đến PPM nhưng sử dụng ngữ cảnh cấp bit so với byte hoặc dài hơn. Ngoài ra, các thí sinh giải thưởng Hutter có thể thay thế văn bản chung với các mục nhỏ byte từ từ điển bên ngoài và phân biệt chữ hoa và chữ thường với ký hiệu đặc biệt so với sử dụng hai mục riêng biệt. Đó là lý do tại sao họ rất giỏi nén văn bản (đặc biệt là văn bản ASCII) và không có giá trị cho việc nén chung.

Maximum Compression là văn bản đẹp và trang web chuẩn nén chung. Matt Mahoney xuất bản một số khác benchmark. Mahoney có thể được quan tâm đặc biệt bởi vì nó liệt kê các thuật toán chính được sử dụng cho mỗi mục.

Answer 2

Luôn có lzip.

Tất cả đùa sang một bên:

• đâu khả năng tương thích là một mối quan tâm, PKZIP (DEFLATE thuật toán) vẫn thắng.
• bzip2 là sự thỏa hiệp tốt nhất giữa việc thưởng thức cơ sở cài đặt tương đối rộng và tỷ lệ nén khá tốt, nhưng yêu cầu một bộ lưu trữ riêng biệt.
• 7-Zip (LZMA thuật toán) nén rất tốt và có sẵn cho dưới LGPL. Tuy nhiên, rất ít hệ điều hành được hỗ trợ tích hợp sẵn.
• rzip là một biến thể của bzip2 mà theo ý kiến ​​của tôi xứng đáng được chú ý nhiều hơn. Nó có thể đặc biệt thú vị đối với các tệp nhật ký khổng lồ cần lưu trữ lâu dài. Nó cũng đòi hỏi một kho lưu trữ riêng biệt.

Answer 3

Nếu bạn muốn sử dụng PAQ làm chương trình, bạn có thể cài đặt gói zpaq trên các hệ thống dựa trên debian.Việc sử dụng (xem thêm man zpaq)

zpaq c archivename.zpaq file1 file2 file3 

nén là khoảng 1/10th quy mô một tập tin zip của. (1.9M so với 15M)