Что такое Base62?
Base62 — это способ записать число, используя только символы, которые переживут вставку куда угодно: десять цифр, 26 заглавных букв и 26 строчных букв. Никакой пунктуации, пробелов, символа дополнения, ничего, что нужно экранировать перед тем, как попасть в URL, имя файла, cookie или ключ базы данных. Десять плюс 26 плюс 26 — это 62, отсюда и название.
Версия на 30 секунд: число 12345 записывается как 3D7, а 1234567890 — как 1LY7VK. Обратный путь — та же операция в обратном порядке, и ему нужен точно тот алфавит, который создал код: другой алфавит превращает те же шесть символов в другое число без всякого сообщения об ошибке.
Эта страница выполняет две связанные задачи, и различие между ними важнее любой другой вещи на этой странице:
- Целочисленный режим воспринимает вход как число. Десятичный ID вроде
1234567890 становится 1LY7VK, а ведущие нули входа не являются частью значения, поэтому они не возвращаются. - Байтовый режим воспринимает вход как строку байтов. Байты читаются как одно огромное целое в порядке big-endian и затем делятся на 62 — та же арифметика, но для другой величины. Здесь число ведущих нулевых байтов сохраняется: один нулевой байт — один нулевой символ.
Откуда берётся 62 и во что это обходится
62 — не степень двойки, и этот единственный факт определяет всё остальное. Привычные кодировки строятся нарезкой входа на фиксированные группы бит: 4 бита печатаются одним шестнадцатеричным символом, 6 бит — одним символом Base64, 5 бит — одним символом Base32. Base62 так не может, потому что никакое целое число бит не укладывается в символ из 62 значений: 5 бит называют только 32 значения, 6 бит — 64. Поэтому Base62 идёт через арифметику: читает весь вход как одно целое и печатает его в основании 62.
Один символ тогда несёт log2(62) = 5,954 бита, что очень близко к 6 у Base64, а в десятичном режиме один символ заменяет log62(10) = 1,792 десятичной цифры. Несколько следствий, которые полезно знать, прежде чем выбирать длину:
| Длина кода | Значения, которые он может назвать | На практике |
|---|
| 4 символа | 624 = 14 776 336 | Достаточно для счётчика, который остаётся меньше восьми знаков, и помещается в пространство, равное номеру телефона. |
| 6 символов | 626 = 56 800 235 584 | Обычный вид кода ID. Десятизначный десятичный ID помещается в шесть символов. |
| 7 символов | 627 = 3 521 614 606 208 | Выше диапазона 32-битного счётчика на два порядка, в ширине короткого слага ссылки. |
| 11 символов | 6211 = 52 036 560 683 837 093 888 | Больше 264 = 18 446 744 073 709 551 616, поэтому полное 64-битное число помещается в одиннадцать символов. |
Если считать в обратную сторону, 1000 десятичных цифр требуют около 558 символов, а 4096 десятичных цифр — 2285. Экономия реальна, но ограничена: Base62 сокращает десятичное число примерно на 44%, и никогда не обгоняет самые плотные печатные кодировки, потому что 5,954 бита на символ просто меньше, чем 6,4 или 6,5.
Целочисленный режим: что происходит с ведущими нулями
У целого числа есть один канонический письменный вид, и он начинается с нулевого символа алфавита, то есть 0 в двух порядках с цифрами впереди и A в порядке с буквами впереди. Всё слева от первого значащего символа — это дополнение, а дополнение не входит в значение: 00012345 и 12345 оба становятся 3D7. Если нужна фиксированная ширина — например, семисимвольный код, который должен выравниваться в столбце, — поле страницы Дополнить результат до фиксированной ширины повторяет нулевые символы, пока не достигнута ширина, поэтому 12345 при ширине 7 печатается как 00003D7 в алфавите с цифрами впереди и как AAAADNH в алфавите с буквами впереди. Дополнение косметическое: эти ведущие символы не добавляют ничего к значению, и декодирование любой из строк возвращает 12345, потому что 0 × 626 и 0 × 625 равны нулю независимо от того, каким символом записан ноль.
Поэтому декодирование дополненной строки тоже работает, и страница сообщает, сколько ведущих символов были нулевыми, чтобы разница между «код семь символов» и «значению нужно три символа» никогда не была загадкой.
Байтовый режим: та же арифметика для строки байтов
Байтовый режим читает байты входа как одно целое число в порядке big-endian — вся строка байтов рассматривается как одно число, какой бы длинной она ни была, — и печатает это число в основании 62. Поскольку байт содержит 8 бит, а символ называет 5,954 из них, байтовый режим не является сжатием: ему нужно около 134% размера входа, немного хуже, чем 133% у Base64. В примере из 92 байт, использованном в таблице размеров выше, 92 байта печатаются как 124 символа Base62, а Base64 тоже печатает 124 (123 из них до заполнения =). Base62 проигрывает Base64 по плотности и выигрывает по безопасности символов — именно этот компромисс намеренно делает каждый короткий код ссылки или приглашения.
Ведущие нулевые байты сохраняются, и это легко сделать неверно в обоих направлениях. Два ведущих нулевых байта, за которыми следует 0x01, печатаются как 001 в алфавите с цифрами впереди и как AAB в алфавите с буквами впереди, потому что ведущие символы означают ноль и их по одному на каждый нулевой байт. Строка байтов из одного 0x00 печатается как один символ 0, а из одного 0x01 — как 1. Это единственное место, где байтовый режим и целочисленный выглядят по-разному, хотя работают одним и тем же алгоритмом.
Цена всего этого в том, что байтовый режим наследует квадратичное время арифметики: 1024 байта оцениваются примерно в треть секунды, а 2048 байт — примерно в 1,3 секунды, те же цифры, что даёт таблица ограничений выше. Поэтому байтовый режим здесь ограничен 2048 байтами на вход и 2048 символами на выход — 2048 байт печатаются примерно как 2751 символ, поэтому примерно 1520 байт — самая большая полезная нагрузка, которая проходит обратное преобразование через эту страницу, — и поэтому байтовый режим на этой странице служит справочником для небольших значений, а не заменой Base64 или Base91 для реальных файлов.
Три алфавита и почему алфавит — это всё
Символы алфавита — фиксированная последовательность, а значение символа — его позиция в этой последовательности. Перемещение последовательности меняет смысл каждого символа. Три порядка широко используются, и ниже одно и то же число записано тремя способами в каждом из них:
| Десятичное | 0-9, затем A-Z, затем a-z | 0-9, затем a-z, затем A-Z | A-Z, затем a-z, затем 0-9 |
|---|
| 0 | 0 | 0 | A |
| 61 | z | Z | 9 |
| 62 | 10 | 10 | BA |
| 12 345 | 3D7 | 3d7 | DNH |
| 1 234 567 890 | 1LY7VK | 1ly7vk | BViHfU |
Если читать последние три столбца как один алфавит, это единая связная схема. Если читать их как взаимозаменяемые, она рассыпается, потому что декодирование слепо к алфавиту самым худшим образом: любой символ входа есть во всех трёх алфавитах, поэтому неверный алфавит не даёт никакой ошибки, а только другое число.
| Код | Читается как 0-9 A-Z a-z | Читается как 0-9 a-z A-Z | Читается как A-Z a-z 0-9 |
|---|
| 3D7 | 12 345 | 13 957 | 211 665 |
| 1LY7VK | 1 234 567 890 | 1 624 950 792 | 48 723 527 772 |
Регистр — вторая, более резкая версия той же ловушки. Base62 чувствителен к регистру в каждом порядке, поэтому перевод кода в строчные молча переписывает его: 1LY7VK — это 1 234 567 890 в алфавите с цифрами впереди, тогда как 1ly7vk — это 1 624 950 792 в том же алфавите — и оно случайно равно 1 234 567 890 в алфавите «цифры, затем строчные», потому что этот порядок — ровно алфавит с цифрами впереди с поменянными местами регистрами букв. Нулевой символ тоже не общий: два порядка с цифрами впереди пишут ноль как 0, а порядок с буквами впереди пишет его как A, так что этот алфавит вообще не начинается с цифры.
Base62 рядом с другими кодировками
| Кодировка | Бит на символ | Размер относительно входа | Примечания |
|---|
| Base16 (hex) | 4 | 200% | Два символа на байт, тривиально читается, алфавита искать не нужно. |
| Base32 | 5 | 160% | Без учёта регистра и безопасна для продиктовывания, самая расточительная в группе. |
| Base36 (0-9 a-z) | ~5,17 | ~155% | Только цифры и строчные буквы, поэтому переживает конвейер с приведением к нижнему регистру. 12345 — это 9ix. |
| Base58 | ~5,86 | ~137% | Выбран для адресов, а не для плотности: четыре похожих символа удалены из алфавита, а не упорядочены. См. Base32 / Base58. |
| Base62 | ~5,95 | ~134% | Каждый символ — цифра или буква, поэтому ничего никогда не экранируется. Плотность между Base58 и Base64. |
| Base64 | 6 | 133% | По умолчанию везде, ценой символов +, / и =, трёх символов, которые требуют экранирования. См. конвертер Base64. |
| Ascii85 / Base85 | 6,4 | 125% | 5 символов на 4 байта, но делит на 85, а его алфавит требует кавычек. См. Ascii85. |
| Base91 | ~6,5 | ~123% | Самая плотная из них, и её вывод наименее безопасно вставлять без экранирования. См. Base91. |
Проценты — асимптотические затраты, округлённые; измеренные числа символов для одного реального входа из 92 байт приведены в таблице размеров выше на этой странице. В целочисленном режиме сравнение идёт в обратную сторону, потому что вход — это десятичный текст, а не байты: там Base62 примерно на 44% короче цифр, которые он заменяет, а Base36 — примерно на 36% короче, поэтому ID-код обычно Base62 или Base36, а не Base58.
Чем Base62 не является
- Не стандарт. Нет RFC и нет спецификации. Ни один орган стандартизации никогда не определял Base62, поэтому алфавит не гарантирован, и поэтому эта страница выводит все три порядка вместо того, чтобы молча выбрать один.
- Не шифрование. Это смена основания, и ничего больше. Любой, кто знает алфавит, обращает его за один проход, и здесь нет ни ключа, ни соли, ни какой-либо секретности.
- Не сжатие. Байтовый режим увеличивает данные примерно на треть. Целочисленный режим лишь выглядит как сжатие, потому что десятичный текст — неэффективный способ записи числа вообще.
- Не без учёта регистра. Base32 можно перевести в строчные и прочитать обратно; Base62 нельзя. Код, который проходит через систему, нормализующую регистр, — это повреждённый код.
- Не самопроверяемый. Нет контрольной суммы и нет контрольного символа, поэтому один неверный символ даёт правдоподобный на вид результат с другим значением. Если это важно, порядок Bitcoin поставляется с контрольной суммой — см. раздел Base58Check в Base32 / Base58.
- Не фиксированной длины. Число символов растёт вместе со значением, поэтому счётчик, начинающийся с 1 и доходящий до 627, проходит путь от одного символа до восьми. Дополняйте до фиксированной ширины, когда нужен стабильный столбец.
Ловушки, которые действительно кусают
- Алфавит отвечает на девять из десяти загадок. Если другой инструмент выдаёт другой код для того же числа, сравните два алфавита символ за символом, прежде чем подозревать ошибку. Таблица выше показывает одно значение в трёх алфавитах, и все три верны.
- Неверный алфавит ломается молча. Для него нет пути ошибки:
3D7 декодируется в 12 345, 13 957 или 211 665 в зависимости только от того, какой порядок предполагается. Проверьте первый символ, который чаще всего является нулевым дополнением, и проверьте, стоят ли цифры или буквы впереди алфавита. - Ведущие нули означают две разные вещи. В целочисленном режиме
00012345 и 12345 — одно и то же число и печатаются одинаково. В байтовом режиме ведущий нулевой байт — это данные, и он печатается как один лишний нулевой символ. Удаление одного из этих символов меняет строку байтов. - Нормализация регистра уничтожает код. Адрес электронной почты, имя хоста или путь Windows может быть приведён к нижнему регистру при передаче. Код Base62 так не выживает, и именно поэтому Base36 всё ещё существует.
- Длинные входы медленные, а не только большие. Преобразование — арифметика над всем входом сразу, поэтому удвоение длины входа учетверяет время. Эта страница отказывается от входов сверх измеренных пределов, вместо того чтобы зависнуть; таблица размеров выше даёт измеренные числа.
- Строка Base62 ничего не доказывает. Поскольку почти любая строка из цифр и букв декодируется без жалоб, произвольный слаг URL декодируется в какое-то число. Код что-то значит, только если система, которая его выдала, также хранит соответствие.
Краткие ответы
«Почему другой инструмент Base62 даёт другой код для того же числа?»
Потому что алфавит отличается. У Base62 нет спецификации, с которой можно было бы не согласиться, поэтому реализации выбирают порядок: сначала цифры и заглавные, сначала цифры и строчные или сначала буквы, затем цифры. Переключите селектор алфавита вверху этой страницы, чтобы увидеть все три ответа рядом.
«Безопасен ли Base62 в URL?»
Да, во всех трёх порядках. Все 62 символа — неэкранированные буквы и цифры, поэтому ни один из них не разворачивается в процентную тройку в строке запроса и ни один не завершает URL, сегмент пути или атрибут HTML. Именно поэтому короткие ссылки делают на Base62, а не на Base64.
«Что меньше, Base62 или Base64?»
Для байтов Base64 немного меньше: около 133% от входа против примерно 134%. На примере из 92 байт выше они совпадают по 124 символам. Для десятичных чисел Base62 сокращает текст примерно на 44%, и вот где практическая выгода.
«Могу ли я декодировать строку Base64 с помощью этой страницы?»
Нет, и она не скажет, что не справилась. Два алфавита совпадают по всем 62 символам, поэтому строка Base64 обычно тоже «допустимый» вход здесь и просто декодируется в другое число. Для Base64 используйте Base64.
«Есть ли у кода Base62 максимальная длина?»
Нет, в теории у алгоритма нет границы. На практике эта страница останавливается на 4096 десятичных цифрах, или на 2048 байтах, потому что арифметика за ней квадратична, и вкладка зависла бы без пояснения на экране. Таблица ограничений выше на этой странице перечисляет измеренные числа.
«Откуда мне знать, что результат на этой странице верен?»
Нажмите Самопроверку. Она запускает все задокументированные примеры, каждую длину байтов от 0 до 64 и набор десятичных чисел во всех трёх алфавитах, сравнивает возвращённые значения с тем, что было на входе, и повторно проверяет, что все 62 символа каждого алфавита безопасны в URL. Кнопка «Пример» дополнительно сравнивает три свои результата со значениями, записанными в файле данных этой страницы, которые были проверены по второй, независимой реализации большого целого, хранящейся в инструментах тестирования этого сайта.
Стандарты и источники
Здесь нечего реализовывать по стандарту: Base62 — соглашение, а не спецификация, а три алфавита, приведённых выше, — те, что встречаются в реальном ПО. Эта страница реализует его собственными процедурами большого целого сайта, написанными простой арифметикой над массивами цифр, чтобы ни один размер никогда не был ограничен типом числа JavaScript.
Текст страницы написан для этого сайта. Каждый пример на этой странице был получен кодом самой страницы, а затем проверен по второй, независимой реализации с нативными большими целыми, которая хранится в инструментах тестирования этого сайта; та же реализация проверила таблицы примеров и размеров в файле данных.
