Как сократить UUID?

Question

В проекте мне приходится иметь дело с UUID в формате v4, например:

931d4657-2e07-477f-be0c-5dd02906a516

В принципе, с ними все в порядке, они просто слишком длинные, чтобы набирать их вручную. Поэтому я думаю о том, как их сократить, но не теряя возможности вернуться к исходному UUID. Так что просто учесть первые n байтов не вариант; -)

Моя первая идея состояла в том, чтобы представить его как символы Юникода вместо шестнадцатеричных кодов, но это приводит к непечатным (и не типизированным) символам. Так что это тоже не вариант.

Тогда я думаю о кодировках Base64 (Base58, ...), но они на самом деле не делают вещи заметными короче (у меня нет конкретной целевой длины, я просто хочу, чтобы это было на соответствующее количество символов меньше, и сохраняю 2 символа не то, что я имею в виду; -)).

Есть ли хитрый трюк для этого, сохраняя при этом возможность вернуться к UUID? У кого-нибудь есть идея?

Answer 1

UUID являются 128-битными числами; шестнадцатеричная форма является просто представлением для использования человеком, а не особенно плотной с 3,55 битами на символ. Потерять тире, и он уходит до 4 бит на символ.

Используйте base64 вместо base16, и вы получите 6 бит на символ для 22 всего. Это примерно так хорошо, как вы можете сделать и сделать его читаемым человеком. На самом деле вы можете получить около 7 бит на байт, что позволит сократить на 1-2 байта больше, но это значительно больше полноты (т. Е. Риска), которая не может быть оправдана для такого небольшого усиления.

Математически, это настолько далеко, насколько вы можете пойти и все же быть в состоянии совершить круговое путешествие. Если вам все еще нужно укорочение, вы должны отказаться от этого - что, вероятно, имеет другие последствия для вашего общего дизайна.

Answer 2

UUID имеют длину 128 бит (16 байт). Есть некоторые биты, которые можно удалить здесь, если вы отбросите версию и вариант; но я не думаю, что это вариант в вашем случае (также вы можете безопасно удалить только 6 бит, см. здесь ).

Использование base64-кодирования уменьшит до 40%

# example uses Ruby
SecureRandom.base64(16) # => UBm-_zkz20ka6dOAA8dkMg
SecureRandom.uuid       # => 3754e815-87fe-4872-8d9b-ae529607c277

В своем комментарии вы написали, что это идентификатор ваших пользователей. Так что, может быть, вы можете работать с укороченной версией в ваших интерфейсах, подобно тому, как git обрабатывает короткие SHA. Это зависит от количества объектов, которые вы хотите обработать, но вы должны быть в состоянии значительно уменьшить «дескриптор» и при этом иметь очень низкую вероятность столкновения. В случае коллизии вы можете попросить пользователя предоставить больше идентификатора.