Basis 62 Konvertierung

Wie würden Sie eine Ganzzahl in die Basis 62 konvertieren (wie hexadezimal, jedoch mit den folgenden Ziffern: '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ').

Ich habe versucht, eine gute Python-Bibliothek dafür zu finden, aber alle scheinen mit dem Konvertieren von Zeichenfolgen beschäftigt zu sein. Das Python base64-Modul akzeptiert nur Zeichenfolgen und wandelt eine einzelne Ziffer in vier Zeichen um. Ich suchte nach etwas ähnlichem, was URL-Shortener verwenden.

Es gibt kein Standardmodul dafür, aber ich habe meine eigenen Funktionen geschrieben, um dies zu erreichen.

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

Beachten Sie die Tatsache, dass Sie ihm jedes Alphabet zum Codieren und Decodieren geben können. Wenn Sie das alphabetArgument weglassen, erhalten Sie das in der ersten Codezeile definierte 62-Zeichen-Alphabet und damit die Codierung / Decodierung zur / von der 62-Basis.

Hoffe das hilft.

PS - Bei URL-Kürzern habe ich festgestellt, dass es besser ist, einige verwirrende Zeichen wie 0Ol1oI usw. wegzulassen. Daher verwende ich dieses Alphabet für meine URL-Kürzungsanforderungen. "23456789abcdefghijkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

Habe Spaß.

Ich habe auch einmal ein Skript dafür geschrieben, ich finde es ziemlich elegant :)

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

Anwendungsbeispiel:

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

Der folgende Decoder-Hersteller arbeitet mit jeder vernünftigen Basis, hat eine viel aufgeräumtere Schleife und gibt eine explizite Fehlermeldung aus, wenn er auf ein ungültiges Zeichen trifft.

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)

Wenn Sie nach der höchsten Effizienz suchen (wie Django), möchten Sie Folgendes. Dieser Code ist eine Kombination effizienter Methoden von Baishampayan Ghose und WoLpH sowie 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

Möglicherweise möchten Sie Ihr Wörterbuch auch im Voraus berechnen. (Hinweis: Die Codierung mit einer Zeichenfolge ist selbst bei sehr langen Zahlen effizienter als mit einer Liste.)

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

1 Million Nummern in weniger als 2,5 Sekunden codiert und decodiert. (2,2 GHz i7-2670QM)

Wenn Sie das django-Framework verwenden, können Sie das Modul django.utils.baseconv verwenden.

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

Neben base62 definierte baseconv auch base2 / base16 / base36 / base56 / base64.

Sie möchten wahrscheinlich base64, nicht base62. Es gibt eine URL-kompatible Version davon, sodass die zusätzlichen zwei Füllzeichen kein Problem darstellen sollten.

Der Prozess ist ziemlich einfach; Beachten Sie, dass base64 6 Bits und ein reguläres Byte 8 darstellt. Weisen Sie jedem der 64 ausgewählten Zeichen einen Wert von 000000 bis 111111 zu und setzen Sie die 4 Werte so zusammen, dass sie mit einem Satz von 3 base256-Bytes übereinstimmen. Wiederholen Sie diesen Vorgang für jeden Satz von 3 Bytes und füllen Sie ihn am Ende mit dem von Ihnen gewählten Auffüllzeichen auf (0 ist im Allgemeinen nützlich).

Wenn Sie lediglich eine kurze ID generieren müssen (da Sie URL-Kürzungen erwähnen), anstatt etwas zu codieren / decodieren, kann dieses Modul helfen:

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

Sie können das zbase62-Modul von pypi herunterladen

z.B

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

Ich habe stark von den Beiträgen anderer hier profitiert. Ich brauchte den Python-Code ursprünglich für ein Django-Projekt, aber seitdem habe ich mich an node.js gewandt. Hier ist eine Javascript-Version des Codes (des Codierungsteils), den Baishampayan Ghose bereitgestellt hat.

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"));

Ich hoffe das folgende Snippet konnte helfen.

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

Verwendung für Ihren Fall:

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

Natürlich können Sie ein anderes Alphabet angeben, das aus einer geringeren oder größeren Anzahl von Symbolen besteht. Anschließend wird Ihre Zahl in die kleinere oder größere Zahlenbasis konvertiert. Wenn Sie beispielsweise '01' als Alphabet angeben, wird eine Zeichenfolge ausgegeben, die die Eingabenummer als Binär darstellt.

Sie können das Alphabet zunächst mischen, um eine eindeutige Darstellung der Zahlen zu erhalten. Dies kann hilfreich sein, wenn Sie einen URL-Shortener-Dienst durchführen.

Dafür gibt es jetzt eine Python-Bibliothek.

Ich arbeite daran, ein Pip-Paket dafür zu erstellen.

Ich empfehle Ihnen, meine base.py https://github.com/kamijoutouma/bases.py zu verwenden, die von base.js inspiriert wurde

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

Informationen zu den verwendbaren Basen finden Sie unter https://github.com/kamijoutouma/bases.py#known-basesalphabets

Hier ist meine Lösung:

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

Erläuterung

In jeder Basis ist jede Zahl gleich. a1+a2*base**2+a3*base**3...Das Ziel ist es also, alle as zu finden .

Für jeden N=1,2,3...isoliert der Code das aN*base**Ndurch "Moduloing", bfür b=base**(N+1)das alle Slices agrößer als sind N, und das Slicing aller as so, dass ihre Serien kleiner sind als Ndurch ajedes Mal, wenn die Funktion vom Strom rekursiv aufgerufen wird aN*base**N.

Base%(base-1)==1daher base**p%(base-1)==1und daher q*base^p%(base-1)==qmit nur einer Ausnahme, wann q==base-1welche zurückkehrt 0. Um diesen Fall zu beheben, wird es zurückgegeben 0. Die Funktion prüft 0von Anfang an.

Vorteile

In diesem Beispiel gibt es nur eine Multiplikation (anstelle einer Division) und einige Moduloperationen, die alle relativ schnell sind.

Persönlich mag ich die Lösung von Baishampayan, hauptsächlich weil ich die verwirrenden Charaktere entfernt habe.

Der Vollständigkeit halber und einer Lösung mit besserer Leistung zeigt dieser Beitrag eine Möglichkeit, das Python base64-Modul zu verwenden.

Ich habe das vor einiger Zeit geschrieben und es hat ziemlich gut funktioniert (Negative und alles inklusive)

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

Entschuldigung für die Länge des Ganzen

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

Hier ist eine rekursive und iterative Methode, um dies zu tun. Die iterative ist je nach Ausführungszahl etwas schneller.

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

Python 3.7.x

Ich habe einen PhD-Github für einige Algorithmen gefunden, als ich nach einem vorhandenen base62-Skript gesucht habe . Es funktionierte zu diesem Zeitpunkt nicht für die aktuelle Max-Version von Python 3, also habe ich das Problem behoben und ein wenig umgestaltet. Ich arbeite normalerweise nicht mit Python und habe es immer ad-hoc verwendet, also YMMV. Alle Kredite gehen an Dr. Zhihua Lai . Ich habe gerade die Probleme für diese Version von Python gelöst.

Datei base62.py

#modified from Dr. Zhihua Lai's original on GitHub
from math import floor
base = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
b = 62;
def toBase10(b62: str) -> int:
    limit = len(b62)
    res = 0
    for i in range(limit):
        res = b * res + base.find(b62[i])
    return res
def toBase62(b10: int) -> str:
    if b <= 0 or b > 62:
        return 0
    r = b10 % b
    res = base[r];
    q = floor(b10 / b)
    while q:
        r = q % b
        q = floor(q / b)
        res = base[int(r)] + res
    return res

Datei try_base62.py

import base62
print("Base10 ==> Base62")
for i in range(999):
    print(f'{i} => {base62.toBase62(i)}')
base62_samples = ["gud", "GA", "mE", "lo", "lz", "OMFGWTFLMFAOENCODING"]
print("Base62 ==> Base10")
for i in range(len(base62_samples)):
    print(f'{base62_samples[i]} => {base62.toBase10(base62_samples[i])}')

Ausgabe von try_base62.py

Base10 ==> Base62
0 => 0
[...]
998 => g6
Base62 ==> Base10
gud => 63377
GA => 2640
mE => 1404
lo => 1326
lz => 1337
OMFGWTFLMFAOENCODING => 577002768656147353068189971419611424

_{^{Da das Repo keine Lizenzinformationen enthielt, habe ich eine PR eingereicht, damit der ursprüngliche Autor zumindest weiß, dass andere Personen ihren Code verwenden und ändern.}}

Entschuldigung, ich kann Ihnen hier nicht mit einer Bibliothek helfen. Ich würde es vorziehen, base64 zu verwenden und Ihrer Wahl nur zusätzliche Zeichen hinzuzufügen - wenn möglich!

Dann können Sie das base64-Modul verwenden.

Wenn das wirklich, wirklich nicht möglich ist:

Sie können es selbst so machen (dies ist Pseudocode):

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

mit einfacher Rekursion

"""
This module contains functions to transform a number to string and vice-versa
"""
BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
LEN_BASE = len(BASE)


def encode(num):
    """
    This function encodes the given number into alpha numeric string
    """

    if num < LEN_BASE:
        return BASE[num]

    return BASE[num % LEN_BASE] + encode(num//LEN_BASE)


def decode_recursive(string, index):
    """
    recursive util function for decode
    """

    if not string or index >= len(string):
        return 0

    return (BASE.index(string[index]) * LEN_BASE ** index) + decode_recursive(string, index + 1)


def decode(string):
    """
    This function decodes given string to number
    """

    return decode_recursive(string, 0)

Am einfachsten überhaupt.

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode_base62(num):
    s = ""
    while num>0:
      num,r = divmod(num,62)
      s = BASE62[r]+s
    return s


def decode_base62(num):
   x,s = 1,0
   for i in range(len(num)-1,-1,-1):
      s = int(BASE62.index(num[i])) *x + s
      x*=62
   return s

print(encode_base62(123))
print(decode_base62("1Z"))