База 62 преобразования

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

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

 l0b013 июл. 2009 г., 16:32
Если вы хотите создать короткие URL-адреса, вы можете использовать весь набор символов, которые не нужно кодировать:en.wikipedia.org/wiki/Percent-encoding#Types_of_URI_characters, Это 66 символов.
 samoz13 июл. 2009 г., 16:24
Похоже, кто-то только что нашел идею проекта с открытым исходным кодом :) Дайте мне знать, если вы найдете что-нибудь или решите создать свой собственный ...
 Miles14 июл. 2009 г., 06:14
Этот вопрос имеет ряд применимых ответов:stackoverflow.com/questions/561486/…
 Mike Cooper14 июл. 2009 г., 06:12
что насчет Base64? Возможно, вам больше повезет найти библиотеки для этого.
 mikl13 июл. 2009 г., 16:45
Я думаю, что я пропущу точку и тильду, чтобы избежать путаницы среди пользователей, но черта и подчеркивание должны быть достойными дополнениями, спасибо.

Ответы на вопрос(17)

онадобился код 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"));
 19 нояб. 2012 г., 06:45
Я обновил этот код и превратил его в проект с открытым исходным кодом для всех, кто заинтересованgithub.com/sbussard/encode-the-things

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

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

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

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

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

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

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

Если вы ищете наивысшую эффективность (например, 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)

 27 мая 2015 г., 10:29
@SMGreenfield Можете ли вы привести несколько примеров, которые не работают?
 25 апр. 2013 г., 10:44
Интересный момент. Имеет смысл, поскольку кортежи более легкие, чем строки. Спасибо за просветление :)!
 24 апр. 2013 г., 09:20
Привет, origiNell, ты прав, что tuple () не нужен, но в моей системе он заставляет код работать примерно на 20% быстрее. Попробуйте протестировать его без tuple () и посмотрите, что работает лучше для вас. Ура :)
 18 апр. 2013 г., 18:05
Не обязательно нужноtuple() вокругBASE_ALPH в начале. В Python каждая строка является итеративной. Эта функция, конечно, используетсяenumerate(), Так что код становится еще проще :)
 12 авг. 2014 г., 17:15
@Sepero Я улучшил вашу версию с точки зрения форматирования, именования, тестов и функциональности (поддерживаются отрицательные числа):pastebin.com/4uket7iu (вы можете обновить свой ответ этим)

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

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)
 25 янв. 2014 г., 04:18
если использоватьreversed(string) быстрее, чем нарезкаstring[::-1] в функции base_decode.
 28 апр. 2011 г., 15:46
Эта версия значительно быстрее принятого решения от Baishampayan. Я оптимизировал дальнейшее вычисление длины вне функции. Результаты тестирования (100 000 итераций): версия-WoLpH: .403 .399 .399 .398 .398 | Версия-Байшампаян: 1.783 1.785 1.782 1.788 1.784. Эта версия примерно в 4 раза быстрее.
 05 февр. 2016 г., 10:49
Мне потребовалось много времени, чтобы найти этот вопрос. Никогда не знал, что это называется преобразованием base62. Хороший ответ.
 mikl02 апр. 2010 г., 17:39
Это здорово, спасибо. Мне нравится короткость :)

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

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

 mikl02 апр. 2010 г., 17:37
Как упоминалось в моем комментарии к Виллихэму Тотланду, Pythons base64 неоптимален для кодирования чисел, поскольку он оптимизирован для строк.

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

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
 26 мая 2015 г., 05:58
Мне очень понравился твой рекурсивный подход. Моя дочь, которая принимала AP Comp Sci, нашла для меня то же самое решение для реализации «base25». (используя "ABCDEFHJKMNPQRTUVWXY34789") на C ++. Я решил преобразовать его в Python и, будучи новичком в этом языке, столкнулся с несколькими камнями преткновения - которые вы элегантно решили в одной строке кода! Вы даже избегаете общей проблемы с переводом 0 в пустую строку в алфавитах, которые не начинаются с 0-9. Отличная работа! (Мне не нужны отрицательные числа, но ваш подход был настолько хорош, что было бы неплохо добавить это для будущих браузеров)
 26 мая 2015 г., 12:29
@SMGreenfield Большое спасибо за ваш отзыв.

PyPI

например

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

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

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)
 10 янв. 2013 г., 14:07
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
 15 янв. 2013 г., 12:32
@Sepero: Что смешного? Это серьезное надежное программное обеспечение промышленного уровня. Нет Микки-Мауса с задним ходом** оператор в цикле.
 15 янв. 2013 г., 19:26
Успокойся, друг. Вы правы. Я упустил истинную ценность вашего внутреннего цикла из-за того, что он похоронен в вещах, которые не связаны с вопросом (упаковка, проверка ошибок, модульное тестирование).
 14 авг. 2014 г., 16:15
Было ли q в последнем значении преднамеренным, чтобы показать повышение ValueError?
 17 янв. 2013 г., 03:27
Выглядит хорошо, но вы не забыли «промышленную силу» кодировщик, который принимает целое число плюс алфавит для создания строки?
Решение Вопроса

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

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"

Повеселись.

 13 июл. 2009 г., 16:42
base62_encode (-1) :)
 28 сент. 2009 г., 16:31
Для декодирования более предпочтительной является не вычислять мощности (экономит время, короче записывать, но, что более важно, избегает ошибочных ошибок), таким образом: num = 0; для символа в строке: num = num * base + alphabet.index (char)
 13 июл. 2009 г., 16:32
+1: приятно! Это может быть расширено с помощью большего количества URL-дружественных символов, чтобы возможно сохранить один символ здесь и там. Знающие персонажи в безопасности:$-_.+!*'(),;/?:@&=  Вы, вероятно, можете использовать некоторые другие символы, такие как[]~ и т.п.
 28 сент. 2009 г., 16:24
Ошибка именования: она не является базовой 62, поскольку алфавит настраивается.
 06 окт. 2009 г., 01:47
@ShreevatsaR: какая-то конкретная причина для использования str.index () вместо поиска в словаре? Смотри мой ответ ...

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

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

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

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
 27 февр. 2017 г., 09:37
К вашему сведению, в вашей входной строке отсутствуют несколько символов / цифр.
 29 мар. 2013 г., 01:51
Это исправляет имя BASE_LIST и также переворачивает строку при декодировании, которая была опущена в отличном ответе Spero.

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

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

 mikl02 апр. 2010 г., 17:34
Стандартные методы кодирования Python base64 не очень подходят для коротких URL-адресов, поскольку они оптимизированы для кодирования байтов (т. Е. Строк / букв) и будут давать более длинные выходные данные, чем просто смещение базы числового значения.
 09 авг. 2011 г., 16:19
@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. Байты не являются строками или буквами. Байты - это байты. знак равно
 17 янв. 2013 г., 02:29
@yesudeep: Итак, байты являются байтами & # x2026; и какова ваша точка зрения?

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

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-адресов.

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

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

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

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

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

 mikl11 янв. 2011 г., 15:55
Я не уверен, что подходит для коротких URL. UUID, как правило, очень большое число, поэтому даже кодирование base57, как он делает, должно быть довольно длинным для короткого URL.
 22 янв. 2011 г., 00:09
Вы можете просто вырезать столько, сколько захотите, столкновения все равно будут маловероятными, поскольку это чисто случайный характер, но больше не будет уникальным идентификатором.

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

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

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

Ваш ответ на вопрос