Thuật toán nén hiệu quả cho các chuỗi văn bản ngắn

Question

Tôi đang tìm kiếm một thuật toán để nén chuỗi văn bản nhỏ: 50-1000 byte (ví dụ: URL). Thuật toán nào hoạt động tốt nhất cho điều này?

Answer 1

Check-out Smaz:

Smaz là một thư viện nén đơn giản phù hợp cho nén rất ngắn chuỗi.

Answer 2

Huffman coding thường hoạt động tốt cho việc này.

Answer 3

Nếu bạn đang nói về thực sự nén văn bản không chỉ rút ngắn sau đó Deflate/gzip (wrapper quanh gzip), zip hoạt động tốt cho các tệp và văn bản nhỏ hơn. Các thuật toán khác có hiệu quả cao đối với các tệp lớn hơn như bzip2, v.v.

Wikipedia có danh sách thời gian nén. (tìm so sánh hiệu quả)

Name  | Text   | Binaries  | Raw images 
-----------+--------------+---------------+------------- 
7-zip  | 19% in 18.8s | 27% in 59.6s | 50% in 36.4s 
bzip2  | 20% in 4.7s | 37% in 32.8s | 51% in 20.0s 
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s 
advzip  | 24% in 21.1s | 37% in 70.6s | 57& in 41.6s 
gzip  | 25% in 4.2s | 39% in 23.1s | 60% in 5.4s 
zip  | 25% in 4.3s | 39% in 23.3s | 60% in 5.7s 

Answer 4

Huffman có chi phí tĩnh, bảng Huffman, vì vậy tôi không đồng ý đó là lựa chọn tốt.

Có các phiên bản thích nghi làm điều này, nhưng tốc độ nén có thể bị ảnh hưởng. Trên thực tế, câu hỏi bạn nên hỏi là "thuật toán để nén chuỗi văn bản với những đặc điểm này". Ví dụ, nếu lặp đi lặp lại dài dự kiến, đơn giản Run-Lengh Encoding có thể là đủ. Nếu bạn có thể đảm bảo rằng chỉ có các từ tiếng Anh, dấu cách, dấu chấm câu và các chữ số không thường xuyên sẽ xuất hiện, thì Huffman với bảng Huffman được xác định trước có thể mang lại kết quả tốt.

Nói chung, các thuật toán của họ Lempel-Ziv có khả năng nén và hiệu suất rất tốt và các thư viện cho chúng rất nhiều. Tôi sẽ đi với điều đó.

Với thông tin rằng những gì đang được nén là URL, thì tôi khuyên bạn nên trước khi nén (với bất kỳ thuật toán nào có thể dễ dàng có sẵn), bạn CODIFY chúng. URL tuân theo các mẫu được xác định rõ và một số phần của mẫu có thể dự đoán được. Bằng cách sử dụng kiến ​​thức này, bạn có thể mã hóa các URL thành một cái gì đó nhỏ hơn để bắt đầu, và những ý tưởng đằng sau mã hóa Huffman có thể giúp bạn ở đây. Ví dụ: dịch URL thành luồng bit, bạn có thể thay thế "http" bằng bit 1 và bất kỳ thứ gì khác bằng bit "0" theo sau là procotol thực tế (hoặc sử dụng bảng để nhận các giao thức phổ biến khác). , như https, ftp, tệp). Các ": //" có thể được giảm hoàn toàn, miễn là bạn có thể đánh dấu sự kết thúc của giao thức. Vv Đi đọc về định dạng URL, và suy nghĩ về cách chúng có thể được mã hóa để có ít không gian hơn.

Answer 5

Bất kỳ thuật toán/thư viện nào hỗ trợ từ điển được đặt trước, ví dụ: zlib.

Bằng cách này bạn có thể làm nổi bật máy nén với cùng loại văn bản có khả năng xuất hiện trong đầu vào. Nếu các tệp tương tự theo một cách nào đó (ví dụ: tất cả các URL, tất cả các chương trình C, tất cả các bài đăng StackOverflow, tất cả các bản vẽ nghệ thuật ASCII) thì một số chất nền sẽ xuất hiện trong hầu hết hoặc tất cả các tệp đầu vào.

Mỗi thuật toán nén sẽ tiết kiệm không gian nếu chuỗi tương tự được lặp đi lặp lại nhiều lần trong một tập tin đầu vào (ví dụ như "the" trong văn bản tiếng Anh hoặc "int" trong mã C.)

Nhưng trong trường hợp của URL nhất định các chuỗi (ví dụ: "http://www.", ".com", ".html", ".aspx" thường sẽ xuất hiện một lần trong mỗi tệp nhập. Vì vậy, bạn cần chia sẻ chúng giữa các tệp bằng cách nào đó thay vì có một lần xuất hiện nén cho mỗi tệp. chúng trong một từ điển cài sẵn sẽ đạt được điều này.

Answer 6

Tôi không có mã để bàn, nhưng tôi luôn thích cách tiếp cận xây dựng một bảng tra cứu 2D kích thước 256 * 256 ký tự (RFC 1978, PPP Predictor nén Nghị định thư). Để nén một chuỗi bạn lặp qua mỗi char và sử dụng bảng tra cứu để có được 'được dự đoán' char tiếp theo bằng cách sử dụng char hiện tại và trước đó làm chỉ mục trong bảng. Nếu có một trận đấu bạn viết 1 bit đơn, nếu không viết 0, char và cập nhật bảng tra cứu với char hiện tại. Cách tiếp cận này về cơ bản duy trì một bảng tra cứu động (và thô) của ký tự tiếp theo có thể xảy ra nhất trong luồng dữ liệu.

Bạn có thể bắt đầu với bảng tra cứu bằng 0, nhưng nó hoạt động tốt nhất trên các chuỗi rất ngắn nếu được khởi tạo với ký tự có khả năng nhất cho mỗi cặp ký tự, ví dụ, cho tiếng Anh. Vì vậy, miễn là bảng tra cứu ban đầu là giống nhau cho nén và giải nén bạn không cần phải phát ra nó vào dữ liệu nén.

Thuật toán này không cung cấp tỷ lệ nén tuyệt vời, nhưng nó cực kỳ tiết kiệm với bộ nhớ và tài nguyên CPU và cũng có thể hoạt động trên luồng dữ liệu liên tục - bộ giải nén duy trì bản sao của bảng tra cứu khi nó giải nén, do đó bảng tra cứu điều chỉnh theo loại dữ liệu đang được nén.

Answer 7

Bạn có thể muốn xem Standard Compression Scheme for Unicode.

SQL Server 2008 R2 sử dụng nó trong nội bộ và có thể đạt tới 50% nén.