Cách hiệu quả nhất để mã hóa GUID tùy ý thành ASCII có thể đọc được (33-127) là gì?

Question

Biểu diễn chuỗi chuẩn của GUID mất khoảng 36 ký tự. Đó là rất tốt đẹp, nhưng cũng thực sự lãng phí. Tôi tự hỏi, làm thế nào để mã hóa nó theo cách ngắn nhất có thể bằng cách sử dụng tất cả các ký tự ASCII trong phạm vi 33-127. Việc thực hiện ngây thơ tạo ra 22 ký tự, đơn giản chỉ vì 128 bit/6 bit sản lượng 22.

Huffman mã hóa là tôi thứ hai tốt nhất, câu hỏi duy nhất là làm thế nào để chọn các mã ....

Các mã hóa phải được lossless, tất nhiên.

Answer 1

Sử dụng cơ sở 85. Xem phần 4.1. Tại sao lại là 85? của A Compact Representation of IPv6 Addresses

Địa chỉ IPv6, giống như GUID được tạo thành từ tám phần 16 bit.

Answer 2

Chỉ cần đi Base64.

Answer 3

Giả sử rằng tất cả GUID của bạn đang được tạo bởi cùng một thuật toán, bạn có thể lưu 4 bit bằng cách không mã hóa thuật toán nibble, trước khi áp dụng bất kỳ mã hóa nào khác: - |

Answer 4

Sử dụng phạm vi đầy đủ từ 33 (khoảng không gian wirh sai, tình cờ?) Đến 127 cho bạn 95 ký tự có thể. Biểu thị giá trị có thể có của 2^128 có thể có của guid trong cơ sở 95 sẽ sử dụng 20 ký tự. Điều này (modulo những thứ như thả nybbles sẽ được liên tục) là tốt nhất bạn có thể làm. Tự khắc phục sự cố - sử dụng cơ sở 64.

Answer 5

An tùy ý HƯỚNG DẪN? Thuật toán "ngây thơ" sẽ tạo ra kết quả tối ưu. Cách duy nhất để nén GUID hơn nữa là sử dụng các mẫu trong dữ liệu bị loại trừ bởi ràng buộc "tùy ý" của bạn.

Answer 6

Bạn có 95 ký tự có sẵn - vì vậy, nhiều hơn 6 bit, nhưng không quá 7 ký tự (khoảng 6,57 thực tế). Bạn có thể sử dụng 128/log2 (95) = khoảng 19,48 ký tự, để mã hóa thành 20 ký tự. Nếu tiết kiệm 2 ký tự theo hình thức mã hóa là giá trị sự mất khả năng đọc cho bạn, một cái gì đó tương tự (giả):

char encoded[21]; 
long long guid; // 128 bits number 

for(int i=0; i<20; ++i) { 
    encoded[i] = chr(guid % 95 + 33); 
    guid /= 95; 
} 
encoded[20] = chr(0); 

mà về cơ bản là chung chung "mã hóa một số ở một số cơ sở" mã, ngoại trừ việc không có nhu cầu để đảo ngược "chữ số" kể từ khi tùy ý của đơn đặt hàng anyway (và little-endian là trực tiếp hơn và tự nhiên). Để lấy lại guid từ chuỗi mã hóa, trong một cách rất giống nhau, tính toán đa thức trong cơ sở 95 (sau khi đã trừ 33 từ mỗi chữ số dĩ nhiên):

guid = 0; 

for(int i=0; i<20; ++i) { 
    guid *= 95; 
    guid += ord(encoded[i]) - 33; 
} 

chủ yếu sử dụng phương pháp Horner để đánh giá đa thức.

Answer 7

Đây là một câu hỏi cũ, nhưng tôi phải giải quyết nó để hệ thống tôi đang làm việc tương thích ngược.

Yêu cầu chính xác là mã định danh do khách hàng tạo sẽ được ghi vào cơ sở dữ liệu và được lưu trữ trong cột có 20 ký tự duy nhất. Nó không bao giờ được hiển thị cho người dùng và không được lập chỉ mục theo bất kỳ cách nào.

Vì tôi không thể loại bỏ yêu cầu, tôi thực sự muốn sử dụng một hướng dẫn (là statistically unique) và nếu tôi có thể mã hóa nó thành 20 ký tự, thì đó sẽ là giải pháp tốt.

Ascii-85 cho phép bạn mã hóa 4 byte dữ liệu nhị phân thành 5 byte dữ liệu Ascii. Vì vậy, một hướng dẫn 16 byte sẽ chỉ phù hợp với 20 ký tự Ascii sử dụng lược đồ mã hóa này. Một Guid có thể có 3.1962657931507848761677563491821e + 38 giá trị rời rạc trong khi 20 ký tự của Ascii-85 có thể có 3.8759531084514355873123178482056e + 38 giá trị rời rạc.

Khi ghi vào cơ sở dữ liệu, tôi có một số lo ngại về việc cắt ngắn để không có ký tự khoảng trắng nào được bao gồm trong bảng mã. Tôi cũng gặp sự cố với collation, mà tôi đã giải quyết bằng cách loại trừ các ký tự chữ thường khỏi mã hóa. Ngoài ra, nó sẽ chỉ bao giờ được thông qua một paramaterized command, vì vậy bất kỳ ký tự SQL đặc biệt nào sẽ được tự động thoát.

Tôi đã bao gồm mã C# để thực hiện mã hóa và giải mã Ascii-85 trong trường hợp nó giúp mọi người ở ngoài đó. Rõ ràng, tùy thuộc vào cách sử dụng của bạn, bạn có thể cần phải chọn một nhân vật khác nhau thiết lập như những hạn chế của tôi khiến tôi chọn một số nhân vật khác thường như 'ß' và 'Ø' - nhưng đó là phần dễ dàng:

/// <summary> 
/// This code implements an encoding scheme that uses 85 printable ascii characters 
/// to encode the same volume of information as contained in a Guid. 
/// 
/// Ascii-85 can represent 4 binary bytes as 5 Ascii bytes. So a 16 byte Guid can be 
/// represented in 20 Ascii bytes. A Guid can have 
/// 3.1962657931507848761677563491821e+38 discrete values whereas 20 characters of 
/// Ascii-85 can have 3.8759531084514355873123178482056e+38 discrete values. 
/// 
/// Lower-case characters are not included in this encoding to avoid collation 
/// issues. 
/// This is a departure from standard Ascii-85 which does include lower case 
/// characters. 
/// In addition, no whitespace characters are included as these may be truncated in 
/// the database depending on the storage mechanism - ie VARCHAR vs CHAR. 
/// </summary> 
internal static class Ascii85 
{ 
    /// <summary> 
    /// 85 printable ascii characters with no lower case ones, so database 
    /// collation can't bite us. No ' ' character either so database can't 
    /// truncate it! 
    /// Unfortunately, these limitation mean resorting to some strange 
    /// characters like 'Æ' but we won't ever have to type these, so it's ok. 
    /// </summary> 
    private static readonly char[] kEncodeMap = new[] 
    { 
     '0','1','2','3','4','5','6','7','8','9', // 10 
     'A','B','C','D','E','F','G','H','I','J', // 20 
     'K','L','M','N','O','P','Q','R','S','T', // 30 
     'U','V','W','X','Y','Z','|','}','~','{', // 40 
     '!','"','#','$','%','&','\'','(',')','`', // 50 
     '*','+',',','-','.','/','[','\\',']','^', // 60 
     ':',';','<','=','>','?','@','_','¼','½', // 70 
     '¾','ß','Ç','Ð','€','«','»','¿','•','Ø', // 80 
     '£','†','‡','§','¥'      // 85 
    }; 

    /// <summary> 
    /// A reverse mapping of the <see cref="kEncodeMap"/> array for decoding 
    /// purposes. 
    /// </summary> 
    private static readonly IDictionary<char, byte> kDecodeMap; 

    /// <summary> 
    /// Initialises the <see cref="kDecodeMap"/>. 
    /// </summary> 
    static Ascii85() 
    { 
     kDecodeMap = new Dictionary<char, byte>(); 

     for (byte i = 0; i < kEncodeMap.Length; i++) 
     { 
      kDecodeMap.Add(kEncodeMap[i], i); 
     } 
    } 

    /// <summary> 
    /// Decodes an Ascii-85 encoded Guid. 
    /// </summary> 
    /// <param name="ascii85Encoding">The Guid encoded using Ascii-85.</param> 
    /// <returns>A Guid decoded from the parameter.</returns> 
    public static Guid Decode(string ascii85Encoding) 
    { 
     // Ascii-85 can encode 4 bytes of binary data into 5 bytes of Ascii. 
     // Since a Guid is 16 bytes long, the Ascii-85 encoding should be 20 
     // characters long. 
     if(ascii85Encoding.Length != 20) 
     { 
      throw new ArgumentException(
       "An encoded Guid should be 20 characters long.", 
       "ascii85Encoding"); 
     } 

     // We only support upper case characters. 
     ascii85Encoding = ascii85Encoding.ToUpper(); 

     // Split the string in half and decode each substring separately. 
     var higher = ascii85Encoding.Substring(0, 10).AsciiDecode(); 
     var lower = ascii85Encoding.Substring(10, 10).AsciiDecode(); 

     // Convert the decoded substrings into an array of 16-bytes. 
     var byteArray = new[] 
     { 
      (byte)((higher & 0xFF00000000000000) >> 56),   
      (byte)((higher & 0x00FF000000000000) >> 48),   
      (byte)((higher & 0x0000FF0000000000) >> 40),   
      (byte)((higher & 0x000000FF00000000) >> 32),   
      (byte)((higher & 0x00000000FF000000) >> 24),   
      (byte)((higher & 0x0000000000FF0000) >> 16),   
      (byte)((higher & 0x000000000000FF00) >> 8),   
      (byte)((higher & 0x00000000000000FF)), 
      (byte)((lower & 0xFF00000000000000) >> 56),   
      (byte)((lower & 0x00FF000000000000) >> 48),   
      (byte)((lower & 0x0000FF0000000000) >> 40),   
      (byte)((lower & 0x000000FF00000000) >> 32),   
      (byte)((lower & 0x00000000FF000000) >> 24),   
      (byte)((lower & 0x0000000000FF0000) >> 16),   
      (byte)((lower & 0x000000000000FF00) >> 8),   
      (byte)((lower & 0x00000000000000FF)), 
     }; 

     return new Guid(byteArray); 
    } 

    /// <summary> 
    /// Encodes binary data into a plaintext Ascii-85 format string. 
    /// </summary> 
    /// <param name="guid">The Guid to encode.</param> 
    /// <returns>Ascii-85 encoded string</returns> 
    public static string Encode(Guid guid) 
    { 
     // Convert the 128-bit Guid into two 64-bit parts. 
     var byteArray = guid.ToByteArray(); 
     var higher = 
      ((UInt64)byteArray[0] << 56) | ((UInt64)byteArray[1] << 48) | 
      ((UInt64)byteArray[2] << 40) | ((UInt64)byteArray[3] << 32) | 
      ((UInt64)byteArray[4] << 24) | ((UInt64)byteArray[5] << 16) | 
      ((UInt64)byteArray[6] << 8) | byteArray[7]; 

     var lower = 
      ((UInt64)byteArray[ 8] << 56) | ((UInt64)byteArray[ 9] << 48) | 
      ((UInt64)byteArray[10] << 40) | ((UInt64)byteArray[11] << 32) | 
      ((UInt64)byteArray[12] << 24) | ((UInt64)byteArray[13] << 16) | 
      ((UInt64)byteArray[14] << 8) | byteArray[15]; 

     var encodedStringBuilder = new StringBuilder(); 

     // Encode each part into an ascii-85 encoded string. 
     encodedStringBuilder.AsciiEncode(higher); 
     encodedStringBuilder.AsciiEncode(lower); 

     return encodedStringBuilder.ToString(); 
    } 

    /// <summary> 
    /// Encodes the given integer using Ascii-85. 
    /// </summary> 
    /// <param name="encodedStringBuilder">The <see cref="StringBuilder"/> to 
    /// append the results to.</param> 
    /// <param name="part">The integer to encode.</param> 
    private static void AsciiEncode(
     this StringBuilder encodedStringBuilder, UInt64 part) 
    { 
     // Nb, the most significant digits in our encoded character will 
     // be the right-most characters. 
     var charCount = (UInt32)kEncodeMap.Length; 

     // Ascii-85 can encode 4 bytes of binary data into 5 bytes of Ascii. 
     // Since a UInt64 is 8 bytes long, the Ascii-85 encoding should be 
     // 10 characters long. 
     for (var i = 0; i < 10; i++) 
     { 
      // Get the remainder when dividing by the base. 
      var remainder = part % charCount; 

      // Divide by the base. 
      part /= charCount; 

      // Add the appropriate character for the current value (0-84). 
      encodedStringBuilder.Append(kEncodeMap[remainder]); 
     } 
    } 

    /// <summary> 
    /// Decodes the given string from Ascii-85 to an integer. 
    /// </summary> 
    /// <param name="ascii85EncodedString">Decodes a 10 character Ascii-85 
    /// encoded string.</param> 
    /// <returns>The integer representation of the parameter.</returns> 
    private static UInt64 AsciiDecode(this string ascii85EncodedString) 
    { 
     if (ascii85EncodedString.Length != 10) 
     { 
      throw new ArgumentException(
       "An Ascii-85 encoded Uint64 should be 10 characters long.", 
       "ascii85EncodedString"); 
     } 

     // Nb, the most significant digits in our encoded character 
     // will be the right-most characters. 
     var charCount = (UInt32)kEncodeMap.Length; 
     UInt64 result = 0; 

     // Starting with the right-most (most-significant) character, 
     // iterate through the encoded string and decode. 
     for (var i = ascii85EncodedString.Length - 1; i >= 0; i--) 
     { 
      // Multiply the current decoded value by the base. 
      result *= charCount; 

      // Add the integer value for that encoded character. 
      result += kDecodeMap[ascii85EncodedString[i]]; 
     } 

     return result; 
    } 
} 

Ngoài ra, ở đây các bài kiểm tra đơn vị. Họ không phải là triệt để như tôi muốn, và tôi không thích những phi định mệnh về nơi Guid.NewGuid() được sử dụng, nhưng họ nên giúp bạn bắt đầu:

/// <summary> 
/// Tests to verify that the Ascii-85 encoding is functioning as expected. 
/// </summary> 
[TestClass] 
[UsedImplicitly] 
public class Ascii85Tests 
{ 
    [TestMethod] 
    [Description("Ensure that the Ascii-85 encoding is correct.")] 
    [UsedImplicitly] 
    public void CanEncodeAndDecodeAGuidUsingAscii85() 
    { 
     var guidStrings = new[] 
     { 
      "00000000-0000-0000-0000-000000000000", 
      "00000000-0000-0000-0000-0000000000FF", 
      "00000000-0000-0000-0000-00000000FF00", 
      "00000000-0000-0000-0000-000000FF0000", 
      "00000000-0000-0000-0000-0000FF000000", 
      "00000000-0000-0000-0000-00FF00000000", 
      "00000000-0000-0000-0000-FF0000000000", 
      "00000000-0000-0000-00FF-000000000000", 
      "00000000-0000-0000-FF00-000000000000", 
      "00000000-0000-00FF-0000-000000000000", 
      "00000000-0000-FF00-0000-000000000000", 
      "00000000-00FF-0000-0000-000000000000", 
      "00000000-FF00-0000-0000-000000000000", 
      "000000FF-0000-0000-0000-000000000000", 
      "0000FF00-0000-0000-0000-000000000000", 
      "00FF0000-0000-0000-0000-000000000000", 
      "FF000000-0000-0000-0000-000000000000", 
      "FF000000-0000-0000-0000-00000000FFFF", 
      "00000000-0000-0000-0000-0000FFFF0000", 
      "00000000-0000-0000-0000-FFFF00000000", 
      "00000000-0000-0000-FFFF-000000000000", 
      "00000000-0000-FFFF-0000-000000000000", 
      "00000000-FFFF-0000-0000-000000000000", 
      "0000FFFF-0000-0000-0000-000000000000", 
      "FFFF0000-0000-0000-0000-000000000000", 
      "00000000-0000-0000-0000-0000FFFFFFFF", 
      "00000000-0000-0000-FFFF-FFFF00000000", 
      "00000000-FFFF-FFFF-0000-000000000000", 
      "FFFFFFFF-0000-0000-0000-000000000000", 
      "00000000-0000-0000-FFFF-FFFFFFFFFFFF", 
      "FFFFFFFF-FFFF-FFFF-0000-000000000000", 
      "FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFFFFFF", 
      "1000000F-100F-100F-100F-10000000000F" 
     }; 

     foreach (var guidString in guidStrings) 
     { 
      var guid = new Guid(guidString); 
      var encoded = Ascii85.Encode(guid); 

      Assert.AreEqual(
       20, 
       encoded.Length, 
       "A guid encoding should not exceed 20 characters."); 

      var decoded = Ascii85.Decode(encoded); 

      Assert.AreEqual(
       guid, 
       decoded, 
       "The guids are different after being encoded and decoded."); 
     } 
    } 

    [TestMethod] 
    [Description(
     "The Ascii-85 encoding is not susceptible to changes in character case.")] 
    [UsedImplicitly] 
    public void Ascii85IsCaseInsensitive() 
    { 
     const int kCount = 50; 

     for (var i = 0; i < kCount; i++) 
     { 
      var guid = Guid.NewGuid(); 

      // The encoding should be all upper case. A reliance 
      // on mixed case will make the generated string 
      // vulnerable to sql collation. 
      var encoded = Ascii85.Encode(guid); 

      Assert.AreEqual(
       encoded, 
       encoded.ToUpper(), 
       "The Ascii-85 encoding should produce only uppercase characters."); 
     } 
    } 
} 

Tôi hy vọng điều này giúp tiết kiệm ai đó một số rắc rối.

Ngoài ra, nếu bạn tìm thấy bất kỳ lỗi nào, hãy cho tôi biết ;-)