Große Zahlen komprimieren

[supercracker13]

Hallo Leute, ich bin gerade dabei ein kleines Programm am schreiben, das Problem ist das dabei große Zahlen anfallen und ich eine Möglichkeit suche diese zu komprimieren.
Als Ganze Zahl kann man das wahrscheinlich nicht sehen da sehr schnell Größen um die 30k Zeichen anfallen.

Kennt ihr rein zufällig eine Methode um solche Zahlen zu komprimieren, muss nicht schnell gehen sondern nur stark komprimieren.
Besonders oft kommt die Zahl 9 vor, falls das hilft.
Hier ist mal ein Ausschnitt aus einer Zahl:

 Spoiler

99192939459697989596979897989919292939459697989596 97989798991929293949569798991697989918991929393949 56979899169798991293949592939495949596979798991929 29394959679899192798991929192939494959679899192798 99192919293949495959697989798991919293949569798991 29394959293949594959697979899192919293949495967989 91923949596939495969596969798991923949595969798991 29394949596979891929394919293929394959596979891929 39491929389919279899189919293929394959596979899129 39495929394956979899169796979899191929394956979899 12939459697989192939491929394939495969596979697989 79899189919292939495967989919239495697989596979897 98991929293929394939495969697989919239495969394959 69596939459697979897989596798959697989798959679798 99129394959293949394959696979899192394956979898991 92929394949596978991923949569798919293495969794959 69794959693949592939491929394939495969697989899192 93495697989912939459697949596978989918991697949596 93949594959293494959697899169798991899192939394939 49192939493949594959695969796979897989919279891919 291929394949596979891927

In der Ganzen Zahl beträgt die 9 ca 50% und das wird in den anderen Zahlen ebenso sei, darum habe ich schon mal gedacht ob man die Ganze zahl umdreht (wusste keinen Fachausdruck xD) also eigentlich bei jeder Ziffer 10-x, also zb aus 9 wird 1.
Damit wären die Zahlen um einiges kleiner.

Nur die Frage diese zu komprimieren. Ich weis man kann es in Bytes umwandeln also zb. 122 = z und so das ganze komprimieren. Leider sind damit keine hohen Kompressionsraten möglich (soweit ich mir jetzt denken kann).

Habt ihr dazu eine kleine Anregung, wäre echt geil

['Heaven.]

GZIP

[strubelz]

Ich hab gelesen, das bzip2 besser komprimiert, aber länger zum komprimieren braucht. Da du ja eine stärkere Kompressionsrate willst solltest du vieleichtneher bzip2 nehmen.

[マルコ]

So weit ich das verstehe möchtest du die Kompression in-memory machen um die Zahl dann direkt wieder verwenden zu können? In dem Fall wäre eine Umcodierung mit Huffman sinnvoll. Dazu brauchst du einen Binary Stream, den du mit einer Lese- und Schreiblogik versiehst. Wie das ganze genau funzt, kannst du hier nachlesen. Den Code für jedes Zeichen musst du nicht jedes Mal neu berechnen, solltest es aber zumindest alle paar tausend Zeichen machen.

[supercracker13]

Ok danke schonmal. Leider suche ich etwas zur dauerhaften Speicherung von Daten und nicht zur direkten wiederverwendung. Hätte ich besser dazu geschrieben.
Mit Huffman habe ich mich auch schon auseinandergesetzt nur leider basiert es darauf, das Zeichen die häufiger vorkommen kleinere Nummern bekommen und die die seltener Vorkommen größere Nummern. Leider gibt es nur einen Unterschied zu 9 und alle andere Zahlen sind ungefähr zur gleichen Zahl vorhanden. Darum glaub ich ist es nicht so effektiv wie ich es gerne hätte. (Wenn das nicht stimmt könnt ich mich gerne verbessern).
Ich versuche jetzt nochmal meinen eigenen Algorithmus zu verbessern.

Edit bitte Lesen ob das Funktioniere würde:
Angenommen ich würde mit Huffman meine Zahl encoden. Dann kommt man der minimalen Entropie ja schon mal ziemlich nah, sodass man es nicht, oder nur minimal noch komprimieren kann.
Würde ich jetzt mit einer bestimmen Funktion die Bytes erhöhen und vermindern, sodass eine neue Dateistruktur ensteht, müsste man es doch noch mal komprimieren können oder ?.
z.B Jedes 7 um 63 erhöhen, jedes 3 um 117 und jedes 13 um 19. Dann sollten doch eigentlich die Daten neue Werte erhalten, sodass man sie neu strukturieren kann. Man muss nur die Funktion wissen um das Ganze umzukehren.
Für mich hört sich das zwar logisch an, wird aber wahrscheinlich nicht wie gewollt funktionieren. Könnt ihr mir den Grund dafür sagen, falls es nicht funktionieren sollte ? (Wenn ich nicht selber drauf komme ^^)

[Schlüsselbein]

Woher kommen die Zahlen? Was hast du mit den Zahlen vor?
@Deine Idee: Es geht bei der Kodierung doch darum, die Information zu behalten und die Redundanz zu entfernen. Spinn das mal weiter und du solltest wissen warum (genaueres dazu kann dir sicher einer der Infostudenten erzählen).

[tayfe]

Ich studiere kein Informatik und habe auch all die anderen Alogirthem etc. noch nie gehört. Aber vllt. hilft es ja trotzdem

Ich habe ganz einfach daran gedacht, die Zahlen durch Division und Wurzelziehung zu verkleinern. So kann man ja auch große Zahlen stark verkleinern. Es würde dann vermutlich wirklich etwas länger dauern mit der Kompression, aber zumindest hättest du dann kleine Zahlen, die nur noch zusammengerechnet werden müssen.

War nur mal so mein kleiner Gedanke, keine Ahnung, ob das hilft

[supercracker13]

Das könnte ich auch mal probieren mit bestimmten Rechenwegen die Zahlen zu verkleineren, dabei muss man nur beachten, das die Zahlen nachher einheitliche Stellenanzahlen bekommen, damit man die Daten auch wieder heraus bekommt.

@Schlüsselbein: Ich hatte das bei meinem Beispiel folgender Maßen gemeint:

 Spoiler

Das hier ist mein Text: Hallo wie geht es dir ? = 23 Bytes
Mit Huffman: 254 0 219 29 89 92 155 73 159 105 30 = 11 Bytes
Meine Idee: 254 30 219 159 89 122 159 203 159 135 30 = 11 Bytes
(Jedes 2. um 30, jedes 4. um 100 und jedes 7. um 4 erhöht)
Mit Huffman: 243 120 56 161 220 220 141 = 7 Bytes

Die Daten gehen dabei eigentlich nicht verloren, da man das ganze auch wieder Rückwärts laufen lassen kann, also zuerst Huffman decodieren. Dann die Zahlen die ich erhöht habe einfach vermindern und nochmal Huffman decodieren. Ich weis das man noch die Daten von Huffman dazu schreiben muss um das ganze zu dekomprimieren. In Relation zu meinem kleinen Text wäre das natürlich schon viel aber hat man eine Datei mit 1Gb ist es kaum nennenswert.
Das war jetzt so meine Theorie wie man Dateien noch besser komprimieren könnte, oder warum geht das nicht.

Kleiner Test:

 Spoiler

Nochmal meins: 243 150 56 36 220 250 145 = 7 Bytes
Nochmal Huffman: 97 249 205 54 13 = 5 Bytes

PS: Habe dafür jetzt Onlinetools benutzt, also falls etwas falsch konvertiert ist wisst ihr wodran es liegt ^^

[Schlüsselbein]

Du hast uns immer noch nicht verraten, was du mit den Zahlen vor hast bzw. wo sie herkommen.

Zu Hufmann: Zu deinem Beispiel oben: Schreib dir mal ein kleines Beispielprogramm dazu und denke ans decoden. Du verschiebst den Informationsgehalt nur.