Verwenden von Base 80 zum Komprimieren von Dateien

Ich möchte die Dateigröße komprimieren, indem ich mein eigenes Nummerierungssystem mit einer 80-basierten Nummer erstelle. Ich möchte wirklich wissen, ob dies überhaupt möglich ist. Ich habe gelernt, dass Hexadezimal Symbole wie A, B, C, D, E, F verwendet, um 10,11,12,13,14,15 darzustellen - und das möchte ich mit meinem eigenen Nummerierungssystem tun, aber in größerem Maßstab . Bitte korrigieren Sie mich, wenn mir etwas fehlt.

Ist es möglich ?

Während Sie weniger 80-basierte Zahlen als 2-basierte Zahlen (Bits) benötigen, um dieselbe Datei zu codieren, besteht die einzige Möglichkeit, diese 80-basierten Nummern auf einem Computer zu speichern, darin, sie als Bits zu codieren. Sie gewinnen also nichts.

Tatsächlich verlieren Sie tatsächlich Speicherplatz, da 80 keine Zweierpotenz ist: Sie benötigen 7 Bits für jede 80-basierte Zahl, aber in diesen 7 Bits können Sie stattdessen 128 verschiedene Zustände aktivieren, wenn Sie sie direkt verwenden.

Es gibt verschiedene Möglichkeiten, die Frage zu interpretieren. Was ich denke , dass Sie fragen könnten, ist, dass Sie eine Folge von Buchstaben in einem Alphabet wo . Sie möchten dies in möglichst wenigen Bits speichern. Wir gehen davon aus, dass die Buchstaben im Alphabet gleichmäßig verteilt sind.Σ | Σ | = $n$$\Sigma$$\left| \Sigma \right| = 80$

Der informationstheoretische Speicherplatz, der zum Speichern benötigt wird, istBits. Mit der arithmetischen Codierung können Sie dies in linearer Zeit tun, indem Sie Bits des Zwischenraums verwenden. (Denken Sie daran, das ist der Logarithmus der Anzahl der Symbole in Bits! Wenn die Größe der Sequenz in ein Maschinenwort passt, ist als Zwischenspeicher höchstens eine konstante Anzahl von Maschinenwörtern erforderlich.)$n \log_2 \left| \Sigma \right|$$O(\log n)$

Das ist also ziemlich gut. Aber was ist, wenn wir einen wahlfreien Zugriff wünschen?

Es stellt sich heraus, dass es möglich ist. Die erste Technik dazu wurde erst vor etwa vier Jahren entdeckt. Wir können die Sequenz in speichern Bits, so dass das Lesen oder Schreiben eines Eintrags Zeit benötigt. Wenn Sie darüber nachdenken, ist dies ein bemerkenswertes Ergebnis, da dies bedeutet, dass ein Computer, der mit einem beliebigen Radix arbeitet, in gewissem Sinne einem binären Computer entspricht.O ( 1 $n \log_2 \left| \Sigma \right|$$O(1)$

Hier ist das Papier: Jewgenij Dodis, Mihai Pătraşcu und Mikkel Thorup, Eine Alternative zur arithmetischen Codierung mit lokaler Dekodierbarkeit , STOC 2010.

Denken Sie übrigens an den Namen Mihai Pătraşcu. Er war und ist das, was wir einem modernen Évariste Galois am nächsten kommen. Er starb sehr jung an einem Gehirntumor im Alter von 29 Jahren. In seiner kurzen Karriere als Informatiker revolutionierte seine Arbeit jedoch das Gebiet der Analyse von Algorithmen auf eine Weise, deren Verständnis Jahrzehnte dauern wird.

Wenn Sie eine Zahl (z. B. 123456789⏨) als Text haben, können Sie diese in eine andere Basis schreiben (z. B. 21i3v9 in Basis 36), sodass Sie sie als Text komprimieren (von 9 auf 6 Zeichen).

Wenn Sie weiter gehen, speichern Sie es am Ende in Binärform (4 Bytes¹).

Dies funktioniert nun, weil Sie mit einem reduzierten Satz [0-9] begonnen und zu einem größeren [0-9a-z] verschoben haben und viele Datenbits in der anfänglichen Darstellung nicht verwendet wurden.

Wenn wir wissen, dass eine Datei nur Buchstaben enthält, können wir sie leicht komprimieren, indem wir die Basis ändern. Wenn Sie jedoch aus beliebigen Inhalten komprimieren , funktioniert dies (immer) nicht. Sie können einige Dateien komprimieren (kleinere Ausgaben erhalten), andere werden jedoch größer, ebenso wie jede verlustfreie Komprimierungsmethode . Dies ist unvermeidlich.

Es kann jedoch immer noch nützlich sein, zum Beispiel eine Methode, die englische Texte gut komprimiert, aber chinesische Texte größer macht, kann gut genug sein, wenn Sie viel mehr Englisch als Chinesisch schreiben.

¹ Eigentlich benötigen Sie nur 2²⁷ Bit, obwohl der Computerspeicher heutzutage ein Vielfaches von 8 Bit verwendet (aber vielleicht wollten Sie eine Reihe von Zahlen von 2²⁷ Bit speichern? ☺).

Basis 80 ?? Warum 80? Es macht keinen Sinn, Basis 85 jedoch. Dies ist sehr praktisch, da Sie 4 Bytes mit 5 Zeichen darstellen können (da 85 ^ 5 = 4.437.053.125, was etwas mehr als 2 ^ 32 = 4.294.967.296 ist).

Hier ist mein Code zum Schreiben eines einzelnen 32-Bit word:

for (i=0; i<5; i++)
{
    c = (word % 85) + 37;
    word /= 85;
    fwrite(&c, sizeof(uint8_t), 1, file);
}

und hier ist zum Zurücklesen:

    word = 0;
    for (i=4; i>=0; i--)
        fread(&c[i], sizeof(uint8_t), 1, file);

    for (i=0; i<5; i++)
        word = word*85 + c[i]-37;

Wenn Sie wirklich Base 80 verwenden möchten, können Sie denselben Ansatz verwenden und die Instanzen von 85 durch 80 ersetzen. Sie benötigen 6 Zeichen für jeweils 4 Bytes anstelle von 5.

Wie wird es etwas komprimieren? Sie erkennen, dass Dateien in Base 256 geschrieben sind, oder? Wenn Sie eine in Base 85 geschriebene Datei komprimieren, hat sie ungefähr die gleiche Größe wie die komprimierte ursprüngliche Base 256-Datei. Daher ist Base 85 (oder Base 64) eine gute Wahl, wenn Sie Binärdaten mit druckbaren Zeichen darstellen möchten.

Unterschiedliche Basen werden für unterschiedliche Zwecke verwendet, obwohl Sie, wie die anderen Antworten erklären, in Bezug auf die Komprimierung nichts gewinnen werden.

Eine Erklärung der Base64-Codierung finden Sie in Wikipedia . Base 64 wird häufig nicht zur Komprimierung verwendet, sondern zum Codieren von Binärdaten, die normalerweise zu nicht druckbaren Zeichen und Steuercodes führen, in einen druckbaren ASCII-Zeichenraum. Dies führt zu einer größeren Dateigröße, ist jedoch nützlich für die Übertragung von Binärdaten, die in andere ASCII-Dateien eingebettet werden können, z. B. in XML, E-Mails, CSS, Webseiten usw.