Representación compacta de URL de GUID/UUID?

Question

Necesito generar un GUID y guardarlo a través de una representación de cadena. La representación de cadena debe ser lo más corta posible, ya que se usará como parte de una cadena de URL ya larga.

En este momento, en lugar de utilizar la representación abcd-efgh -... normal, utilizo los bytes brutos generados y los codifica en su lugar en base64, lo que da como resultado una cadena algo más corta.

¿Pero es posible hacerlo aún más corto?

Estoy bien con perder cierto grado de exclusividad y mantener un contador, pero escanear todas las claves existentes no es una opción. Sugerencias?

Answer 1

Utilicé una codificación Ascii85 para escribir una columna Guid a una base de datos en 20 caracteres ASCII. He publicado el código de C# en caso de que sea útil. El conjunto de caracteres específico puede ser diferente para una codificación URL, pero puede elegir los caracteres que se adapten a su aplicación. Está disponible aquí: What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Answer 2

Claro, solo use una base más grande que 64. Tendrá que codificarlos usando un alfabeto personalizado, pero debería poder encontrar algunos caracteres ASCII imprimibles "url-safe".

Base64 codifica 6 bits utilizando 8, por lo que un valor GUID de 16 bytes se convierte en 22 bytes codificados. Puede reducir eso por un personaje o dos, pero no mucho más.

Answer 3

No estoy seguro si esto es factible, pero podría poner todos los GUID generados en una tabla y usar en la URL solo el índice del GUID en la tabla.

También podría reducir la longitud del guid; por ejemplo, use 2 bytes para indicar el número de días desde 2010, por ejemplo, y 4 bytes para el número de milisegundos desde el comienzo del día actual. Tendrá colisiones solo para 2 GUID generados en el mismo milisegundo. También podría agregar 2 bytes aleatorios adicionales que lo harán aún mejor.

Answer 4

Puede acercarse a esto desde la otra dirección. Produzca la representación de cadena más corta posible y asóciela en un Guid.

generar la clave utilizando un alfabeto definido de la siguiente manera:

En psuedocode:

string RandomString(char[] alphabet, int length) 
{ 
    StringBuilder result = new StringBuilder(); 
    for (int i = 0; i < length; i++) 
    result.Append(alphabet[RandomInt(0, alphabet.Length)]); 

    return result; 
} 

Si se mantiene la longitud de cadena < 16, puede simplemente hexagonal codificar el resultado y lo pasará al Guid constructor para analizar.

Answer 5

no exactamente para el mismo problema, pero muy muy cerca - He usado CRC64, Base64 eso y usted obtiene 11 bytes, CRC64 ha sido probado (no probado) para NO producir duplicados en una amplia gama de instrumentos de cuerda.

Y dado que es 64 bits de largo por definición, obtienes la clave que es la mitad del tamaño.

Para responder directamente la pregunta original, puede codificar CRC64 cualquier representación de sus GUID.

O simplemente ejecute CRC64 en la clave de negocios y tendrá 64 bits únicos que luego puede base64.

Answer 6

encontré este interesante debate: https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/

Básicamente se toma el 36 caracteres y convertirlos en 16 bytes de binario, pero primero ordenar las tres piezas temporales mediante un procedimiento almacenado:

set @uuid:= uuid(); 
select @uuid; 
+--------------------------------------+ 
| @uuid        | 
+--------------------------------------+ 
| 59f3ac1e-06fe-11e6-ac3c-9b18a7fcf9ed | 
+--------------------------------------+ 

CREATE DEFINER=`root`@`localhost` 
    FUNCTION `ordered_uuid`(uuid BINARY(36)) 
    RETURNS binary(16) DETERMINISTIC 
    RETURN UNHEX(CONCAT(SUBSTR(uuid, 15, 4),SUBSTR(uuid, 10, 4),SUBSTR(uuid, 1, 8),SUBSTR(uuid, 20, 4),SUBSTR(uuid, 25))); 

select hex(ordered_uuid(@uuid)); 
+----------------------------------+ 
| hex(ordered_uuid(@uuid))   | 
+----------------------------------+ 
| 11e606fe59f3ac1eac3c9b18a7fcf9ed | 
+----------------------------------+ 

Answer 7

(larga tiempo, pero acaba de llegar a la misma necesidad hoy)

UUID son 128 bits de largo, representados por 32 hex más 4 guiones. Si usamos un diccionario de 64 (2^6) ascii`s imprimibles, solo se trata de convertir de 32 grupos de 4 bits (longitud de un hex) a 22 grupos de 6 bits.

Aquí hay un shortner UUID. En lugar de 36 caracteres, obtienes 22, sin perder los bits originales.

https://gist.github.com/tomlobato/e932818fa7eb989e645f2e64645cf7a5

class UUIDShortner 
    IGNORE = '-' 
    BASE6_SLAB = ' ' * 22 

    # 64 (6 bits) items dictionary 
    DICT = 'a'.upto('z').to_a + 
     'A'.upto('Z').to_a + 
     '0'.upto('9').to_a + 
     ['_', '-'] 

    def self.uuid_to_base6 uuid 
     uuid_bits = 0 

     uuid.each_char do |c| 
      next if c == IGNORE 
      uuid_bits = (uuid_bits << 4) | c.hex 
     end 

     base6 = BASE6_SLAB.dup 

     base6.size.times { |i| 
      base6[i] = DICT[uuid_bits & 0b111111] 
      uuid_bits >>= 6 
     } 

     base6 
    end 
end 

# Examples: 

require 'securerandom' 
uuid = ARGV[0] || SecureRandom.uuid 
short = UUIDShortner.uuid_to_base6 uuid 
puts "#{uuid}\n#{short}" 

# ruby uuid_to_base6.rb 
# c7e6a9e5-1fc6-4d5a-b889-4734e42b9ecc 
# m75kKtZrjIRwnz8hLNQ5hd