Conversion de la base 62

Question

Comment convertir un nombre entier en base 62 (comme l'hexadécimal, mais avec ces chiffres : '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ').

J'ai essayé de trouver une bonne bibliothèque Python pour cela, mais elles semblent toutes occupées à convertir des chaînes de caractères. Le module Python base64 n'accepte que les chaînes de caractères et transforme un seul chiffre en quatre caractères. Je cherchais quelque chose qui ressemble à ce qu'utilisent les raccourcisseurs d'URL.

Answer 1

Il n'existe pas de module standard pour cela, mais j'ai écrit mes propres fonctions pour y parvenir.

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(num, alphabet):
    """Encode a positive number into Base X and return the string.

    Arguments:
    - `num`: The number to encode
    - `alphabet`: The alphabet to use for encoding
    """
    if num == 0:
        return alphabet[0]
    arr = []
    arr_append = arr.append  # Extract bound-method for faster access.
    _divmod = divmod  # Access to locals is faster.
    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 decoding
    """
    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

Notez le fait que vous pouvez lui donner n'importe quel alphabet à utiliser pour l'encodage et le décodage. Si vous laissez le alphabet argument, vous allez avoir l'alphabet de 62 caractères défini sur la première ligne de code, et donc l'encodage/décodage vers/depuis la base 62.

J'espère que cela vous aidera.

PS - Pour les raccourcisseurs d'URL, j'ai constaté qu'il est préférable de laisser de côté quelques caractères déroutants comme 0Ol1oI, etc. J'utilise donc cet alphabet pour mes besoins de raccourcissement d'URL. "23456789abcdefghijkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

Amusez-vous bien.

Answer 2

J'ai écrit une fois un script pour faire cela aussi, je pense que c'est assez élégant :)

import string
# Remove the `_@` below for base62, now it has 64 characters
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

Exemple d'utilisation :

for i in range(100):                                    
    print i, base_decode(base_encode(i)), base_encode(i)

Answer 3

Si vous recherchez la plus grande efficacité (comme django), vous voudrez quelque chose comme ce qui suit. Ce code est une combinaison de méthodes efficaces de Baishampayan Ghose, WoLpH et 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

Vous pouvez également calculer votre dictionnaire à l'avance. (Note : L'encodage avec une chaîne de caractères montre plus d'efficacité qu'avec une liste, même avec des nombres très longs).

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

Encodage et décodage d'un million de chiffres en moins de 2,5 secondes. (2.2Ghz i7-2670QM)

Answer 4

Le décodeur suivant fonctionne avec n'importe quelle base raisonnable, a une boucle beaucoup plus ordonnée, et donne un message d'erreur explicite quand il rencontre un caractère invalide.

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 5

Vous voulez probablement la base64, pas la base62. Il en existe une version compatible avec les URL, ce qui fait que les deux caractères de remplissage supplémentaires ne devraient pas poser de problème.

Le processus est assez simple ; considérez que la base64 représente 6 bits et qu'un octet ordinaire en représente 8. Attribuez une valeur de 000000 à 111111 à chacun des 64 caractères choisis, et assemblez les 4 valeurs pour obtenir un ensemble de 3 octets en base256. Répétez l'opération pour chaque ensemble de 3 octets, en ajoutant à la fin le caractère de remplissage de votre choix (0 est généralement utile).