[Техпоп] Как преобразовать числовые идентификаторы в строковые с произвольным алфавитом

И как сделать так, чтобы не получились ГАВНО и ЖЁПА.

Это финальный пост в моем цикле про инкрементальные и строковые идентификаторы. Мы уже разобрали, что это такое и как преобразовать инкрементальные идентификаторы в псевдослучайные числовые.

Инкрементальные идентификаторы — это идентификаторы, использующие последовательные натуральные числа: 1, 2, 3… Их проблема в том, что они несут информацию сами по себе. Например, мы можем понять, в каком порядке регистрировались пользователи и сколько их всего.

Идентификаторы можно преобразовать так, чтобы они не содержали дополнительной информации. Самое простое — это преобразовать последовательные числа 1, 2, 3 в числа, которые выглядят как случайные. Такое преобразование называется обфускацией.

Проблемы, связанные с безопасностью, мы уже решили после обфускации. Дальнейшее преобразование нужно просто для того, чтобы сделать идентификаторы короче, а работу с ними — проще и удобнее.

Определимся с терминологией: алфавит — это множество символов, из которых составляется какой-то текст. Количество символов в алфавите называется мощностью этого алфавита.

Если перекодировать текст алфавитом с большей мощностью, то он станет короче. Обычные цифры можно считать алфавитом с мощностью 10. Мощность латинского алфавита — 26. Латинский алфавит вместе с цифрами — 36. Если использовать и строчные, и прописные, и цифры — 62. Если добавить еще символы + и /, то получим алфавит Base64. В Base64 алгоритм сложнее, чем тот, что я буду использовать, но суть похожа.

А еще есть Base65536. Он позволяет скукожить оригинальный текст так, чтобы в твиттере в одно сообщение влезало в два раза больше информации. Применение, скорее, шуточное, но все же.

Вспоминаем школьную информатику. Числа могут быть представлены в разных система счисления: двоичная (BIN), восьмеричная (OCT), десятичная (DEC) и шестнадцатеричная (HEX). Это если брать популярные. В общем случае у системы счисления может быть любое основание, ведь, по своей сути, набор цифр в системе счисления — это алфавит. В двоичной системе алфавит из двух символов (0 и 1), в десятичной — из 10 (0-9), в шестнадцатеричной — 16 (0-9, A-F).

Чтобы преобразовать десятичное число к любой другой системе счисления, нужно просто последовательно делить это число на основание нужной системы счисления и записывать остатки. Остатки в обратном порядке и будут разрядами числа в новой системе счисления.

Для примера, переведем число 197359 в шестнадцатеричную систему.

197359 = 12334 * 16 + 15

12334 = 770 * 16 + 14

770 = 48 * 16 + 2

48 = 3 * 16 + 0

3 = 0 * 16 + 3

Получаем ряд шестнадцатеричных цифр: 3, 0, 2, 14 (E), 15 (F), т.е. число 302EF.

Еще раз посмотрим наш пример с переводом числа 197359 в HEX. Самым интересным там является не итоговое число, а ряд десятичных чисел на предпоследнем этапе: 3, 0, 2, 14, 15.

Теперь посмотрим на шестнадцатеричный алфавит:

С технической точки зрения его можно представить как массив из 16 символов, а числа 3, 0, 2, 14, 15 — это индексы элементов в этом массиве:

Но что, если мы возьмем любой другой алфавит этой же длины? Например, первую половину русского алфавита:

Получится то же самое шестнадцатеричное число, но закодированное другими символами:

Т.е. 302EF в обычном HEX-алфавите превращается в ГАВНО в нашем алфавите.

До этого я писал, что десятичное число можно привести к любой системе счисления, а здесь я пишу, что можно взять любой массив символов. Вот мы и получили кодирование десятичного числа произвольным алфавитом. Возьмем, например, опять русский алфавит, но теперь целиком, и еще перемешаем его:

Получаем произвольный алфавит с мощностью 33. Закодируем число 197359 этим алфавитом:

197359 = 5980 * 33 + 19 → А

5980 = 181 * 33 + 7 → П

181 = 5 * 33 + 16 → Ё

5 = 0 * 33 + 5 → Ж

Получаем ЖЁПА в выбранном алфавите.

В текущем виде наш алфавит содержит все символы русского языка, а значит могут получиться какие-то слова. Вряд ли кто-то захочет, чтобы его профиль на DTF имел такую ссылку:

Пруфов у меня нет, но есть мнение, что при генерировании строковых идентификаторов на YouTube они проверяют новые идентификаторы на то, есть ли в них слова из какого-то словаря, и, если есть, генерируют другой. Это может быть правдой, потому что у них огромная избыточность идентификаторов — просто генерируй любой другой, пока не понравится. Возможных идентификаторов так много, что они не закончатся, даже если выкидывать неподходящие.

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

Самый простой способ сделать это — убрать гласные и цифры, похожие на гласные (0, 1, иногда 4). Также можно убрать согласные, которые содержатся в опасных словах (f, n и g). Однако, стоит иметь в виду, что мы убираем символы, а значит, мощность алфавита уменьшается. Тут стоит вспомнить, что с технической точки зрения строчные и прописные буквы — это разные символы, и мы можем засунуть в алфавит и те, и другие:

Сейчас я уже не стал его перемешивать, чтобы было нагляднее. Еще я убрал букву «З», так как ее легко спутать с тройкой.

Наше тестовое число 197359 в этом алфавите превращается в «3шЦС». Это уже лучше, чем ГАВНО и ЖЁПА.

В принципе, задача уже выполнена, но есть еще одно улучшение, которое можно сделать. Строковые идентификаторы могут получиться любой длины, а так как мы их еще и перемешали при обфускации, то их длина не зависит от порядка. Например, какой-то пользователь может зарегистрироваться и получить идентификатор из 7 символов, а игрок сразу после него — из 1 символа. Если это какие-то онлайн игры, то профили с короткими идентификаторами могут выглядеть более ценными, а это плохо. Поэтому нужно привести идентификаторы к какой-то минимальной длине. Например, чтобы они были не от 1 до 7 символов, а от 6 до 7 — это выглядит более честно.

Но возникает вопрос: чем дополнять? Мы не можем просто взять какой-то идентификатор (например, «3шЦС» для 197359) и добавить несколько символов из того же алфавита, чтобы этот идентификатор стал длиннее, например «3шЦС5Ж». «3шЦС5Ж» — это уже совсем другой идентификатор, который занят числом 513330894.

Значит, нужно дополнять символами из какого-то другого алфавита. Например, можно убрать несколько символов из нашего текущего алфавита и собрать из них второй для дополнения до минимальной длины. Тогда наш основной алфавит будет выглядеть так:

Его мощность получается 32. А алфавит для дополнения выглядит так:

Для выбора дополнительных символов никакого особого алгоритма нет, я просто беру случайные символы. Чтобы идентификатор был детерминированным, нужно взять псевдослучайную последовательность, а в качестве seed'а задать ей оригинальный числовой идентификатор.

С этими изменениями наше число 197359 превращается в «п2Фщ», а с дополнением до минимальной длины — в «п2Фщкж».

Мы научились кодировать числовые идентификаторы произвольным алфавитом, но иногда нам нужно полученную строку преобразовать обратно. Для это просто делаем все в обратном порядке:

"п2Фщкж" → "п2Фщ"

"п2Фщ" → 6, 0, 23, 15

0 * 32 + 6 = 6

6 * 32 + 0 = 192

192 * 32 + 23 = 6167

6167 * 32 + 15 = 197359

Вообще, при переводе какой-то системы в десятичную в школьной информатике обычно используется немного другая запись:

6 * 32 ^ 3 + 0 * 32 ^ 2 + 23 * 32 ^ 1 + 15 * 32 ^ 0

Но я использовал схему Горнера для вычисления полиномов. Она считается более эффективной для вычисления на компьютерах.

Алгоритм готов! Именно в таком виде (только с другим алфавитом) я использую его в нашей игре, чтобы у игроков были уникальные строковые идентификаторы.

#техпоп #приходько_техпоп