Conversion de la Base 62
comment convertir un entier en base 62 (comme hexadécimal, mais avec ces chiffres: '0123456789abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz').
j'ai essayé de trouver une bonne bibliothèque Python pour cela, mais ils semblent tous être occupés à convertir des cordes. Le module Python base64 n'accepte que les chaînes et transforme un seul chiffre en quatre caractères. Je cherchais quelque chose qui ressemble à ce que les raccourcisseurs D'URL utilisent.
18 réponses
Il n'y a pas de module standard pour cela, mais j'ai écrit mes propres fonctions pour y parvenir.
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
Notez le fait que vous pouvez lui donner n'importe quel alphabet pour encoder et décoder. Si vous quittez l'argument alphabet , vous obtiendrez l'alphabet de 62 caractères défini sur la première ligne de code, et donc encodage/décodage à/à partir de 62 base.
Espérons que cette aide.
PS - pour les raccourcisseurs D'URL, J'ai trouvé qu'il vaut mieux laisser de côté quelques personnages déroutants comme 0Ol1oI etc. Ainsi j'utilise cet alphabet pour mes besoins de raccourcissement D'URL - "23456789abcdefghijkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"
amusez-vous bien.
j'ai écrit un script pour faire ça aussi, je pense que c'est assez élégant:)
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
exemple d'usage:
for i in range(100):
print i, base_decode(base_encode(i)), base_encode(i)
le décodeur suivant fonctionne avec n'importe quelle base raisonnable, a une boucle Beaucoup plus raide, 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)
si vous êtes à la recherche de la plus haute efficacité (comme django), vous aurez besoin de quelque chose comme ce qui suit. Ce code est une combinaison de méthodes efficaces de Baishampayan Ghose et 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 aussi calculer votre dictionnaire à l'avance. (Note: L'encodage avec une chaîne 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
codé et décodé 1 million de numéros en moins de 2,5 secondes. (2,2 Ghz i7-2670QM)
vous voulez probablement la base64, pas la base62. Il y a une version compatible URL de celui-ci flottant autour, donc les deux caractères supplémentaires de remplissage ne devrait pas être un problème.
le processus est assez simple; considérez que base64 représente 6 bits et un octet régulier représente 8. Assignez une valeur de 000000 à 111111 à chacun des 64 caractères choisis, et mettez les 4 valeurs ensemble pour correspondre à un ensemble de 3 octets de base256. Répétez pour chaque jeu de 3 octets, padding à la fin avec votre choix du caractère de remplissage (0 est généralement utile).
j'ai une bibliothèque Python pour faire exactement cela ici: http://www.djangosnippets.org/snippets/1431/
si tout ce dont vous avez besoin est de générer un ID court (puisque vous mentionnez les raccourcis URL) plutôt que d'encoder/décoder quelque chose, ce module pourrait vous aider:
vous pouvez télécharger le module zbase62 de pypi
eg
>>> import zbase62
>>> zbase62.b2a("abcd")
'1mZPsa'
j'ai grandement bénéficié des autres postes ici. J'avais besoin du code python à l'origine pour un projet Django, mais depuis, je me suis tourné vers node.js, donc voici un version javascript du code (la partie encodage) que Baishampayan Ghose fourni.
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"));
j'espère que l'extrait suivant pourrait aider.
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)])
Usage pour votre cas:
number = 367891
alphabet = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
print num2sym(number, alphabet) # will print '1xHJ'
évidemment, vous pouvez spécifier un autre alphabet, consistant en un nombre inférieur ou supérieur de symboles, puis il convertira votre nombre à la base de nombre inférieur ou supérieur. Par exemple, en fournissant '01' comme alphabet la chaîne de production représentant le nombre d'entrée comme binaire.
vous pouvez mélanger l'alphabet initialement à ayez votre représentation unique des nombres. Il peut être utile si vous faites le service de raccourci D'URL.
voici ma solution:
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()
explication
dans n'importe quelle base chaque nombre est égal à a1+a2*base**2+a3*base**3... donc le but est de trouver tous les a s.
pour chaque N=1,2,3... le code isole le aN*base**N par "moduloing" par b pour b=base**(N+1) qui coupe tous les a plus grands que N , et découpant tous les a de sorte que leurs serial est plus petit que N en diminuant a chaque fois que la fonction est appelée récursivement par le courant aN*base**N .
Base%(base-1)==1 donc base**p%(base-1)==1 et donc q*base^p%(base-1)==q avec une seule exception, lorsque q==base-1 qui renvoie 0 . Pour corriger ce cas, il retourne 0 . La fonction vérifie 0 depuis le début.
avantages
dans cet échantillon il n'y a qu'une seule multiplication (au lieu d'une division) et quelques opérations de module, qui sont toutes relativement rapides.
j'ai écrit ça il y a un moment et ça a plutôt bien marché (négatifs et tout compris)
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
désolé pour la longueur de tout
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
Voici une façon récurive et itérative de le faire. L'itératif est un peu plus rapide selon le nombre d'exécution.
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
il y a maintenant une bibliothèque python pour cela.
je travaille sur un paquet pip pour ça.
je vous recommande d'utiliser mon bases.py https://github.com/kamijoutouma/bases.py qui s'inspire des bases.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
se référer à https://github.com/kamijoutouma/bases.py#known-basesalphabets pour quelles bases sont utilisables
si vous utilisez django framework, vous pouvez utiliser django.utils.module baseconv.
>>> from django.utils import baseconv
>>> baseconv.base62.encode(1234567890)
1LY7VK
en plus de base62, baseconv a également défini base2/base16/base36/base56/base64.
Désolé, je ne peux pas vous aider avec une bibliothèque ici. Je préférerais utiliser base64 et ajouter des caractères supplémentaires à votre choix -- si possible!
alors vous pouvez utiliser le module base64.
Si c'est vraiment, vraiment pas possible:
vous pouvez le faire vous-même de cette façon (c'est un pseudo-code):
base62vals = []
myBase = 62
while num > 0:
reminder = num % myBase
num = num / myBase
base62vals.insert(0, reminder)