Как преобразовать целое число в самую короткую URL-безопасную строку в Python?
Я хочу кратчайший способ представления целого числа в URL. Например, 11234 можно сократить до 2be2, используя шестнадцатеричное. Поскольку base64 использует кодировку из 64 символов, должна быть возможность представлять целое число в base64, используя даже меньше символов, чем шестнадцатеричное. Проблема в том, что я не могу найти самый чистый способ преобразования целого числа в base64 (и обратно) с использованием Python.
Модуль base64 имеет методы для работы с байтовыми строками - поэтому, возможно, одним из решений будет преобразование целого числа в его двоичное представление в виде строки Python... но я тоже не уверен, как это сделать.
15 ответов
Этот ответ по духу похож на ответ Дугласа Лидера со следующими изменениями:
- Он не использует реальный Base64, так что нет никаких дополнительных символов
Вместо того, чтобы сначала преобразовать число в байтовую строку (основание 256), оно преобразует его непосредственно в основание 64, что позволяет вам представлять отрицательные числа, используя знак знака.
import string ALPHABET = string.ascii_uppercase + string.ascii_lowercase + \ string.digits + '-_' ALPHABET_REVERSE = dict((c, i) for (i, c) in enumerate(ALPHABET)) BASE = len(ALPHABET) SIGN_CHARACTER = '$' def num_encode(n): if n < 0: return SIGN_CHARACTER + num_encode(-n) s = [] while True: n, r = divmod(n, BASE) s.append(ALPHABET[r]) if n == 0: break return ''.join(reversed(s)) def num_decode(s): if s[0] == SIGN_CHARACTER: return -num_decode(s[1:]) n = 0 for c in s: n = n * BASE + ALPHABET_REVERSE[c] return n
>>> num_encode(0)
'A'
>>> num_encode(64)
'BA'
>>> num_encode(-(64**5-1))
'$_____'
Несколько примечаний:
- Вы могли бы (незначительно) повысить удобочитаемость чисел base-64, поместив string.digits первым в алфавите (и сделав символ знака '-'); Я выбрал порядок, который я сделал, основываясь на urlsafe_b64encode Python.
- Если вы кодируете много отрицательных чисел, вы могли бы повысить эффективность, используя знаковый бит или дополнение один / два вместо знакового символа.
- Вы должны иметь возможность легко адаптировать этот код к различным базам, изменяя алфавит, либо ограничивая его только буквенно-цифровыми символами, либо добавляя дополнительные "безопасные для URL" символы.
- Я бы рекомендовал в большинстве случаев не использовать представление, отличное от base 10, в URI - это добавляет сложности и усложняет отладку без значительной экономии по сравнению с издержками HTTP - если только вы не собираетесь использовать что-то вроде TinyURL-esque.
Все ответы, касающиеся Base64, являются очень разумными решениями. Но они технически неверны. Чтобы преобразовать целое число в кратчайшую возможную безопасную строку URL-адреса, вам нужно получить базовое значение 66 (имеется 66 безопасных символов URL-адреса).
Этот код выглядит так:
from io import StringIO
import urllib
BASE66_ALPHABET = u"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_.~"
BASE = len(BASE66_ALPHABET)
def hexahexacontadecimal_encode_int(n):
if n == 0:
return BASE66_ALPHABET[0].encode('ascii')
r = StringIO()
while n:
n, t = divmod(n, BASE)
r.write(BASE66_ALPHABET[t])
return r.getvalue().encode('ascii')[::-1]
Вот полная реализация с исходным кодом и готовым к установке pip-пакетом:
Вам, вероятно, не нужна настоящая кодировка base64 для этого - она будет добавлять отступы и т. Д., Потенциально даже приводя к большим строкам, чем hex для небольших чисел. Если нет необходимости взаимодействовать с чем-либо еще, просто используйте свою собственную кодировку. Например. вот функция, которая будет кодировать на любую базу (обратите внимание, что цифры на самом деле сначала сохраняются наименее значимыми, чтобы избежать дополнительных вызовов reverse():
def make_encoder(baseString):
size = len(baseString)
d = dict((ch, i) for (i, ch) in enumerate(baseString)) # Map from char -> value
if len(d) != size:
raise Exception("Duplicate characters in encoding string")
def encode(x):
if x==0: return baseString[0] # Only needed if don't want '' for 0
l=[]
while x>0:
l.append(baseString[x % size])
x //= size
return ''.join(l)
def decode(s):
return sum(d[ch] * size**i for (i,ch) in enumerate(s))
return encode, decode
# Base 64 version:
encode,decode = make_encoder("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/")
assert decode(encode(435346456456)) == 435346456456
Это дает преимущество в том, что вы можете использовать любую базу по своему усмотрению, просто добавляя соответствующие символы в базовую строку кодировщика.
Обратите внимание, что выгоды для более крупных баз не будут такими большими. Base 64 уменьшит только размер до 2/3rds базы 16 (6 бит / символ вместо 4). Каждое удвоение добавляет только один бит на символ. Если у вас нет реальной необходимости уплотнять вещи, использование шестнадцатеричного кода, вероятно, будет самым простым и быстрым вариантом.
Кодировать n:
data = ''
while n > 0:
data = chr(n & 255) + data
n = n >> 8
encoded = base64.urlsafe_b64encode(data).rstrip('=')
Расшифровать s:
data = base64.urlsafe_b64decode(s + '===')
decoded = 0
while len(data) > 0:
decoded = (decoded << 8) | ord(data[0])
data = data[1:]
В том же духе, что и для некоторых "оптимальных" кодировок, вы можете использовать 73 символа в соответствии с RFC 1738 (фактически 74, если вы считаете "+" пригодным для использования):
alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_`\"!$'()*,-."
encoded = ''
while n > 0:
n, r = divmod(n, len(alphabet))
encoded = alphabet[r] + encoded
и расшифровка:
decoded = 0
while len(s) > 0:
decoded = decoded * len(alphabet) + alphabet.find(s[0])
s = s[1:]
Легкий бит - это преобразование байтовой строки в безопасный для сети base64:
import base64
output = base64.urlsafe_b64encode(s)
Хитрый бит - это первый шаг - преобразовать целое число в байтовую строку.
Если ваши целые числа малы, лучше их кодировать в шестнадцатеричном формате - см. Saua
В противном случае (хакерская рекурсивная версия):
def convertIntToByteString(i):
if i == 0:
return ""
else:
return convertIntToByteString(i >> 8) + chr(i & 255)
Вам не нужна кодировка base64, вы хотите представить цифру 10 в цифре X.
Если вы хотите, чтобы ваша базовая цифра 10 была представлена 26 доступными буквами, вы можете использовать: http://en.wikipedia.org/wiki/Hexavigesimal. (Вы можете расширить этот пример для гораздо большей базы, используя все допустимые символы URL)
Вы должны хотя бы быть в состоянии получить базу 38 (26 букв, 10 цифр, +, _)
Base64 использует 4 байта / символа для кодирования 3 байтов и может кодировать только кратные 3 байта (и добавляет заполнение в противном случае).
Таким образом, представление 4 байтов (вашего среднего значения int) в Base64 займет 8 байтов. Кодирование тех же 4 байтов в шестнадцатеричном формате также займет 8 байтов. Так что вы ничего не получите за один int.
Немного хакер, но это работает:
def b64num(num_to_encode):
h = hex(num_to_encode)[2:] # hex(n) returns 0xhh, strip off the 0x
h = len(h) & 1 and '0'+h or h # if odd number of digits, prepend '0' which hex codec requires
return h.decode('hex').encode('base64')
Вы можете заменить вызов.encode('base64') на что-то в модуле base64, например, urlsafe_b64encode()
У меня есть небольшая библиотека с именем zbase62: http://pypi.python.org/pypi/zbase62
С его помощью вы можете преобразовать объект Python 2 str в строку в кодировке base-62 и наоборот:
Python 2.7.1+ (r271:86832, Apr 11 2011, 18:13:53)
[GCC 4.5.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import os
>>> d = os.urandom(32)
>>> d
'C$\x8f\xf9\x92NV\x97\x13H\xc7F\x0c\x0f\x8d9}\xf5.u\xeeOr\xc2V\x92f\x1b=:\xc3\xbc'
>>> from zbase62 import zbase62
>>> encoded = zbase62.b2a(d)
>>> encoded
'Fv8kTvGhIrJvqQ2oTojUGlaVIxFE1b6BCLpH8JfYNRs'
>>> zbase62.a2b(encoded)
'C$\x8f\xf9\x92NV\x97\x13H\xc7F\x0c\x0f\x8d9}\xf5.u\xeeOr\xc2V\x92f\x1b=:\xc3\xbc'
Тем не менее, вам все равно нужно преобразовать целое число в стр. Это встроено в Python 3:
Python 3.2 (r32:88445, Mar 25 2011, 19:56:22)
[GCC 4.5.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import os
>>> d = os.urandom(32)
>>> d
b'\xe4\x0b\x94|\xb6o\x08\xe9oR\x1f\xaa\xa8\xe8qS3\x86\x82\t\x15\xf2"\x1dL%?\xda\xcc3\xe3\xba'
>>> int.from_bytes(d, 'big')
103147789615402524662804907510279354159900773934860106838120923694590497907642
>>> x= _
>>> x.to_bytes(32, 'big')
b'\xe4\x0b\x94|\xb6o\x08\xe9oR\x1f\xaa\xa8\xe8qS3\x86\x82\t\x15\xf2"\x1dL%?\xda\xcc3\xe3\xba'
Насколько я знаю, для преобразования из int в байты и наоборот в Python 2 не существует удобного, стандартного способа. Наверное, мне стоит скопировать какую-нибудь реализацию, такую как эта: https://github.com/warner/foolscap/blob/46e3a041167950fa93e48f65dcf106a576ed110e/foolscap/banana.py в zbase62 для вашего удобства.
Я работаю над созданием пакета для этого.
Я рекомендую вам использовать мой Base.py https://github.com/kamijoutouma/bases.py который был вдохновлен Base.js
from bases import Bases
bases = Bases()
bases.toBase16(200) // => 'c8'
bases.toBase(200, 16) // => 'c8'
bases.toBase62(99999) // => 'q0T'
bases.toBase(200, 62) // => 'q0T'
bases.toAlphabet(300, 'aAbBcC') // => 'Abba'
bases.fromBase16('c8') // => 200
bases.fromBase('c8', 16) // => 200
bases.fromBase62('q0T') // => 99999
bases.fromBase('q0T', 62) // => 99999
bases.fromAlphabet('Abba', 'aAbBcC') // => 300
обратитесь к https://github.com/kamijoutouma/bases.py, чтобы узнать, какие базы можно использовать
Для вашего случая
Я рекомендую использовать базу 32, 58 или 64
Предупреждение Base-64: помимо нескольких различных стандартов, заполнение в настоящее время не добавляется и длина строки не отслеживается. Не рекомендуется для использования с API, которые ожидают формальные строки base-64!
То же самое касается базы 66, которая в настоящее время не поддерживается ни base.js, ни base.py, но может появиться в будущем.
Если вы ищете способ сократить целочисленное представление с помощью base64, я думаю, вам нужно искать в другом месте. Когда вы кодируете что-то с помощью base64, оно не становится короче, а фактически становится длиннее.
Например, 11234, закодированный с base64, даст MTEyMzQ=
При использовании base64 вы упустили из виду тот факт, что вы не конвертируете только цифры (0-9) в кодировку 64 символов. Вы конвертируете 3 байта в 4 байта, так что вы гарантированно, что ваша строка в кодировке base64 будет на 33,33% длиннее.
Мне нужно было целое число со знаком, поэтому я закончил с:
import struct, base64
def b64encode_integer(i):
return base64.urlsafe_b64encode(struct.pack('i', i)).rstrip('=\n')
Пример:
>>> b64encode_integer(1)
'AQAAAA'
>>> b64encode_integer(-1)
'_____w'
>>> b64encode_integer(256)
'AAEAAA'
Чистый python, без зависимостей, без кодирования байтовых строк и т. Д., Просто превращение base 10 int в base 64 int с правильными символами RFC 4648:
def tetrasexagesimal(number):
out=""
while number>=0:
if number == 0:
out = 'A' + out
break
digit = number % 64
out = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"[digit] + out
number /= 64 # //= 64 for py3 (thank spanishgum!)
if number == 0:
break
return out
tetrasexagesimal(1)
Я бы предложил метод "кодировать целое как двоичную строку, а затем метод base64 кодировать этот", который вы предлагаете, и я бы сделал это с помощью struct:
>>> import struct, base64
>>> base64.b64encode(struct.pack('l', 47))
'LwAAAA=='
>>> struct.unpack('l', base64.b64decode(_))
(47,)
Отредактируйте снова: чтобы удалить лишние 0 для чисел, которые слишком малы, чтобы требовать полной 32-битной точности, попробуйте это:
def pad(str, l=4):
while len(str) < l:
str = '\x00' + str
return str
>>> base64.b64encode(struct.pack('!l', 47).replace('\x00', ''))
'Lw=='
>>> struct.unpack('!l', pad(base64.b64decode('Lw==')))
(47,)
Как было упомянуто здесь в комментариях, вы можете кодировать данные, используя 73 символа, которые не экранируются в URL. Я нашел два места, где использовалась эта кодировка URL-адреса Base73:
- https://git.nolog.cz/NoLog.cz/f.bain/src/branch/master/static/script.js Сокращатель URL-адресов на основе JS
- https://gist.github.com/LoneFry/3792021 на PHP
Но на самом деле вы можете использовать больше символов, например
/,
[,
],
:,
;и некоторые другие. Эти символы экранируются только тогда, когда вы выполняете
encodeURIComponent т.е. вам нужно передать данные через параметр get.
Фактически вы можете использовать до 82 символов. Полный алфавит
!$&'()*+,-./0123456789:;=@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]_abcdefghijklmnopqrstuvwxyz~. Я отсортировал все символы по их коду, поэтому, когда числа Base82URL сортируются как простые строки, они сохраняют тот же порядок.
Я тестировал в Chrome и Firefox, они работают нормально, но могут сбивать с толку обычных пользователей. Но я использовал такие идентификаторы для внутренних вызовов API, где их никто не видит.
32-битное целое число без знака может иметь максимальное значение 2^32=4294967296 И после кодирования в Base82 потребуется 6 символов:
$0~]mx.
У меня нет кода на Python, но вот код JS, который генерирует случайный идентификатор (int32 без знака) и кодирует его в Base82URL:
/**
* Convert uint32 number to Base82 url safe
* @param {int} number
* @returns {string}
*/
function toBase82Url(number) {
// all chars that are not escaped in url
let keys = "!$&'()*+,-./0123456789:;=@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]_abcdefghijklmnopqrstuvwxyz~"
let radix = keys.length
let encoded = []
do {
let index = number% radix
encoded.unshift(keys.charAt(index))
number = Math.trunc(number / radix)
} while (number !== 0)
return encoded .join("")
}
function generateToken() {
let buf = new Uint32Array(1);
window.crypto.getRandomValues(buf)
var randomInt = buf[0]
return toBase82Url(randomInt)
}