String komprimieren

[Lichtgestalt]

Hallo Ihr Balltreter,

kann mir jemand helfen einen String zu komprimieren? Also ich habe einen String, der kann ziemlich lang werden. Es handelt sich dabei um ein serialisiertes Array in JavaScript, z.B.:

a=s|class:tag=[:a=s|SUP:BODY=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|2]:j=[:0=[:0=i|7:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|4:1=i|6]]:k=[:0=i|5:1=i|0]:l=null|null:m=b|false]:a=s|d]]:B=[:a=s|b:b=[:a=s|c]]:H1=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|7:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:a=s|c]:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]:P=[:a=s|b:b=[:a=s|c]]:SUP=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|3]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:e=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|3:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:f=[:0=i|3]:a=s|d]]]:class=[:a=s|.special2:.special=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|3]:j=[:0=[:0=i|3:1=i|2]]:k=[:0=i|5:1=i|0]:l=null|null:m=b|false]:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]

Ist jetzt nur ein Beispiel. Der kann noch viel länger werden. Da ich den auch speichern und verschicken will, sollte er möglichst kurz werden. Gibt es vielleicht einen schlauen Algorithmus, da Muster (bzw. sich wiederholende Zeichengruppen) zu finden, die ich dann durch einzelne Zeichen ersetzen kann?

mfG, Lichtgestalt

[seth]

gudn tach!

kann mir jemand helfen einen String zu komprimieren?

die string-komprimier-onkel.

Gibt es vielleicht einen schlauen Algorithmus, da Muster (bzw. sich wiederholende Zeichengruppen) zu finden, die ich dann durch einzelne Zeichen ersetzen kann?

lz77 und lz78 von onkel ziv und onkel lempel.

anschliessend zum zeichenhaeufigkeitsbasierten komprimieren, weiss vielleicht noch onkel huffman rat.

prost
seth

[Lichtgestalt]

Dankeschön, da hab ich ja erstmal was zu lesen .)

[Christoph Schnauß]

hallo,

Hallo Ihr Balltreter

Grmpf, wasn das für eine Anrede :-(

kann mir jemand helfen einen String zu komprimieren? Also ich habe einen String, der kann ziemlich lang werden. Es handelt sich dabei um ein serialisiertes Array in JavaScript

Wenn dein String einmal vorhanden ist, wirst du ihn wohl kaum mehr "eindampfen" können. Es bleibt dir nur eine Möglichkeit: schau nach, wie dein String überhaupt entsteht und überlege, ob du ihn nicht gleich in deutlicher "menschenlesbarer" Form zusammenbauen kannst. Sofern er keine Fehler aufweist, ist deinem Rechner das ziemlich schnuppe, ob du ihn noch lesen kannst, er kann sicher was damit anfangen.

Der kann noch viel länger werden.

Oh. Er hat ja jetzt schon eine gewisse fraktale Grazilität.

Da ich den auch speichern und verschicken will

Hm. Nur mal so: wie willst du ein Javascript-Erzeugnis speichern? Und warum willst du es dann ohne das übliche "Drumherum" an Content verschicken - eventuell per mail?

Gibt es vielleicht einen schlauen Algorithmus, da Muster (bzw. sich wiederholende Zeichengruppen) zu finden, die ich dann durch einzelne Zeichen ersetzen kann?

Auch in Javascript kannst du Reguläre Ausdrücke verwenden. Es nutzt dir nur nicht viel, weil du zur Programmausführung dann wieder eine Funktion brauchst, die deine Ersetzungen gewissermaßen rückgängig macht, so daß der Code ausgeführt werden kann.

Grüße aus Berlin

Christoph S.

[Lichtgestalt]

Wenn dein String einmal vorhanden ist, wirst du ihn wohl kaum mehr "eindampfen" können.

komm komm, ich habe mir jetzt eine Funktion gebastelt und aus diesem:

a=s|class:tag=[:a=s|SUP:BODY=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|9:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:a=s|d]]:B=[:a=s|b:b=[:a=s|c]]:H1=[:a=s|b:b=[:a=s|c]:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]:P=[:a=s|b:b=[:a=s|c]]:SUP=[:a=s|b:b=[:a=s|c]]]:class=[:a=s|.special2:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]a=s|class:tag=[:a=s|SUP:BODY=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|9:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:a=s|d]]:B=[:a=s|b:b=[:a=s|c]]:H1=[:a=s|b:b=[:a=s|c]:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]:P=[:a=s|b:b=[:a=s|c]]:SUP=[:a=s|b:b=[:a=s|c]]]:class=[:a=s|.special2:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]a=s|class:tag=[:a=s|SUP:BODY=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|9:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:a=s|d]]:B=[:a=s|b:b=[:a=s|c]]:H1=[:a=s|b:b=[:a=s|c]:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]:P=[:a=s|b:b=[:a=s|c]]:SUP=[:a=s|b:b=[:a=s|c]]]:class=[:a=s|.special2:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]a=s|class:tag=[:a=s|SUP:BODY=[:a=s|b:b=[:c=[:i=[:0=i|1:1=i|1]:j=[:0=[:0=i|5:1=i|4]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:d=[:i=[:0=i|1:1=i|0]:j=[:0=[:0=i|9:1=i|2]]:k=[:0=i|0:1=i|0]:l=null|null:m=b|false]:a=s|d]]:B=[:a=s|b:b=[:a=s|c]]:H1=[:a=s|b:b=[:a=s|c]:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]:P=[:a=s|b:b=[:a=s|c]]:SUP=[:a=s|b:b=[:a=s|c]]]:class=[:a=s|.special2:.special=[:a=s|b:b=[:a=s|c]]:.special2=[:a=s|b:b=[:a=s|c]]]

wurde dieser:

þ!b:b!c]Cþb:bEþ]]:Fþ()*+,-:Gþ/ss:tagIþ!S;!<=[Jþ$%>&i|?Kþd=[$%|0Lþj=[&i@2Mþass!#l2Nþ]:j=[Qþi|Rþ0]:TþclaVþ:1=iXþ[:ZþUP\þÿ=Za=s|!ÿ.specia#ÿ:i=Z0=$ÿR1X%ÿ:0=Z0=&ÿFk=Z(ÿ0=R0:1)ÿ=RTl*ÿ=null|n+ÿull:m=b,ÿ|false]-ÿa=s|V/ÿ:BODY;ÿE=Zc<ÿ|1Q>ÿ5:1=R4?ÿ|9:1=R@ÿs|dFBAÿIJKGL]:MGa=AC]:H1C:#lC]:#l2CFPC]:S\CFclN:#lC]:#l2C]]IJKGL]:MGa=AC]:H1C:#lC]:#l2CFPC]:S\CFclN:#lC]:#l2C]]IJKGL]:MGa=AC]:H1C:#lC]:#l2CFPC]:S\CFclN:#lC]:#l2C]]IJKGL]:MGa=AC]:H1C:#lC]:#l2CFPC]:S\CFclN:#lC]:#l2C]]

das sind nur noch 26% der Ausgangslänge. Zugegeben schaffe ich diese Raten nur bei ziemlich langen Strings (dieser hatte 1788 Zeichen), aber immerhin ist das doch wohl mehr als "kaum" :-)

Hm. Nur mal so: wie willst du ein Javascript-Erzeugnis speichern?

per Hand in einer .txt-Datei oder in einem Cookie.

Und warum willst du es dann ohne das übliche "Drumherum" an Content verschicken - eventuell per mail?

damit andere das Programm mit der gleichen Einstellung öffnen können.

Es nutzt dir nur nicht viel, weil du zur Programmausführung dann wieder eine Funktion brauchst, die deine Ersetzungen gewissermaßen rückgängig macht, so daß der Code ausgeführt werden kann.

ach nee, das hatte ich eigentlich als selbsvertändlich vorausgesetzt ,-) Mein Entpacker geht übrigens auch schon tadellos :-)

Aber mir ist bei dieser ganzen Sache ein ganz anderer Gedanke gekommen: je stärker der String komprimiert wird, desto zufälliger - "chaotischer" - wird die Zeichenverteilung. Sonst - wenn es noch Muster gäbe - könnte man ja weiterkomprimieren. Aber dieser komprimierte Chaos-String enthält ja troztdem die gleiche Information, wie der entpackte, sonst ließe er sich ja nicht eindeutig entpacken. Also schlußfolgere ich: je komplexer oder chaotischer ein Muster, desto höher ist die darin enthaltene Informationsdichte. Ist das der Inhalt der "Chaosforschung"?

[seth]

gudn tach!

Wenn dein String einmal vorhanden ist, wirst du ihn wohl kaum mehr "eindampfen" können.

komm komm, ich habe mir jetzt eine Funktion gebastelt und [...]
nur noch 26% der Ausgangslänge.

ich weiss auch nicht, was Christoph damit gescheites sagen wollte, zumal er das postete, lange _nachdem_ ich auf die kompressionsverfahren gedeutet hatte.
ich hatte sogar schon eine antwort verfasst, von der ich jedoch beim erneuten durchlesen (lang lebe die vorschau!) glaubte, sie wuerde als zu unhoeflich und nicht besonders inhaltsreich aufgenommen werden, weshalb ich sie - aus faulheitsgruenden, sie umzuformulieren - einfach nicht abschickte.

Hm. Nur mal so: wie willst du ein Javascript-Erzeugnis speichern?

per Hand in einer .txt-Datei oder in einem Cookie.

hmm, vielleicht waere es ja auch moeglich, einfach den kram einem serverseitigen script (z.b. perl, stichwort: "backticks") zu uebergeben, welches den text mit bzip2 oder so komprimiert. dann wird's sogar noch etwas kleiner.
kommt allerdings stark darauf an, welche moeglichkeiten dir zur verfuegung stehen.

Mein Entpacker geht übrigens auch schon tadellos :-)

wenn nichts allzu viel code ist, der auch noch halbwegs sauber kommentiert ist, kannst du ihn ja hier posten. fuers archiv.

Aber mir ist bei dieser ganzen Sache ein ganz anderer Gedanke gekommen: je stärker der String komprimiert wird, desto zufälliger - "chaotischer" - wird die Zeichenverteilung. Sonst - wenn es noch Muster gäbe - könnte man ja weiterkomprimieren. Aber dieser komprimierte Chaos-String enthält ja troztdem die gleiche Information, wie der entpackte, sonst ließe er sich ja nicht eindeutig entpacken. Also schlußfolgere ich: je komplexer oder chaotischer ein Muster, desto höher ist die darin enthaltene Informationsdichte. Ist das der Inhalt der "Chaosforschung"?

wow! das ist doch mal ne frage. meine "antwort" faellt allerdings eher nuechtern aus, weil ich auch nicht so fit in dieser materie bin.

kurz: imh(!)o jein!

ich vermute eher, dass es ein bestandteil der informationstheorie ist. allerdings ueberschneiden sich diese gebiete hier wohl ziemlich, denn auch in der chaosforschung oder allgemeiner bei dynamischen systemen werden solche fragen nach dem informationsgehalt angesprochen.

wenn du wirklich was darueber wissen willst, wirst du wohl nicht um das intensive studium einiger buecher kommen. fuer den anfang mag das auch schon recht grosse angebot der wikipedia (nicht immer nur deutsch!) genuegen. und fuer intensivere informationen wird dort ja haeufig auf standardwerke verwiesen, die dir weiterhelfen koennen wollen/sollen.

noch ein wort zu deiner ("umkehr"-)schlussfolgerung: die folgerung stimmt so afais nicht, denn ein _zufaelliges_ muster koennte beliebig komplex sein und muesste dennoch nicht fuer eine hochkomprimierte information stehen. allerdings ist das auch wieder abhaengig von der definition von "information".

prost
seth

[Sven Rautenberg]

Moin!

Aber mir ist bei dieser ganzen Sache ein ganz anderer Gedanke gekommen: je stärker der String komprimiert wird, desto zufälliger - "chaotischer" - wird die Zeichenverteilung. Sonst - wenn es noch Muster gäbe - könnte man ja weiterkomprimieren. Aber dieser komprimierte Chaos-String enthält ja troztdem die gleiche Information, wie der entpackte, sonst ließe er sich ja nicht eindeutig entpacken. Also schlußfolgere ich: je komplexer oder chaotischer ein Muster, desto höher ist die darin enthaltene Informationsdichte. Ist das der Inhalt der "Chaosforschung"?

Nein, die Chaosforschung hat dann doch ein etwas anderes Themengebiet.

Aber die Informationstheorie behandelt solche Dinge, wie z.B. die Zunahme der zufällig wirkenden Muster bei Komprimierungsalgorithmen.

In Kurzform: Jede Abfolge von Informationen (z.B. Textstrings) bestehen aus unterschiedlichen "Symbolen" eines "Alphabets". Bei Textstrings sind die Symbole die einzelnen Zeichen, und das Alphabet ist die gesamte Zeichentabelle. Jedes Symbol wird repräsentiert durch ein bestimmtes Bitmuster.

Einfaches Konstrukt: Die Symbole sind alle Zeichen der ASCII-Tabelle, jedes Zeichen ist 8 Bit lang. Wenn jetzt aber im String nur Kleinbuchstaben vorkommen, oder anders gesagt: Nur eine definiert kleine Untermenge aller 8-Bit-Symbole, dann ist ja die Definition der ungenutzten Symbole reine Platzverschwendung.

Die Informationstheorie definiert nun zwei Begriffe: Entropie und Redundanz, die beide direkt miteinander zusammenhängen. Die Entropie ist ein Maß für die Zufälligkeit einer Information, die Redundanz das Gegenteil. Kurzes Rechenbeispiel: Wenn ich 8 Bit für die Codierung von Kleinbuchstaben nutze, in Wirklichkeit sind aber nur 5 Bit notwendig (Bytes 0 bis 31), dann habe ich in dem 8-Bit-Datenstrom eine Entropie von 5 Bit, und eine Redundanz von 3 Bit. Eine verlustfreie Komprimierung kann im Idealfall die gesamte Redundanz der Information "wegrechnen". Das Ergebnis ist, dass die Zufälligkeit des Datenstroms steigt, denn statt 5 von 8 Bit Entropie sind es jetzt 5 von 5 Bit (also 100%).

In Wirklichkeit ist es noch komplexer: Ein deutscher Text in Kleinbuchstaben hat ja nicht 32 verschiedene Buchstaben, sondern nur 26. Außerdem kommen bestimmte Buchstaben wie E, R, N, S, T, L viel häufiger vor, als andere. Auf den Buchstaben Q folgt beispielsweise auch extrem häufig ein U. All diese Abweichungen von kompletter Zufälligkeit senken die Entropie und heben die Redundanz. Dabei kommt es (siehe Berechnungsvorschrift) rechnerisch zu Kommazahlen für Redundanz und Entropie. Vielleicht hat der Kleinbuchstabentext also keine Entropie von 5 Bit, sondern eventuell nur 4,1 Bit. Man könnte also bis zu 3,9 Bit Redundanz herauskomprimieren.

Das funktioniert aber nur, wenn das Kompressionsverfahren exakt auf den konkreten Text abgestimmt ist. Allgemeine Verfahren nutzen Ansätze, die meistens gute Ergebnisse bringen, aber eben nicht überall ideale.

Als Extrembeispiel: Angenommen, der Text bestünde nur aus den zwei Worten "ja" und "nein" - dann wäre die Entropie des Textes vermutlich 1 Bit - für jedes "nein" benutzt man also lieber ein Nullbit, für jedes "ja" ein Einsbit. Die Redundanz, die der Text bei 8 Bit Zeichenbreite hätte, wären 7 Bit.

Wobei auch das nicht stimmt, denn die Folge von "ja" und "nein", als Bitfolge betrachtet, ist vermutlich auch nicht komplett zufällig, sondern hat gewisse Wahrscheinlichkeiten, und damit auch weiter komprimierbare Redundanz. :)

- Sven Rautenberg

[Manuel B.]

Ich grüsse den Cosmos,

Wenn dein String einmal vorhanden ist, wirst du ihn wohl kaum mehr "eindampfen" können.

Und wie funktinieren dann Packprogramme? Meinst du, die können nichts komprimieren, was schon vorhanden ist? Entweder fehlt deiner Aussage völlig der Sinn, oder er kommt nur nicht rüber. Kannst du deine Aussage verdeutlichen?

Möge das "Self" mit euch sein