Как преобразовать целое число в самую короткую URL-безопасную строку в Python? - PullRequest
63 голосов
/ 18 февраля 2009

Я хочу кратчайший способ представления целого числа в URL. Например, 11234 можно сократить до «2be2», используя шестнадцатеричное. Поскольку base64 использует кодировку из 64 символов, должна быть возможность представлять целое число в base64, используя даже меньше символов, чем шестнадцатеричное. Проблема в том, что я не могу найти самый чистый способ преобразования целого числа в base64 (и обратно) с использованием Python.

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

Ответы [ 14 ]

60 голосов
/ 18 февраля 2009

Этот ответ по духу похож на ответ Дугласа Лидера со следующими изменениями:

  • Он не использует реальный 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" символы.
  • Я бы рекомендовал против , использующих представление, отличное от базового 10, в URI в большинстве случаев - это добавляет сложность и усложняет отладку без значительной экономии по сравнению с издержками HTTP - если только вы не собираетесь что-то делать TinyURL-эск.
18 голосов
/ 01 августа 2013

Все ответы, касающиеся 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-пакета:

https://github.com/aljungberg/hhc

14 голосов
/ 18 февраля 2009

Возможно, вам не нужна настоящая кодировка 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). Каждое удвоение добавляет только один бит на символ. Если у вас нет реальной необходимости уплотнять вещи, использование шестнадцатеричного кода, вероятно, будет самым простым и быстрым вариантом.

9 голосов
/ 18 февраля 2009

Для кодирования 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:]
8 голосов
/ 18 февраля 2009

Простой бит - это преобразование байтовой строки в web-safe base64:

import base64
output = base64.urlsafe_b64encode(s)

Хитрый бит - это первый шаг - преобразование целого числа в строку байтов.

Если ваши целые числа маленькие, то лучше их кодировать в шестнадцатеричном формате - см. saua

В противном случае (хакерская рекурсивная версия):

def convertIntToByteString(i):
    if i == 0:
        return ""
    else:
        return convertIntToByteString(i >> 8) + chr(i & 255)
7 голосов
/ 18 февраля 2009

Вам не нужна кодировка base64, вы хотите представить цифру 10 в цифре base X.

Если вы хотите, чтобы ваша базовая цифра 10 была представлена ​​26 доступными буквами, вы можете использовать: http://en.wikipedia.org/wiki/Hexavigesimal. (Вы можете расширить этот пример для гораздо большей базы, используя все допустимые символы URL)

По крайней мере, вы должны получить основание 38 (26 букв, 10 цифр, +, _)

4 голосов
/ 18 февраля 2009

Base64 использует 4 байта / символа для кодирования 3 байтов и может кодировать только кратные 3 байта (и добавляет заполнение в противном случае).

Таким образом, для представления 4 байтов (вашего среднего значения int) в Base64 потребуется 8 байтов. Кодирование тех же 4 байтов в шестнадцатеричном формате также займет 8 байтов. Так что вы ничего не получите за один int.

3 голосов
/ 07 июля 2011

У меня есть небольшая библиотека с именем 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#L41 в zbase62 для вашего удобства.

3 голосов
/ 18 февраля 2009

немного хакер, но это работает:

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 ()

2 голосов
/ 27 мая 2015

Я работаю над созданием пакета для этого пункта.

Я рекомендую вам использовать мой 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#known-basesalphabets для каких баз можно использовать

Для вашего случая

Я рекомендую использовать основание 32, 58 или 64

Предупреждение Base-64: помимо нескольких различных стандартов, заполнение в настоящее время не добавляется и длина строки не отслеживается. Не рекомендуется для использования с API, которые ожидают формальные строки base-64!

То же самое касается базы 66, которая в настоящее время не поддерживается ни base.js, ни base.py, но может произойти в будущем 1019 *

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...