Nén số lớn (hoặc chuỗi) giá trị nhỏ

Question

trang ASP.NET của tôi có sau tham số chuỗi truy vấn:

…?IDs=1000000012,1000000021,1000000013,1000000022&... 

Đây IDs tham số sẽ luôn luôn có số cách nhau bằng một cái gì đó, trong trường hợp này ,. Hiện tại có 4 số nhưng thông thường chúng sẽ ở giữa 3 và 7.

Bây giờ, tôi đang tìm phương pháp để chuyển đổi từng số lớn từ trên xuống thành giá trị nhỏ nhất có thể; cụ thể nén giá trị của tham số chuỗi truy vấn IDs. Cả hai, nén từng thuật toán số hoặc nén toàn bộ giá trị của tham số chuỗi truy vấn IDs đều được chào đón.

1. Mã hóa hoặc giải mã không phải là vấn đề; chỉ cần nén tham số chuỗi tham số IDs giá trị.
2. Tạo một số giá trị nhỏ duy nhất cho IDs và sau đó truy lục giá trị của nó từ một số nguồn dữ liệu nằm ngoài phạm vi.

Có một thuật toán để nén các số lớn như vậy thành các giá trị nhỏ hoặc để nén giá trị của tham số chuỗi truy vấn IDs tất cả cùng nhau không?

Answer 1

Bạn về cơ bản cần nhiều chỗ cho số của bạn vì bạn đang sử dụng cơ số 10 để đại diện cho chúng. Một cải tiến sẽ được sử dụng cơ sở 16 (hex). Vì vậy, ví dụ, bạn có thể đại diện cho 255 (3 chữ số) là ff (2 chữ số).

Bạn có thể lấy khái niệm mà hơn nữa bằng cách sử dụng một cơ sở số lượng lớn hơn nhiều ... tập tất cả các ký tự có giá trị thông số chuỗi truy vấn: ''

AZ, az, 0-9, '- ',' ~ ',' _ ',' + '

Điều đó mang lại cho bạn cơ sở 67 ký tự để hoạt động (xem Wikipedia on QueryString).

Hãy xem this SO post để biết cách tiếp cận chuyển đổi cơ sở 10 thành số căn cứ tùy ý.

EDIT:

Trong SO bài liên quan, nhìn vào phần này:

string xx = IntToString(42, 
      new char[] { '0','1','2','3','4','5','6','7','8','9', 
      'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z', 
      'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x'}); 

Đó là hầu hết những gì bạn cần. Chỉ cần mở rộng nó bằng cách thêm vài nhân vật đó là mất tích:

yz.- ~ _ +

Đó bài thiếu một phương pháp để trở về căn cứ 10. Tôi sẽ không viết nó :-) nhưng thủ tục như sau:

Xác định bộ đếm tôi sẽ gọi TOTAL.

Nhìn vào ngay hầu hết ký tự và tìm vị trí của nó trong mảng.
TOTAL = (vị trí của ký tự trong mảng) Ví dụ: Đầu vào là BA1. TOTAL bây giờ là 1 (vì "1" ở vị trí 1 trong mảng)

Bây giờ hãy xem ký tự tiếp theo bên trái của ký tự đầu tiên và tìm vị trí của nó trong mảng. TOTAL + = 47 * (vị trí của ký tự trong mảng) Ví dụ: Đầu vào là BA1. TOTAL hiện là (47 * 11) + 1 = 518

Bây giờ hãy xem ký tự tiếp theo bên trái của ký tự trước và tìm vị trí của nó trong mảng. TOTAL + = 47 * 47 * (vị trí của ký tự trong mảng) Ví dụ: Đầu vào là BA1. Tổng số bây giờ là (47 * 47 * 10) + (47 * 11) + 1 = 243508

Và cứ tiếp tục như vậy.

Tôi khuyên bạn nên viết một bài kiểm tra đơn vị chuyển đổi một loạt 10 số cơ sở thành cơ sở 47 và sau đó quay lại để đảm bảo mã chuyển đổi của bạn hoạt động đúng.

Lưu ý làm thế nào bạn đại diện cho một 6 chữ số cơ sở 10 chỉ trong 3 chữ số của cơ sở 47 :-)

Answer 2

Nếu vấn đề chỉ là chiều dài URL, bạn có thể chuyển đổi số điện thoại để , sau đó chuyển đổi chúng trở lại con số ở phía máy chủ

Answer 3

Phạm vi của các số của bạn là gì? Giả sử họ có thể phù hợp trong một số nguyên 16-bit, tôi sẽ:

• Lưu trữ tất cả các số của bạn như 16-bit integers (2 byte cho mỗi số, phạm vi -32,768 tới 32,767)
• Xây dựng một bytestream của số nguyên 16-bit (XDR có thể là một lựa chọn tốt ở đây; tại ít nhất, hãy chắc chắn để xử lý endianness chính xác)
• Base64 encode bytestream, bằng cách sử dụng mã hóa base64 sửa đổi cho URL (ròng khoảng 3 ký tự trên mỗi số)

Như một thêm tiền thưởng bạn không cần ký tự dấu phẩy nữa vì bạn biết mỗi số là 2 byte.

Hoặc, nếu điều đó không đủ tốt, tôi sẽ sử dụng zlib để nén luồng số nguyên của bạn và sau đó base64 luồng nén zlib. Bạn cũng có thể chuyển sang số nguyên 32 bit nếu 16 bit không phải là phạm vi đủ lớn (nghĩa là nếu bạn thực sự cần số trong phạm vi 1.000.000.000).

Edit:

Có lẽ đã quá muộn, nhưng đây là một thực hiện mà có thể làm những gì bạn cần:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Scratch { 
    class Program { 
     static void Main(string[] args) { 
      //var ids = new[] { 1000000012, 1000000021, 1000000013, 1000000022 }; 
      var rand = new Random(); 
      var ids = new int[rand.Next(20)]; 
      for(var i = 0; i < ids.Length; i++) { 
       ids[i] = rand.Next(); 
      } 

      WriteIds(ids); 
      var s = IdsToString(ids); 
      Console.WriteLine("\nResult string is: {0}", s); 
      var newIds = StringToIds(s); 
      WriteIds(newIds); 
      Console.ReadLine(); 
     } 

     public static void WriteIds(ICollection<Int32> ids) { 
      Console.Write("\nIDs: "); 
      bool comma = false; 
      foreach(var id in ids) { 
       if(comma) { 
        Console.Write(","); 
       } else { 
        comma = true; 
       } 
       Console.Write(id); 
      } 
      Console.WriteLine(); 
     } 

     public static string IdsToString(ICollection<Int32> ids) { 
      var allbytes = new List<byte>(); 
      foreach(var id in ids) { 
       var bytes = BitConverter.GetBytes(id); 
       allbytes.AddRange(bytes);     
      } 
      var str = Convert.ToBase64String(allbytes.ToArray(), Base64FormattingOptions.None); 
      return str.Replace('+', '-').Replace('/', '_').Replace('=', '.'); 
     } 

     public static ICollection<Int32> StringToIds(string idstring) { 
      var result = new List<Int32>(); 
      var str = idstring.Replace('-', '+').Replace('_', '/').Replace('.', '='); 
      var bytes = Convert.FromBase64String(str); 
      for(var i = 0; i < bytes.Length; i += 4) { 
       var id = BitConverter.ToInt32(bytes, i); 
       result.Add(id); 
      } 
      return result; 
     } 
    } 
} 

Answer 4

cách khuôn mẫu được các ID bạn đang nhận được? nếu chữ số bằng chữ số, các ID là ngẫu nhiên, thì phương pháp tôi sắp đề xuất sẽ không hiệu quả lắm. nhưng nếu các ID bạn đưa ra làm ví dụ là đại diện cho các loại bạn muốn nhận được thì có lẽ những điều sau đây có thể hoạt động?

tôi khuyến khích ý tưởng này bằng ví dụ.

bạn có ví dụ: 1000000012 làm ID mà bạn muốn nén. tại sao không lưu trữ nó như [{1}, {0,7}, {12}]? Điều này có nghĩa là chữ số đầu tiên là số 1, sau đó là 7 số 0, sau đó là 12. Vì vậy, nếu chúng ta sử dụng ký hiệu {x} sẽ đại diện cho một thể hiện của x, trong khi chúng ta sử dụng {x, y} có nghĩa là x xảy ra y lần trong một hàng.

bạn có thể mở rộng điều này với một chút phù hợp với mẫu và/hoặc phù hợp với chức năng.Ví dụ:

ví dụ, đối sánh mẫu: 1000100032 sẽ là [{1000,2} {32}]. Ví dụ:

ví dụ, chức năng phù hợp: nếu ID của bạn có 10 chữ số, sau đó chia ID thành hai số có 5 chữ số và lưu lại phương trình của đường đi qua cả hai điểm. nếu ID = 1000000012, bạn có y1 = 10000 và y2 = 12. do đó, độ dốc của bạn là -9988 và điểm đánh chặn của bạn là 10000 (giả sử x1 = 0, x2 = 1). Trong trường hợp này, nó không phải là một sự cải tiến, nhưng nếu các con số ngẫu nhiên hơn, nó có thể được. Tương tự, bạn có thể lưu trữ chuỗi các ID với các hàm tuyến tính từng phần.

trong mọi trường hợp, điều này chủ yếu phụ thuộc vào cấu trúc ID của bạn.

Answer 5

Tôi giả sử bạn đang làm điều này như một cách giải quyết cho những hạn chế chiều dài yêu cầu URL ...

câu trả lời khác đã gợi ý mã hóa các số id thập phân trong hex, base47 hoặc base64, nhưng bạn có thể (về mặt lý thuyết) làm một tốt hơn nhiều so với việc sử dụng LZW (hoặc tương tự) để nén danh sách id. Tùy thuộc vào số lượng dự phòng có trong danh sách ID của bạn, bạn có thể giảm đáng kể hơn 40%, ngay cả sau khi mã hóa lại các byte đã nén dưới dạng văn bản.

Trong trình bao, tôi khuyên bạn nên tìm một thư viện nén văn bản sẵn có được triển khai trong Javascript và sử dụng phía máy khách để nén danh sách ID. Sau đó mã hóa bytestring nén bằng cách sử dụng base47/base64 và chuyển chuỗi được mã hóa làm tham số URL. Ở phía máy chủ làm ngược lại; tức là giải mã, sau đó giải nén.

EDIT: Là một thử nghiệm, tôi đã tạo một danh sách gồm 36 số nhận dạng khác nhau giống như số bạn đã cung cấp và nén bằng gzip. Tệp gốc là 396 byte, tệp nén là 101 byte và tệp nén + base64 là 138 byte. Đó là mức giảm 65% tổng thể. Và tỷ lệ nén thực sự có thể cải thiện cho các tệp lớn hơn. Tuy nhiên, khi tôi thử điều này với một bộ đầu vào nhỏ (ví dụ: chỉ 4 số nhận dạng ban đầu), tôi không có nén, và sau khi mã hóa kích thước lớn hơn bản gốc.

Google "thư viện LZW javascript"

Về lý thuyết, có thể có giải pháp đơn giản hơn. Gửi các tham số dưới dạng "dữ liệu bài đăng" thay vì trong URL yêu cầu và yêu cầu trình duyệt áp dụng tính năng nén bằng cách sử dụng một trong các mã hóa mà nó hiểu được. Điều đó sẽ giúp bạn tiết kiệm nhiều hơn vì không cần phải mã hóa dữ liệu đã nén thành các ký tự URL hợp pháp.

Sự cố là làm cho trình duyệt nén yêu cầu ... và thực hiện điều đó theo cách độc lập của trình duyệt.

Answer 6

Đây là một sơ đồ thực sự đơn giản khác sẽ cho phép nén tốt cho một tập hợp các số dạng N + delta trong đó N là một hằng số lớn.

public int[] compress(int[] input) { 
    int[] res = input.clone(); 
    Arrays.sort(res); 
    for (int i = 1; i < res.length; i++) { 
     res[i] = res[i] - res[i - 1]; 
    } 
    return res; 
} 

này nên giảm tập {1000000012,1000000021,1000000013,1000000022} vào danh sách [1000000012,1,9,1], sau đó bạn có thể nén thêm bởi đại diện cho những con số trong mã hóa base47 như mô tả trong câu trả lời khác.

Sử dụng mã hóa thập phân đơn giản, điều này từ 44 ký tự đến 16 ký tự; tức là 63%. (Và sử dụng base47 sẽ cho phép nén nhiều hơn).

Nếu không thể chấp nhận để sắp xếp id, bạn không nhận được nén tốt như vậy. Trong ví dụ này, {1000000012,1000000021,1000000013,1000000022} nén vào danh sách [1000000012,9,-8,9].Đó chỉ là một ký tự dài hơn cho ví dụ này

Dù bằng cách nào, điều này tốt hơn thuật toán nén chung hoặc lược đồ mã hóa ... CHO LOẠI NÀY INPUT.