И как сделать так, чтобы не получились ГАВНО и ЖЁПА.
Это финальный пост в моем цикле про инкрементальные и строковые идентификаторы. Мы уже разобрали, что это такое и как преобразовать инкрементальные идентификаторы в псевдослучайные числовые.
В предыдущих сериях…
Инкрементальные идентификаторы — это идентификаторы, использующие последовательные натуральные числа: 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.
Теперь посмотрим на шестнадцатеричный алфавит:
0123456789ABCDEF
С технической точки зрения его можно представить как массив из 16 символов, а числа 3, 0, 2, 14, 15 — это индексы элементов в этом массиве:
- 3 → 3
- 0 → 0
- 2 → 2
- 14 → E
- 15 → F
Но что, если мы возьмем любой другой алфавит этой же длины? Например, первую половину русского алфавита:
АБВГДЕЁЖЗИЙКЛМНО
Получится то же самое шестнадцатеричное число, но закодированное другими символами:
- 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). Однако, стоит иметь в виду, что мы убираем символы, а значит, мощность алфавита уменьшается. Тут стоит вспомнить, что с технической точки зрения строчные и прописные буквы — это разные символы, и мы можем засунуть в алфавит и те, и другие:
2356789бвгджклмнпрстфхцчшщъыьБВГДЖКЛМНПРСТФХЦЧШЩЪЫЬ
Сейчас я уже не стал его перемешивать, чтобы было нагляднее. Еще я убрал букву «З», так как ее легко спутать с тройкой.
Наше тестовое число 197359 в этом алфавите превращается в «3шЦС». Это уже лучше, чем ГАВНО и ЖЁПА.
Дополнение до минимальной длины
В принципе, задача уже выполнена, но есть еще одно улучшение, которое можно сделать. Строковые идентификаторы могут получиться любой длины, а так как мы их еще и перемешали при обфускации, то их длина не зависит от порядка. Например, какой-то пользователь может зарегистрироваться и получить идентификатор из 7 символов, а игрок сразу после него — из 1 символа. Если это какие-то онлайн игры, то профили с короткими идентификаторами могут выглядеть более ценными, а это плохо. Поэтому нужно привести идентификаторы к какой-то минимальной длине. Например, чтобы они были не от 1 до 7 символов, а от 6 до 7 — это выглядит более честно.
Но возникает вопрос: чем дополнять? Мы не можем просто взять какой-то идентификатор (например, «3шЦС» для 197359) и добавить несколько символов из того же алфавита, чтобы этот идентификатор стал длиннее, например «3шЦС5Ж». «3шЦС5Ж» — это уже совсем другой идентификатор, который занят числом 513330894.
Значит, нужно дополнять символами из какого-то другого алфавита. Например, можно убрать несколько символов из нашего текущего алфавита и собрать из них второй для дополнения до минимальной длины. Тогда наш основной алфавит будет выглядеть так:
25679бпрстфхцчшщъыьПРСТФХЦЧШЩЪЫЬ
Его мощность получается 32. А алфавит для дополнения выглядит так:
38вгджклмнБВГДЖКЛМН
Для выбора дополнительных символов никакого особого алгоритма нет, я просто беру случайные символы. Чтобы идентификатор был детерминированным, нужно взять псевдослучайную последовательность, а в качестве 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
Но я использовал схему Горнера для вычисления полиномов. Она считается более эффективной для вычисления на компьютерах.
Алгоритм готов! Именно в таком виде (только с другим алфавитом) я использую его в нашей игре, чтобы у игроков были уникальные строковые идентификаторы.
Подзаголовок ну чисто байт на клики)
Тут такая узконаправленная тема, что иначе бы никто не открыл вообще)
взорнул
а вообще статья хорошая
Ради этой фразы пост и писался.
А как сделать так, чтобы получилось...
ежи
Расскажи про Base65536
Грубо говоря, в оригинальном тексте с обычным алфавитом один символ - это один байт, т.е. один символ покрывает 256 вариантов текста. В Base65536 один символ - это 2 байта. Берем какой-нибудь текст длиной 255 символов (255 байт) и переводим в Base65536. Получается что-то такое:
𤇃𢊻𤄻嶜𤄋𤇁𡊻𤄛𤆬𠲻𤆻𠆜𢮻𤆻ꊌ𢪻𤆻邌𤆻𤊻𤅋𤲥𣾻𤄋𥆸𣊻𤅛ꊌ𤆻𤆱炼綻𤋅𤅴薹𣪻𣊻𣽻𤇆𤚢𣺻赈𤇣綹𤻈𤇣𤾺𤇃悺𢦻𤂻𤅠㢹𣾻𤄛𤆓𤦹𤊻𤄰炜傼𤞻𢊻𣲻𣺻ꉌ邹𡊻𣹫𤅋𤇅𣾻𤇄𓎜𠚻𤊻𢊻𤉛𤅫𤂑𤃃𡉌𤵛𣹛𤁐𢉋𡉻𡡫𤇠𠞗𤇡𡊄𡒌𣼻燉𣼋𦄘炸邹㢸𠞻𠦻𡊻𣈻𡈻𣈛𡈛ꊺ𠆼𤂅𣻆𣫃𤮺𤊻𡉋㽻𣺬𣈛𡈋𤭻𤂲𣈻𤭻𤊼𢈛儛𡈛ᔺТут все те же 255 байт, но размер текста теперь 128 символов - влезает в твиттер (когда там еще было ограничение 140 символов).
Ah yes, enslaved hieroglyphs