URL-компактное представление GUID / UUID?

Question

Мне нужно сгенерировать GUID и сохранить его через строковое представление.Строковое представление должно быть как можно короче, поскольку оно будет использоваться как часть уже длинной строки URL.

Прямо сейчас, вместо использования обычного представления abcd-efgh -..., я используюгенерируются необработанные байты и вместо них кодируется base64, что приводит к несколько более короткой строке.

Но возможно ли сделать ее еще короче?

Я в порядкес потерей некоторой степени уникальности и сохранением счетчика, но сканирование всех существующих ключей не вариант.Предложения?

Answer 1

Я использовал кодировку Ascii85 для записи Guid в столбец базы данных из 20 символов ASCII. Я разместил код C # на случай, если он будет полезен. Конкретный набор символов может отличаться для кодировки URL, но вы можете выбрать любой символ, который подходит вашему приложению. Это доступно здесь: Каков наиболее эффективный способ кодирования произвольного GUID в читаемый ASCII (33-127)?

Answer 2

Конечно, просто используйте базу больше 64. Вам придется кодировать их, используя собственный алфавит, но вы сможете найти еще несколько «безопасных для url» печатных символов ASCII.

Base64 кодирует 6 бит, используя 8, поэтому 16-байтовое значение GUID становится 22-байтовым.Вы можете уменьшить это на символ или два, но не намного.

Answer 3

Я не уверен, что это возможно, но вы можете поместить все сгенерированные GUID в таблицу и использовать в URL только индекс GUID в таблице.

Вы также можете уменьшитьдлина guid - например, используйте 2 байта, чтобы указать количество дней с 2010 года, например, и 4 байта для количества миллисекунд с начала текущего дня.У вас будут коллизии только для 2 GUID, сгенерированных за одну и ту же миллисекунду.Вы также можете добавить еще 2 случайных байта, которые сделают это еще лучше.

Answer 4

(долгое время, но сегодня возникла такая же потребность)

UUID имеют длину 128 битов и представлены 32 шестнадцатеричными плюс 4 дефисами.Если мы используем словарь из 64 (2 ^ 6) печатаемых ascii`s, это всего лишь вопрос преобразования 32 групп по 4 бита (длина шестнадцатеричного числа) в 22 группы по 6 бит.

Здесьявляется UUID.Вместо 36 символов вы получаете 22 без потери оригинальных битов.

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 5

Мне показалось интересным это обсуждение: https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/

По сути, вы берете 36 символов и превращаете их в 16 байт двоичного файла, но сначала сортируете три временных фрагмента, используя хранимую процедуру:

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 6

Вы можете подойти к этому с другой стороны. Создайте кратчайшее возможное строковое представление и отобразите его в Guid.

Сгенерируйте ключ, используя определенный алфавит, как показано ниже:

В псевдокоде:

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

Если оставить длину строки <16, вы можете просто закодировать результат в шестнадцатеричном формате и передать его конструктору Guid для анализа.

Answer 7

не для точно такой же проблемы, но очень и очень близко - я использовал CRC64, Base64, и вы получаете 11 байтов, CRC64 был протестирован (не доказан), чтобы НЕ создавать дубликаты для широкого диапазона строк.

И поскольку он по определению имеет длину 64 бита, вы получаете ключ, который в два раза меньше.

Чтобы прямо ответить на исходный вопрос - вы можете CRC64 кодировать любое представление ваших GUID.

Или просто запустить CRC64 для бизнес-ключа, и у вас будет 64-битная уникальная вещь, которую вы сможете затемbase64.