Nén các chuỗi nhỏ, với những gì để tạo từ điển bên ngoài?

Question

Tôi muốn nén nhiều chuỗi nhỏ (khoảng 75-100 độ dài C# chuỗi). Tại thời điểm từ điển được tạo, tôi đã biết tất cả các chuỗi ngắn (gần một nghìn tỷ). Sẽ không có chuỗi ngắn bổ sung nào trong tương lai. Tôi cần thêm chính xác một chuỗi mà không giải nén các chuỗi khác.

Bây giờ tôi đang tìm kiếm một thư viện hoặc cách tốt nhất để làm như sau:

1. Tạo một từ điển sử dụng tất cả các chuỗi Tôi có
2. Sử dụng từ điển này để nén mỗi chuỗi
3. một cách để nén một chuỗi bằng từ điển từ 1.

Tôi đã tìm thấy good related question, nhưng điều này không cụ thể. Có lẽ có cái gì đó cho C# Tôi không biết, hoặc một thư viện ưa thích hoặc ai đó đã làm điều đó. Đó là lý do tôi hỏi câu hỏi này.

EDIT:

Với từ điển mà tôi đang nói về những điều như thế này: http://en.wikipedia.org/wiki/Dictionary_coder Nhưng tất cả những gì giúp để có được những chuỗi ngắn hơn. Các chuỗi là các tin nhắn văn bản ngắn trong các ngôn ngữ và URL khác nhau (30%/70%). Không cần các chuỗi được nén là con người có thể đọc được. Nó sẽ được lưu trữ trong các tập tin nhị phân.

Answer 1

Nếu có một nghìn tỷ dây và không còn nữa, thì mỗi chuỗi có thể được biểu diễn bằng 40 bit (5 byte). Tất cả những gì bạn cần là một cách để sử dụng 5 byte làm chỉ mục cho hàng nghìn tỷ.

Làm thế nào để bạn biết tất cả nghìn tỷ chuỗi? Nếu máy nén và bộ giải nén đều có quyền truy cập vào tất cả nghìn tỷ chuỗi hoặc nếu có cách để đặt hàng và tạo lại các chuỗi, thì tất cả những gì bạn cần là chỉ mục.

Nếu bạn không thể tìm cách lập chỉ mục các chuỗi, thì bạn có thể lấy một tập con của các chuỗi và sử dụng chúng làm từ điển cho máy nén.Chỉ cần lấy mẫu đại diện nhất (bạn cần phải tìm ra những gì có thể làm cho một số chuỗi phổ biến hơn các chuỗi khác hoặc đại diện của các chuỗi khác) và nối chúng vào một từ điển 32K. Khoảng 400 nghìn tỷ dây của bạn. Sau đó, deflateSetDictionary zlib của ngày cuối nén và inflateSetDictionary vào cuối giải nén, cả hai đều sử dụng chính xác cùng một từ điển 32K. Điều đó sẽ cung cấp nén tốt trên các chuỗi ngắn.

Answer 2

tôi đã không sử dụng nó, nhưng Smaz âm thanh đầy hứa hẹn cho việc này ...

Smaz là một thư viện nén đơn giản phù hợp cho nén rất chuỗi ngắn. Thư viện nén mục đích chung sẽ xây dựng trạng thái cần thiết để nén dữ liệu động, để có thể nén mọi loại dữ liệu. Đây là một ý tưởng rất hay, nhưng không phải cho một vấn đề cụ thể: nén các chuỗi nhỏ sẽ không hoạt động.

Smaz thay vào đó là không tốt cho nén dữ liệu mục đích chung, nhưng có thể nén văn bản bằng 40-50% trong trường hợp trung bình (chỉ hoạt động tốt hơn với tiếng Anh), và có thể thực hiện một chút nén cho HTML và cũng là url. Điểm quan trọng là Smaz có thể nén ngay cả các chuỗi gồm hai hoặc ba byte!

Ví dụ: chuỗi "the" được nén thành một byte đơn.

Vì văn bản được viết bằng C, hãy kiểm tra Bart De Smet's example for interoping with C through C#.