Was ist der beste Weg, um eine Liste von Zahlen in eine einzige alphanumerische Zeichenfolge zu komprimieren oder zu kodieren?

Question

Was ist der beste Weg, um eine Liste von Zahlen beliebiger Länge und Größe zu einer einzigen alphanumerischen Zeichenfolge zu komprimieren oder zu kodieren?

Das Ziel ist es, etwas wie 1,5,8,3,20,212,42 in etwas wie a8D1jN umwandeln zu können, um in einer URL verwendet zu werden, und dann zurück zu 1,5,8,3,20,212, 42.

Für die resultierende Zeichenfolge bin ich gut mit einer beliebigen Zahl und ASCII-Zeichen, Klein- und Großbuchstaben, also: 0-9a-zA-Z. Ich bevorzuge überhaupt keine Interpunktion.

UPDATE: Hinweis hinzugefügt, welche Zeichen in Ordnung sind.

Answer 1

Abhängig von der Reichweite der Nummern - mit einem vernünftigen Bereich könnte ein einfaches dictionary compression Schema funktionieren.

Angesichts Ihrer Editierung und Schätzung von 10k Zeilen könnte ein Wörterbuchschema, bei dem jede Nummer einem Tripel von [A-Za-z0-9] zugeordnet wird, für 62 * 62 * 62 verschiedene Einträge eindeutig sein.

Answer 2

Sie können ein Codierungsschema wie das Base64 verwenden.

Base64-Module oder -Bibliotheken sind in mehreren Programmiersprachen üblich.

Answer 3

Es könnte einen super coolen und effizienten Algorithmus für Ihren Fall geben. Ein sehr einfacher, getesteter und zuverlässiger Algorithmus wäre jedoch die Verwendung eines "gemeinsamen" Codier- oder Komprimierungsalgorithmus für die durch Komma getrennte Zahlenfolge.

Es gibt viele zur Auswahl.

Answer 4

"Beste" hängt davon ab, was Ihre Kriterien sind.

Wenn am besten bedeutet einfach: nur Zeichenfolge die Zahlen zusammen mit einem festen Charakter getrennt:

1a5a8a3a20a212a42

Dies auch sein sollte schnell

Wenn Sie die resultierende Zeichenfolge zu sein klein, können Sie die Zeichenfolge oben durch einen Komprimierungsalgorithmus wie zip ausführen, dann das Ergebnis durch einige Codierung wie base64 oder ähnliches.

Answer 5

Wenn Sie Ihre Liste als eine Zeichenfolge betrachten, dann haben Sie 11 verschiedene Zeichen zu kodieren (0-9 und Komma). Dies kann in 4 Bits ausgedrückt werden. Wenn Sie bereit wären hinzuzufügen, sagen Sie $ und! zu Ihrer Liste von akzeptablen Zeichen, dann hätten Sie 64 verschiedene Ausgangszeichen und könnten daher 6 Bits pro Zeichen codieren.

Das würde bedeuten, dass Sie die Zeichenfolge einer codierten Zeichenfolge zuordnen könnten, die etwa 30% kürzer als die ursprüngliche Zeichenfolge und ziemlich verschleiert und zufällig aussah.

Auf diese Weise können Sie die Nummernfolge [1,5,8,3,20,212,42] in die Zeichenfolge "gLQfoIcIeQqq" umcodieren.

UPDATE: Ich fühlte mich inspiriert und schrieb eine Python-Lösung für diese Lösung (nicht schnell aber funktional genug ...

)

ZERO = ord('0') 
OUTPUT_CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!" 

def encode(numberlist): 

    # convert to string -> '1,5,8,3,20,212,42' 
    s = str(numberlist).replace(' ','')[1:-1] 

    # convert to four bit values -> ['0010', '1011', '0110', ... ] 
    # (add 1 to avoid the '0000' series used for padding later) 
    four_bit_ints = [0 <= (ord(ch) - ZERO) <= 9 and (ord(ch) - ZERO) + 1 or 11 for ch in s] 
    four_bits = [bin(x).lstrip('-0b').zfill(4) for x in four_bit_ints] 

    # make binary string and pad with 0 to align to 6 -> '00101011011010111001101101...' 
    bin_str = "".join(four_bits) 
    bin_str = bin_str + '0' * (6 - len(bin_str) % 6) 

    # split to 6bit blocks and map those to ints 
    six_bits = [bin_str[x * 6 : x * 6 + 6] for x in range(0, len(bin_str)/6)] 
    six_bit_ints = [int(x, 2) for x in six_bits] 

    # map the 6bit integers to characters 
    output = "".join([OUTPUT_CHARACTERS[x] for x in six_bit_ints]) 

    return output 

def decode(input_str): 

    # map the input string from characters to 6bit integers, and convert those to bitstrings 
    six_bit_ints = [OUTPUT_CHARACTERS.index(x) for x in input_str] 
    six_bits = [bin(x).lstrip('-0b').zfill(6) for x in six_bit_ints] 

    # join to a single binarystring 
    bin_str = "".join(six_bits) 

    # split to four bits groups, and convert those to integers 
    four_bits = [bin_str[x * 4 : x * 4 + 4] for x in range(0, len(bin_str)/4)] 
    four_bit_ints = [int(x, 2) for x in four_bits] 

    # filter out 0 values (padding) 
    four_bit_ints = [x for x in four_bit_ints if x > 0] 

    # convert back to the original characters -> '1',',','5',',','8',',','3',',','2','0',',','2','1','2',',','4','2' 
    chars = [x < 11 and str(x - 1) or ',' for x in four_bit_ints] 

    # join, split on ',' convert to int 
    output = [int(x) for x in "".join(chars).split(',') if x] 

    return output 


if __name__ == "__main__": 

    # test 
    for i in range(100): 
     numbers = range(i) 
     out = decode(encode(numbers)) 
     assert out == numbers 

    # test with original series 
    numbers = [1,5,8,3,20,212,42] 
    encoded = encode(numbers) 
    print encoded   # prints 'k2UBsZgZi7uW' 
    print decode(encoded) # prints [1, 5, 8, 3, 20, 212, 42] 

Answer 6

Statt Komma die Zahlen zu trennen, können Sie eine einfache Codierung tun, wo Sie die letzte Ziffer jeder Zahl mit ‚a‘ + Ziffer ersetzen. Also, Ihre Liste [1,5,8,3,20,212,42] würde mysteriös aussehen bfid2a21c4c. :)

Ich würde so etwas nur verwenden, wenn es eine Handvoll Zahlen gibt, wo die Komprimierung nicht in der Lage sein wird, die Zeichenfolge viel zu verkürzen. Wenn es viele Zahlen sind, über die wir sprechen, könnten Sie stattdessen versuchen, eine Art von Komprimierung + base64-Codierung für die Daten durchzuführen.

Answer 7

Sie können auch den chinesischen Restsatz verwenden.

Die Idee ist, eine Zahl X, so dass

X = a1 mod n1 
X = a2 mod n2 
... 
X = ak mod nk 

gcd (Ni, Nj) = 1 für jede Kombination (i j) zu finden.

Das CRT sagt, wie man eine kleinste Zahl X findet, die diese Gleichungen erfüllt.

So können Sie die Zahlen a1 ... ak als X codieren und eine Liste von Ns festhalten. Jedes Ni muss größer als ai sein, ganz so.