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

Question

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

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

Answer 1

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

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"

Веселитесь.

Answer 2

Однажды я написал сценарий для этого, я думаю, он довольно элегантный:)

import string
BASE_LIST = string.digits + string.letters + '_@'
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)

Answer 3

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

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)

Answer 4

Если вы ищете максимальную эффективность (например, django), вам нужно что-то вроде следующего. Этот код представляет собой комбинацию эффективных методов от Байшампаян Гхос, WoLpH и Джона Мачин.

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

Answer 5

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

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

Answer 6

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

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

Answer 7

Вы можете скачать модуль zbase62 с pypi

например

>>> import zbase62
>>> zbase62.b2a("abcd")
'1mZPsa'

Answer 8

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

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

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

Answer 9

Вот мое решение:

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

---

Объяснение

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

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

---

Преимущества

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

Answer 10

Мне очень понравились посты других здесь. Первоначально мне понадобился код Python для проекта Django, но с тех пор я обратился к node.js, так что вот версия javascript кода (часть кодирования), которую 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"));