¿Representación de URL compacta de GUID/UUID?

uuid npm

Question

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

En este momento, en lugar de usar la representación abcd-efgh -... normal, uso los bytes en bruto generados y los codificados en base64 en su lugar, lo que resulta en una cadena algo más corta.

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

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

Answer 1

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

Los UUID tienen una longitud de 128 bits, representados por 32 hex más 4 guiones. Si usamos un diccionario de 64 (2 ^ 6) ascii imprimibles, es solo una cuestión de convertir de 32 grupos de 4 bits (longitud de un hex) a 22 grupos de 6 bits.

Aquí hay un corto 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

Answer 2

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

Base64 codifica 6 bits usando 8, por lo que un valor GUID de 16 bytes se convierte en 22 bytes codificados. Es posible que puedas reducir eso en uno o dos personajes, pero no mucho más.

Answer 3

Me pareció interesante esta discusión: https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/

Básicamente, toma los 36 caracteres y los convierte en 16 bytes de binario, pero primero ordena las tres piezas temporales utilizando 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 4

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

También puede 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 puede agregar 2 bytes más aleatorios que lo harán aún mejor.

Answer 5

Podrías acercarte a esto desde la otra dirección. Produce la representación de cadena más corta posible y mapéala en un Guid.

Genere la clave utilizando un alfabeto definido como se muestra a continuación:

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 mantiene la longitud de la cadena <16, puede simplemente codificar en hexadecimal el resultado y pasarlo al constructor Guid para analizar.

Answer 6

Utilicé una codificación Ascii85 para escribir un Guid en una columna de base de datos en 20 caracteres ASCII. He publicado el código C # en caso de que sea útil. El conjunto de caracteres específico puede ser diferente para una codificación de URL, pero puede elegir los caracteres que se adapten a su aplicación. Está disponible aquí: ¿Cuál es la forma más eficiente de codificar un GUID arbitrario en ASCII legible (33-127)?

Answer 7

no exactamente por el mismo problema, pero muy cerca. He usado CRC64, Base64, y obtienes 11 bytes. CRC64 ha sido probado (no probado) para NO producir duplicados en una amplia gama de cadenas.

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

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

O simplemente ejecute CRC64 en la clave de negocios y tendrá un objeto único de 64 bits que luego podrá basar en 64.