Nén chuỗi ngắn thực sự đơn giản

Question

Có một kỹ thuật nén thực sự đơn giản cho các chuỗi có chiều dài tối đa khoảng 255 ký tự không (vâng, tôi đang nén URLs)?

Tôi không quan tâm đến cường độ nén - Tôi đang tìm một thứ gì đó hoạt động rất tốt và nhanh chóng triển khai. Tôi muốn một cái gì đó đơn giản hơn SharpZipLib: một cái gì đó có thể được thực hiện với một vài phương pháp ngắn.

Answer 1

Tôi nghĩ câu hỏi then chốt ở đây là "Tại sao bạn muốn để nén URL?"

Đang cố gắng để rút ngắn url dài cho thanh địa chỉ?

Bạn nên lưu trữ URL ban đầu ở đâu đó (cơ sở dữ liệu, tệp văn bản ...) cùng với mã băm của phần không thuộc miền (MD5 là tốt). Sau đó bạn có thể có một trang đơn giản (hoặc một số HTTPModule nếu bạn đang cảm thấy hào nhoáng) để đọc MD5 và tra cứu URL thực. Đây là cách TinyURL và những người khác làm việc.

Ví dụ:

http://mydomain.com/folder1/folder2/page1.aspx 

thể được thiếu để:

http://mydomain.com/2d4f1c8a 

Sử dụng một thư viện nén cho điều này sẽ không làm việc. Chuỗi sẽ được nén thành một biểu diễn nhị phân ngắn hơn, nhưng chuyển đổi lại thành chuỗi cần phải hợp lệ như một phần của URL (ví dụ: Base64) sẽ loại bỏ bất kỳ lợi ích nào bạn thu được từ quá trình nén.

Lưu trữ nhiều URL trong bộ nhớ hoặc trên đĩa?

Sử dụng thư viện nén được tích hợp bên trong System.IO.Compression hoặc thư viện ZLib đơn giản và cực kỳ tốt. Vì bạn sẽ lưu trữ dữ liệu nhị phân, đầu ra được nén sẽ ổn định.Bạn sẽ cần phải giải nén nó để sử dụng nó như một URL.

Answer 2

Mục tiêu của bạn là gì?

• URL ngắn hơn? Hãy thử các công cụ rút gọn URL như http://tinyurl.com/ hoặc http://is.gd/
• Dung lượng lưu trữ? Kiểm tra System.IO.Compression. (Hoặc SharpZipLib)

Answer 3

Tôi sẽ bắt đầu thử một trong các thư viện zip (nguồn mở miễn phí) hiện có, ví dụ: http://www.icsharpcode.net/OpenSource/SharpZipLib/

Zip nên làm việc tốt cho chuỗi văn bản, và tôi không chắc chắn nếu nó là giá trị thực hiện một thuật toán nén yourserlf ....

Answer 4

Tôi muốn đề nghị xem xét trong System.IO.Compression Namespace. Có an article on CodeProject có thể hữu ích.

Answer 5

Bạn đã thử chỉ sử dụng gzip?

Không có ý tưởng nếu nó sẽ làm việc hiệu quả với các chuỗi ngắn như vậy, nhưng tôi muốn nói nó có lẽ là đặt cược tốt nhất của bạn.

Answer 6

Các mã nguồn mở thư viện SharpZipLib là dễ sử dụng và sẽ cung cấp cho bạn các công cụ nén

Answer 7

Như được đề xuất trong the accepted answer, Sử dụng nén dữ liệu không hoạt động để rút ngắn đường dẫn URL đã quá ngắn.

DotNetZip có lớp DeflateStream hiển thị phương pháp tĩnh (Được chia sẻ trong VB) CompressString. Đó là cách một dòng để nén chuỗi bằng DEFLATE (RFC 1951). Việc thực hiện DEFLATE hoàn toàn tương thích với System.IO.Compression.DeflateStream, nhưng DotNetZip nén tốt hơn. Dưới đây là cách bạn có thể sử dụng nó:

string[] orig = { 
    "folder1/folder2/page1.aspx", 
    "folderBB/folderAA/page2.aspx", 
}; 
public void Run() 
{ 
    foreach (string s in orig) 
    { 
     System.Console.WriteLine("original : {0}", s); 
     byte[] compressed = DeflateStream.CompressString(s); 
     System.Console.WriteLine("compressed : {0}", ByteArrayToHexString(compressed)); 
     string uncompressed = DeflateStream.UncompressString(compressed); 
     System.Console.WriteLine("uncompressed: {0}\n", uncompressed); 
    } 
} 

Sử dụng mã mà, đây là kết quả xét nghiệm của tôi:

original : folder1/folder2/page1.aspx 
compressed : 4bcbcf49492d32d44f03d346fa0589e9a9867a89c5051500 
uncompressed: folder1/folder2/page1.aspx 

original : folderBB/folderAA/page2.aspx 
compressed : 4bcbcf49492d7272d24f03331c1df50b12d3538df4128b0b2a00 
uncompressed: folderBB/folderAA/page2.aspx 

Vì vậy, bạn sẽ nhìn thấy "nén" mảng byte, khi đại diện trong hex, dài hơn bản gốc, dài khoảng 2x. Lý do là một byte hex thực sự là 2 ký tự ASCII.

Bạn có thể bù đắp phần nào cho điều đó bằng cách sử dụng base-62, thay vì base-16 (hex) để biểu thị số. Trong trường hợp đó a-z và A-Z cũng là các chữ số, cho bạn 0-9 (10) + a-z (+26) + A-Z (+26) = 62 tổng số. Điều đó sẽ rút ngắn sản lượng đáng kể. Tôi đã không thử điều đó. chưa.

---

EDIT
Ok Tôi đã thử nghiệm encoder Base-62. Nó rút ngắn chuỗi hex khoảng một nửa. Tôi nghĩ rằng nó sẽ cắt giảm đến 25% (62/16 = ~ 4) Nhưng tôi nghĩ rằng tôi đang mất một cái gì đó với discretization. Trong các thử nghiệm của tôi, chuỗi được mã hóa cơ sở-62 kết quả có cùng độ dài với URL gốc. Vì vậy, không, bằng cách sử dụng nén và sau đó mã hóa base-62 vẫn không phải là một cách tiếp cận tốt. bạn thực sự muốn có giá trị băm.

Answer 8

Bạn có thể sử dụng deflate thuật toán trực tiếp, mà không cần bất kỳ checksums đầu hoặc cuối trang, như mô tả trong câu hỏi này: Python: Inflate and Deflate implementations

này cắt giảm một URL 4100 nhân vật để 1270 ký tự base64, trong thử nghiệm của tôi, cho phép nó để phù hợp với bên trong Giới hạn 2000 của IE.

Và đây là ví dụ về số 4000-character URL, không thể giải quyết bằng hashtable vì applet có thể tồn tại trên bất kỳ máy chủ nào.