Вопрос по base62, math, python – База 62 преобразования

68

Как бы вы преобразовали целое число в основание 62 (как шестнадцатеричное, но с этими цифрами: «0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ»).

Я пытался найти хорошую библиотеку Python для нее, но все они, кажется, заняты преобразованием строк. Модуль Python base64 принимает только строки и превращает одну цифру в четыре символа. Я искал что-то похожее на то, что используют сокращения URL.

что насчет Base64? Возможно, вам больше повезет найти библиотеки для этого. Mike Cooper
Похоже, кто-то только что нашел идею проекта с открытым исходным кодом :) Дайте мне знать, если вы найдете что-нибудь или решите создать свой собственный ... samoz
Этот вопрос имеет ряд применимых ответов:stackoverflow.com/questions/561486/… Miles
Если вы хотите создать короткие URL-адреса, вы можете использовать весь набор символов, которые не нужно кодировать:en.wikipedia.org/wiki/Percent-encoding#Types_of_URI_characters, Это 66 символов. l0b0
Я думаю, что я пропущу точку и тильду, чтобы избежать путаницы среди пользователей, но черта и подчеркивание должны быть достойными дополнениями, спасибо. mikl

Ваш Ответ

17   ответов
42

я думаю, он довольно элегантный :)

import string
BASE_LIST = string.digits + string.letters + '[email protected]'
BASE_DICT = dict((c, i) for i, c in enumerate(BASE_LIST))

def base_decode(string, reverse_base=BASE_DICT):
    length = len(reverse_base)
    ret = 0
    for i, c in enumerate(string[::-1]):
        ret += (length ** i) * reverse_base[c]

    return ret

def base_encode(integer, base=BASE_LIST):
    if integer == 0:
        return base[0]

    length = len(base)
    ret = ''
    while integer != 0:
        ret = base[integer % length] + ret
        integer /= length

    return ret

Пример использования:

for i in range(100):                                    
    print i, base_decode(base_encode(i)), base_encode(i)
Мне потребовалось много времени, чтобы найти этот вопрос. Никогда не знал, что это называется преобразованием base62. Хороший ответ.
Это здорово, спасибо. Мне нравится короткость :) mikl
Эта версия значительно быстрее принятого решения от Baishampayan. Я оптимизировал дальнейшее вычисление длины вне функции. Результаты тестирования (100 000 итераций): версия-WoLpH: .403 .399 .399 .398 .398 | Версия-Байшампаян: 1.783 1.785 1.782 1.788 1.784. Эта версия примерно в 4 раза быстрее.
если использоватьreversed(string) быстрее, чем нарезкаstring[::-1] в функции base_decode.
3

Если все, что вам нужно, это сгенерировать короткий идентификатор (так как вы упоминаете сокращения URL), а не что-то кодировать / декодировать, этот модуль может помочь:

https://github.com/stochastic-technologies/shortuuid/

Я не уверен, что подходит для коротких URL. UUID, как правило, очень большое число, поэтому даже кодирование base57, как он делает, должно быть довольно длинным для короткого URL. mikl
Вы можете просто вырезать столько, сколько захотите, столкновения все равно будут маловероятными, поскольку это чисто случайный характер, но больше не будет уникальным идентификатором.
0

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

Тогда вы можете использовать модуль base64.

Если это действительно, действительно невозможно:

Вы можете сделать это самостоятельно таким образом (это псевдокод):

base62vals = []
myBase = 62
while num > 0:
   reminder = num % myBase
   num = num / myBase
   base62vals.insert(0, reminder)
1

ее в зависимости от количества выполнений.

def base62_encode_r(dec):
    s = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    return s[dec] if dec < 62 else base62_encode_r(dec / 62) + s[dec % 62]
print base62_encode_r(2347878234)

def base62_encode_i(dec):
    s = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    ret = ''
    while dec > 0:
        ret = s[dec % 62] + ret
        dec /= 62
    return ret
print base62_encode_i(2347878234)

def base62_decode_r(b62):
    s = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    if len(b62) == 1:
        return s.index(b62)
    x = base62_decode_r(b62[:-1]) * 62 + s.index(b62[-1:]) % 62
    return x
print base62_decode_r("2yTsnM")

def base62_decode_i(b62):
    s = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    ret = 0
    for i in xrange(len(b62)-1,-1,-1):
        ret = ret + s.index(b62[i]) * (62**(len(b62)-i-1))
    return ret
print base62_decode_i("2yTsnM")

if __name__ == '__main__':
    import timeit
    print(timeit.timeit(stmt="base62_encode_r(2347878234)", setup="from __main__ import base62_encode_r", number=100000))
    print(timeit.timeit(stmt="base62_encode_i(2347878234)", setup="from __main__ import base62_encode_i", number=100000))
    print(timeit.timeit(stmt="base62_decode_r('2yTsnM')", setup="from __main__ import base62_decode_r", number=100000))
    print(timeit.timeit(stmt="base62_decode_i('2yTsnM')", setup="from __main__ import base62_decode_i", number=100000))

0.270266867033
0.260915645986
0.344734796766
0.311662500262
Мне очень понравился твой рекурсивный подход. Моя дочь, которая принимала AP Comp Sci, нашла для меня то же самое решение для реализации «base25». (используя "ABCDEFHJKMNPQRTUVWXY34789") на C ++. Я решил преобразовать его в Python и, будучи новичком в этом языке, столкнулся с несколькими камнями преткновения - которые вы элегантно решили в одной строке кода! Вы даже избегаете общей проблемы с переводом 0 в пустую строку в алфавитах, которые не начинаются с 0-9. Отличная работа! (Мне не нужны отрицательные числа, но ваш подход был настолько хорош, что было бы неплохо добавить это для будущих браузеров)
@SMGreenfield Большое спасибо за ваш отзыв.
8

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

def base_n_decoder(alphabet):
    """Return a decoder for a base-n encoded string
    Argument:
    - `alphabet`: The alphabet used for encoding
    """
    base = len(alphabet)
    char_value = dict(((c, v) for v, c in enumerate(alphabet)))
    def f(string):
        num = 0
        try:
            for char in string:
                num = num * base + char_value[char]
        except KeyError:
            raise ValueError('Unexpected character %r' % char)
        return num
    return f

if __name__ == "__main__":
    func = base_n_decoder('0123456789abcdef')
    for test in ('0', 'f', '2020', 'ffff', 'abqdef'):
        print test
        print func(test)
While I would probably never use this, I had too give you a thumbs up for creativity. This code gave me a laugh. :) – Sepero Jan 10 '13 at 13:07
Было ли q в последнем значении преднамеренным, чтобы показать повышение ValueError?
Успокойся, друг. Вы правы. Я упустил истинную ценность вашего внутреннего цикла из-за того, что он похоронен в вещах, которые не связаны с вопросом (упаковка, проверка ошибок, модульное тестирование).
@Sepero: Что смешного? Это серьезное надежное программное обеспечение промышленного уровня. Нет Микки-Мауса с задним ходом** оператор в цикле.
Выглядит хорошо, но вы не забыли «промышленную силу» кодировщик, который принимает целое число плюс алфавит для создания строки?
138

Для этого нет стандартного модуля, но я написал свои собственные функции для этого.

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(num, alphabet=BASE62):
    """Encode a positive number in Base X

    Arguments:
    - `num`: The number to encode
    - `alphabet`: The alphabet to use for encoding
    """
    if num == 0:
        return alphabet[0]
    arr = []
    base = len(alphabet)
    while num:
        num, rem = divmod(num, base)
        arr.append(alphabet[rem])
    arr.reverse()
    return ''.join(arr)

def decode(string, alphabet=BASE62):
    """Decode a Base X encoded string into the number

    Arguments:
    - `string`: The encoded string
    - `alphabet`: The alphabet to use for encoding
    """
    base = len(alphabet)
    strlen = len(string)
    num = 0

    idx = 0
    for char in string:
        power = (strlen - (idx + 1))
        num += alphabet.index(char) * (base ** power)
        idx += 1

    return num

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

Надеюсь это поможет.

PS - для сокращателей URL я обнаружил, что лучше не указывать несколько запутанных символов, таких как 0Ol1oI и т. Д. Таким образом, я использую этот алфавит для своих нужд по сокращению URL -"23456789abcdefghijkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

Повеселись.

base62_encode (-1) :)
+1: приятно! Это может быть расширено с помощью большего количества URL-дружественных символов, чтобы возможно сохранить один символ здесь и там. Знающие персонажи в безопасности:$-_.+!*'(),;/?:@&=  Вы, вероятно, можете использовать некоторые другие символы, такие как[]~ и т.п.
Ошибка именования: она не является базовой 62, поскольку алфавит настраивается.
@ShreevatsaR: какая-то конкретная причина для использования str.index () вместо поиска в словаре? Смотри мой ответ ...
Для декодирования более предпочтительной является не вычислять мощности (экономит время, короче записывать, но, что более важно, избегает ошибочных ошибок), таким образом: num = 0; для символа в строке: num = num * base + alphabet.index (char)
1
BASE_LIST = tuple("23456789ABCDEFGHJKLMNOPQRSTUVWXYZabcdefghjkmnpqrstuvwxyz")
BASE_DICT = dict((c, v) for v, c in enumerate(BASE_LIST))
BASE_LEN = len(BASE_LIST)

def nice_decode(str):
    num = 0
    for char in str[::-1]:
        num = num * BASE_LEN + BASE_DICT[char]
    return num

def nice_encode(num):
    if not num:
        return BASE_LIST[0]

    encoding = ""
    while num:
        num, rem = divmod(num, BASE_LEN)
        encoding += BASE_LIST[rem]
    return encoding
К вашему сведению, в вашей входной строке отсутствуют несколько символов / цифр.
Это исправляет имя BASE_LIST и также переворачивает строку при декодировании, которая была опущена в отличном ответе Spero.
7

Если вы ищете наивысшую эффективность (например, django), вам понадобится что-то вроде следующего. Этот код представляет собой сочетание эффективных методов от Baishampayan Ghose и WoLpH и John Machin.

# Edit this list of characters as desired.
BASE_ALPH = tuple("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
BASE_DICT = dict((c, v) for v, c in enumerate(BASE_ALPH))
BASE_LEN = len(BASE_ALPH)

def base_decode(string):
    num = 0
    for char in string:
        num = num * BASE_LEN + BASE_DICT[char]
    return num

def base_encode(num):
    if not num:
        return BASE_ALPH[0]

    encoding = ""
    while num:
        num, rem = divmod(num, BASE_LEN)
        encoding = BASE_ALPH[rem] + encoding
    return encoding

Вы можете также рассчитать свой словарь заранее. (Примечание: кодирование со строкой показывает большую эффективность, чем со списком, даже с очень длинными числами.)

>>> timeit.timeit("for i in xrange(1000000): base.base_decode(base.base_encode(i))", setup="import base", number=1)
2.3302059173583984

Закодировал и расшифровал 1 миллион номеров менее чем за 2,5 секунды. (2,2 ГГц i7-2670QM)

Интересный момент. Имеет смысл, поскольку кортежи более легкие, чем строки. Спасибо за просветление :)!
@SMGreenfield Можете ли вы привести несколько примеров, которые не работают?
Привет, origiNell, ты прав, что tuple () не нужен, но в моей системе он заставляет код работать примерно на 20% быстрее. Попробуйте протестировать его без tuple () и посмотрите, что работает лучше для вас. Ура :)
Не обязательно нужноtuple() вокругBASE_ALPH в начале. В Python каждая строка является итеративной. Эта функция, конечно, используетсяenumerate(), Так что код становится еще проще :)
@Sepero Я улучшил вашу версию с точки зрения форматирования, именования, тестов и функциональности (поддерживаются отрицательные числа):pastebin.com/4uket7iu (вы можете обновить свой ответ этим)
1

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

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

2

онадобился код Python для проекта Django, но с тех пор я обратился к node.js, так что здесьjavascript version кода (часть кодирования), которую предоставил Baishampayan Ghose.

var ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

function base62_encode(n, alpha) {
  var num = n || 0;
  var alphabet = alpha || ALPHABET;

  if (num == 0) return alphabet[0];
  var arr = [];
  var base = alphabet.length;

  while(num) {
    rem = num % base;
    num = (num - rem)/base;
    arr.push(alphabet.substring(rem,rem+1));
  }

  return arr.reverse().join('');
}

console.log(base62_encode(2390687438976, "123456789ABCDEFGHIJKLMNPQRSTUVWXYZ"));
Я обновил этот код и превратил его в проект с открытым исходным кодом для всех, кто заинтересованgithub.com/sbussard/encode-the-things
1

главным образом из-за удаления непонятных персонажей.

Для полноты и решения с лучшей производительностью,эта почта показывает, как использовать модуль Python base64.

Как упоминалось в моем комментарии к Виллихэму Тотланду, Pythons base64 неоптимален для кодирования чисел, поскольку он оптимизирован для строк. mikl
2

вы можете использовать модуль django.utils.baseconv.

>>> from django.utils import baseconv
>>> baseconv.base62.encode(1234567890)
1LY7VK

В дополнение к base62, baseconv также определил base2 / base16 / base36 / base56 / base64.

2

PyPI

например

>>> import zbase62
>>> zbase62.b2a("abcd")
'1mZPsa'
Да, я смотрел на это раньше, но он конвертирует строки, а не числа :) mikl
4

Вы, вероятно, хотите base64, а не base62. Имеется URL-совместимая версия, так что дополнительные два символа-заполнителя не должны быть проблемой.

Процесс довольно прост; учтите, что base64 представляет 6 битов, а обычный байт представляет 8. Присвойте значение от 000000 до 111111 каждому из 64 выбранных символов и соедините 4 значения, чтобы они соответствовали набору из 3 base256 байтов. Повторите эти действия для каждого набора из 3 байтов, дополняя в конце выбранным вами символом заполнения (обычно полезен 0).

Стандартные методы кодирования Python base64 не очень подходят для коротких URL-адресов, поскольку они оптимизированы для кодирования байтов (т. Е. Строк / букв) и будут давать более длинные выходные данные, чем просто смещение базы числового значения. mikl
@mikl Конечно, модуль Python base64 может не подходить для генерации коротких URL-адресов, но все методы кодирования Python действительно работают с последовательностями чисел base-256. байты на самом деле являются «строками» в кодировке 256-й строки. Python 2.x обрабатывает строки как последовательность байтов, в то время как Python 3.x (что делает правильно) обрабатывает строки как Unicode. Таким образом, b 'foobar' apos; на самом деле это всего лишь причудливый способ написания [102, 111, 111, 98, 97, 114] или [0x66,0x6f, 0x6f, 0x62,0x61,0x72] или b '\ x66 \ x6f \ x6f \ x62 \ x61 \ x72 & apos ; что неудивительно, что представление base-256. Байты не являются строками или буквами. Байты - это байты. знак равно
@yesudeep: Итак, байты являются байтами & # x2026; и какова ваша точка зрения?
2

Я надеюсь, что следующий фрагмент может помочь.

def num2sym(num, sym, join_symbol=''):
    if num == 0:
        return sym[0]
    if num < 0 or type(num) not in (int, long):
        raise ValueError('num must be positive integer')

    l = len(sym)  # target number base
    r = []
    div = num
    while div != 0: # base conversion
        div, mod = divmod(div, l)
        r.append(sym[mod])

    return join_symbol.join([x for x in reversed(r)])

Использование для вашего случая:

number = 367891
alphabet = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
print num2sym(number, alphabet)  # will print '1xHJ'

Очевидно, что вы можете указать другой алфавит, состоящий из меньшего или большего количества символов, тогда он преобразует ваш номер в меньшую или большую числовую базу. Например, предоставление «01»; в виде алфавита выведет строку, представляющую входной номер в двоичном виде.

Вы можете перетасовать алфавит, чтобы получить уникальное представление чисел. Это может быть полезно, если вы используете службу сокращения URL-адресов.

Неплохо. Вы можете использоватьif num < 0 or type(num) not in (int, long):.
спасибо, только исправил
Это лучше, но это немного сложнее, потому чтоlong не существует в Py 3.x - так что можно использоватьthis answer.
Or использовать мою собственную портативную версию:isinstance(x, (type(1), type(2**32))).
1

Я написал это некоторое время назад, и это работало довольно хорошо (негативы и все включено)

def code(number,base):
    try:
        int(number),int(base)
    except ValueError:
        raise ValueError('code(number,base): number and base must be in base10')
    else:
        number,base = int(number),int(base)
    if base < 2:
        base = 2
    if base > 62:
        base = 62
    numbers = [0,1,2,3,4,5,6,7,8,9,"a","b","c","d","e","f","g","h","i","j",
               "k","l","m","n","o","p","q","r","s","t","u","v","w","x","y",
               "z","A","B","C","D","E","F","G","H","I","J","K","L","M","N",
               "O","P","Q","R","S","T","U","V","W","X","Y","Z"]
    final = ""
    loc = 0
    if number < 0:
        final = "-"
        number = abs(number)
    while base**loc <= number:
        loc = loc + 1
    for x in range(loc-1,-1,-1):
        for y in range(base-1,-1,-1):
            if y*(base**x) <= number:
                final = "{}{}".format(final,numbers[y])
                number = number - y*(base**x)
                break
    return final

def decode(number,base):
    try:
        int(base)
    except ValueError:
        raise ValueError('decode(value,base): base must be in base10')
    else:
        base = int(base)
    number = str(number)
    if base < 2:
        base = 2
    if base > 62:
        base = 62
    numbers = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f",
               "g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v",
               "w","x","y","z","A","B","C","D","E","F","G","H","I","J","K","L",
               "M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
    final = 0
    if number.startswith("-"):
        neg = True
        number = list(number)
        del(number[0])
        temp = number
        number = ""
        for x in temp:
            number = "{}{}".format(number,x)
    else:
        neg = False
    loc = len(number)-1
    number = str(number)
    for x in number:
        if numbers.index(x) > base:
            raise ValueError('{} is out of base{} range'.format(x,str(base)))
        final = final+(numbers.index(x)*(base**loc))
        loc = loc - 1
    if neg:
        return -final
    else:
        return final

извините за длину всего этого

2

def base62(a):
    baseit = (lambda a=a, b=62: (not a) and '0' or
        baseit(a-a%b, b*62) + '0123456789abcdefghijklmnopqrstuvwxyz'
                              'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[a%b%61 or -1*bool(a%b)])
    return baseit()
explanation

В любой базе каждое число равноa1+a2*base**2+a3*base**3... Таким образом, цель состоит в том, чтобы найти всеas.

Для каждогоN=1,2,3... код изолируетaN*base**N по "модуляции" отb заb=base**(N+1) который нарезает всеaбольше чемNи нарезать всеas, так что их серийный номер меньше, чемN уменьшаяa каждый раз функция вызывается рекурсивно текущимaN*base**N.

Base%(base-1)==1 следовательноbase**p%(base-1)==1 и поэтомуq*base^p%(base-1)==q только с одним исключением, когдаq==base-1 который возвращается0, Чтобы исправить это дело, он возвращает0, Функция проверяет0 с начала.

advantages

В этом примере есть только одно умножение (вместо деления) и некоторые операции модуля, которые все относительно быстрые.

Похожие вопросы