algorithm guid

algorithm - ¿Cuál es la forma más eficiente de codificar un GUID arbitrario en ASCII legible(33-127)?



uuid npm (7)

La representación de cadena estándar de GUID toma alrededor de 36 caracteres. Lo cual es muy bueno, pero también realmente derrochador. Me pregunto cómo codificarlo de la manera más breve posible usando todos los caracteres ASCII en el rango 33-127. La implementación ingenua produce 22 caracteres, simplemente porque 128 bits / 6 bits rinde 22.

La codificación de Huffman es mi segunda mejor opción, la única pregunta es cómo elegir los códigos ...

La codificación debe ser sin pérdida, por supuesto.

¿Un GUID arbitrario ? El algoritmo "ingenuo" producirá resultados óptimos. La única forma de comprimir más un GUID es hacer uso de patrones en los datos excluidos por su restricción "arbitraria".

Esta es una vieja pregunta, pero tuve que resolverla para que un sistema en el que estaba trabajando fuera compatible con versiones anteriores.

El requisito exacto era un identificador generado por el cliente que se escribiría en la base de datos y se almacenaría en una columna única de 20 caracteres. Nunca se mostró al usuario y no se indexó de ninguna manera.

Como no podía eliminar el requisito, realmente quería usar un Guid (que es estadísticamente único ) y si podía codificarlo sin pérdidas en 20 caracteres, sería una buena solución dadas las limitaciones.

Ascii-85 le permite codificar 4 bytes de datos binarios en 5 bytes de datos Ascii. Por lo tanto, un guid de 16 bytes se ajustará a 20 caracteres Ascii utilizando este esquema de codificación. Un Guid puede tener 3.1962657931507848761677563491821e + 38 valores discretos mientras que 20 caracteres de Ascii-85 pueden tener 3.8759531084514355873123178482056e + 38 valores discretos.

Al escribir en la base de datos, me preocupaba el truncamiento, por lo que no se incluyen caracteres en blanco en la codificación. También tuve problemas con la collation , a la que me referí al excluir los caracteres en minúsculas de la codificación. Además, solo se pasaría a través de un comando paramaterizado , por lo que cualquier carácter especial de SQL se escaparía automáticamente.

He incluido el código C # para realizar la codificación y decodificación Ascii-85 en caso de que ayude a alguien por ahí. Obviamente, dependiendo de tu uso, es posible que debas elegir un conjunto de caracteres diferente ya que mis limitaciones me hicieron elegir algunos caracteres inusuales como ''ß'' y ''Ø'', pero esa es la parte fácil:

/// <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; } }

Además, aquí están las pruebas unitarias. No son tan exhaustivos como me gustaría, y no me gusta el no determinismo de dónde se Guid.NewGuid() , pero deberían ayudarte a empezar:

/// <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."); } } }

Espero que esto le ahorre a alguien un problema.

Además, si encuentras algún error, házmelo saber ;-)

Tiene 95 caracteres disponibles, por lo tanto, más de 6 bits, pero no tanto como 7 (en realidad, alrededor de 6,57). Podría usar 128 / log2 (95) = alrededor de 19.48 caracteres, para codificar en 20 caracteres. Si guardar 2 caracteres en la forma codificada vale la pérdida de legibilidad para usted, algo así como (pseudocódigo):

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);

que es básicamente el código genérico de "codificar un número en alguna base", excepto que no hay necesidad de invertir los "dígitos" ya que la orden es arbitraria de todos modos (y little-endian es más directo y natural). Recuperar el guid de la cadena codificada es, de manera muy similar, el cálculo polinomial en la base 95 (después de restar 33 de cada dígito por supuesto):

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

esencialmente utilizando el enfoque de Horner para la evaluación polinomial.

Usar el rango completo de 33 (¿qué pasa wirh space, por cierto?) A 127 le da 95 caracteres posibles. Expresando los 2^128 valores posibles de guid en la base 95 se usarán 20 caracteres. Esto (módulo como eliminar nybbles que será constante) es lo mejor que puedes hacer. Ahórrese el problema - use la base 64.

Suponiendo que todos sus GUID están siendo generados por el mismo algoritmo, puede guardar 4 bits al no codificar el algoritmo nibble, antes de aplicar cualquier otra codificación: - |