Kann man eine kurze Zeichenfolge zuverlässig komprimieren?

Wenn Sie, wie Sie angegeben haben, Ihre Ausgabezeichenfolgen die gleichen Zeichen wie die Eingabezeichenfolge verwenden müssen, und wenn Sie nichts Besonderes über die Anforderungen der Eingabezeichenfolge wissen, dann ist es nicht möglich, zu komprimieren jede mögliche 53-stellige Zeichenfolge bis zu 50 Zeichen. Dies ist eine einfache Anwendung des Fachprinzips .

• Ihre Eingabezeichenfolgen können als eine 53-stellige Zahl in Basis 67 dargestellt werden, dh eine Ganzzahl von 0 bis 67 ⁵³ - 1> 6 * 10 ⁹⁶ .
• Sie möchten diese Zahlen einer Ganzzahl von 0 bis 67 ⁵⁰ - 1 ÷ 2 * 10 ⁹¹ zuordnen.
• Nach dem Prinzip der Schublade können Sie also sicherstellen, dass 67 ³ = 300,763 verschiedene Eingaben jedem möglichen Ausgang zugeordnet werden - was bedeutet, dass Sie beim Dekomprimieren keine Möglichkeit haben wissen Sie, auf welches dieser 300,763 Originale Sie zurückmelden sollen.

Damit das funktioniert, müssen Sie Ihre Anforderungen ändern. Sie könnten einen größeren Satz von Zeichen verwenden, um die Ausgabe zu codieren (Sie könnten sie auf 50 Zeichen herunterrechnen, wenn jede 87 mögliche Werte hätte, anstatt die 67 in der Eingabe). Oder man könnte eine Redundanz in der Eingabe identifizieren - vielleicht kann das erste Zeichen nur eine "3" oder eine "5" sein, das Neunzehnte und Zwanzigste sind eine Zustandsabkürzung, die nur 62 verschiedene mögliche Werte haben kann, so etwas.

Wenn Sie keines dieser Dinge tun können, müssen Sie einen Kompressionsalgorithmus verwenden, wie Huffman-Kodierung, und die Tatsache akzeptieren, dass einige Strings komprimierbar (und kürzer werden) und andere nicht (und werden) get länger ).

Was Sie fragen, ist im allgemeinsten Fall nicht möglich, was sich sehr einfach nachweisen lässt.

Nehmen wir an, es war möglich, eine beliebige 53 Zeichen lange Zeichenfolge in 50 Zeichen zu codieren. Tun Sie das und fügen Sie dann drei zufällige Zeichen zur codierten Zeichenfolge hinzu. Dann haben Sie eine andere beliebige, 53 Zeichen lange Zeichenfolge. Wie komprimierst du das?

Was Sie wollen, kann nicht garantiert werden, dass Sie für mögliche Daten arbeiten. Es ist jedoch möglich, dass all Ihre realen Daten eine Entropie haben, die ausreicht, um ein Schema zu entwickeln, das funktioniert.

In diesem Fall werden Sie wahrscheinlich eine Variante der Huffman-Codierung verwenden wollen, die im Grunde Bitcodierungen mit variabler Bitlänge für die Zeichen in Ihrer Menge zuweist, wobei die kürzesten Kodierungen für die am häufigsten verwendeten Zeichen verwendet werden. Sie können alle Ihre Daten analysieren, um eine Reihe von Codierungen zu erstellen. Nach der Huffman-Codierung ist Ihre Zeichenfolge ein (hoffentlich kürzerer) Bitstream, den Sie mit 6 Bit pro Zeichen in Ihren Zeichensatz codieren. Es kann kurz genug für alle Ihre realen Daten sein.

Eine Bibliothek-basierte Codierung wie Smaz (in einer anderen Antwort verwiesen) funktioniert möglicherweise auch. Auch hier kann nicht garantiert werden, dass es für alle möglichen Daten funktioniert.

Ein Byte (Zeichen) kann 256 Werte (0-255) kodieren, aber Ihr Satz gültiger Zeichen verwendet nur 67 Werte, die in 7 Bits (leider werden 6 Bits nur 64 Zeichen enthalten) und keinem Ihrer Zeichen dargestellt werden können verwendet das High-Bit des Bytes.

Gegeben, dass Sie das hohe Bit wegwerfen und nur 7 Bits speichern können, indem Sie die Anfangsbits des nächsten Zeichens in das "freie" Feld des ersten Zeichens schreiben. Dies würde nur 47 Byte Speicherplatz benötigen. (53 x 7 = 371 Bits, 371/8 = 46,4 == 47)

Dies wird nicht wirklich als Komprimierung betrachtet, sondern eher als eine Änderung der Codierung .

Zum Beispiel ist "ABC" 0x41 0x42 0x43

Als Beispiel werden diese 3 Zeichen keinen Speicherplatz speichern, aber Ihre 53 Zeichen werden immer als 47 ausgegeben, garantiert.

Beachten Sie jedoch, dass die Ausgabe nicht in Ihrem ursprünglichen Zeichensatz enthalten ist, wenn dies für Sie wichtig ist.

Der Prozess wird:

Wenn ich mich richtig erinnere, wird die Huffman-Codierung die kompakteste Art sein, die Daten zu speichern. Es ist zu lange her, dass ich es verwendet habe, um den Algorithmus schnell zu schreiben, aber die allgemeine Idee ist hier , aber wenn ich mich richtig erinnere, was du tust, ist:

1. Erhalte die Anzahl für jedes verwendete Zeichen
2. priorisieren sie basierend darauf, wie oft sie aufgetreten sind
3. Erstellen Sie einen Baum basierend auf der Priorisierung
4. Erhalte die komprimierte Bit-Darstellung jedes Zeichens, indem du den Baum durchquerst (start an der Wurzel, links = 0 rechts = 1)
5. Ersetzen Sie jedes Zeichen durch die Bits aus dem Baum

Smaz ist eine einfache Komprimierungsbibliothek, die sich zum Komprimieren sehr kurzer Strings eignet.