[Wettbewerb] String komprimieren

Ich nominiere mich mit dem pastebin Beispiel selbst als Kandidat für den "worst abuse of the rules" Award. Dicht gefolgt von der Methode den vollständigen Text im Code zu speichern und nur auszugeben

Zitat von Oscar

Die Länge beträgt nun 6033 Bytes und befindet sich in der Datei "original.txt" im ZIP-Archiv.

Eigentlich sind es nicht 6033 Bytes sondern 6033 Zeichen.

Da die Kodierung der Datei UTF-8 ist und einige Zeichen außerhalb des ASCII-Bereiches enthalten sind, wird für einige Zeichen mehr als 1 Byte benötigt.

Der String hat daher eine tatsächliche Größe von 6105 Bytes.

Man könnte daher schon alleine durch die Umkodierung in ISO 8859-2 1,2% Dateigröße einsparen.

In der Bewertung hier würde dies jedoch nicht honoriert werden, da diese ausschließlich auf die Zeichenanzahl abstellt.

Noch wilder würde es, wenn man diesen Umstand ausnutzt und den großen Wertebereich von UTF-32 nimmt um jeweils 4 Ausgangszeichen in nur ein einziges UTF-32-Zeichen zusammenzufassen (analog geht auch UTF-16).
Auf diese Weise würde man hier als wahrscheinlicher Sieger vom Platz gehen, da wir nur noch 25% soviele Zeichen haben, obwohl die Dateigröße nahezu gleich bleibt.

Daher plädiere ich dafür, die Bewertung komplett von der Zeichenlänge zu entkoppeln und nur die resultierende Dateigröße als Bewertungsmaßstab zu verwenden.

Mal zur Verdeutlichung - Folgende 2 Funktionen:

Func _StringCompress($sString)
    Return BinaryToString(StringToBinary($sString & (Mod(StringLen($sString), 2) ? Chr(0) : ""), 4), 2)
EndFunc

Func _StringDecompress($vCompress)
    Return BinaryToString(StringToBinary($vCompress, 2), 4)
EndFunc

würden zu einer Bewertungskompressionsrate von 49.395 % führen obwohl eine hieraus resultierende Datei genauso groß ist wie die Ausgangsdatei. (hier speziell sogar noch 3 Byte mehr, da die ungerade Anzahl an Bytes hier einfach nicht behandelt wurde)

Zitat von Oscar

Wenn ich die Datei als UTF8_NOBOM einlese und die komprimierte Datei als Binary speichere, danach wieder als Binary einlese und mit dem Original vergleiche, dann stimmen die Daten nicht mehr, weil jetzt ANSI.

Die wird nur als ANSI interpretiert wenn du veranlasst, dass der Binary als ANSI zu interpretieren ist.
Vielleicht steckt auch gar kein String in der Datei sondern eine ganz andere Struktur, so dass erst bestimmte weitere Schritte durchgeführt werden müssen?

Kurz: Wenn die Funktionen gar keine Strings als Input und Output bekommen sollen, sondern Dateinamen, dann hat sich der Teilnehmer darum zu kümmern, dass die komprimierte Datei korrekt in eine Datei geschrieben werden und von dort auch korrekt wieder eingelesen werden.

Der Größenvergleich ist hier einfach und fair, da einfach nur die beiden Dateigrößen miteinander verglichen werden müssen.

Die beiden Funktionen _StringCompress() und _StringDecompress() werden also um Dateioperationen erweitert:

; komprimiert den String $sString und speichert das Komprimat (gibts das Wort?) in die Datei $sFilePath
Func _StringCompress($sString, $sFilePath)


; extrahiert aus der komprimierten Datei $sFilePath den Ausgangsstring
Func _StringDecompress($sFilePath)
    ...
    Return $sString

Zitat von Oscar

Wenn ich die Datei als UTF8_NOBOM einlese und die komprimierte Datei als Binary speichere, danach wieder als Binary einlese und mit dem Original vergleiche, dann stimmen die Daten nicht mehr, weil jetzt ANSI.

Beim Einlesen der Daten mit angegebenem Encoding UTF8_NOBOM, sollte AutoIt es intern in UCS2 umwandeln. Letzten Endes ist die Codierung ja aber egal, es muss nach dem Dekomprimieren nur das gleiche rauskommen, wie die Daten zuvor waren...

Neuster Stand mit Prekompressor:

============================================================

Result for "Ahnungslos"

============================================================

Decompressed = Original: True

Length Original: 6033

Length compressed: 3236

Length decompressed: 6033

Compress-Ratio: 46.362 %

Time compressed: 4420 ms

Time decompressed: 258 ms

============================================================

Ich hab etwa 2000 Zeilen Spaghetticode fabriziert der zu allem Überfluss auch noch ganz besonders langsam ist und nicht die Kompression erreicht die ich gerne hätte^^

Werde das irgendwann Morgen abgeben, viel Spaß beim Durchlesen Oscar

PS: Nächstes Mal wird die 50% in Angriff genommen. Das ist zwar noch ein paar Meter, aber das schaffen wir

Zitat von Mars

Ich hab etwa 2000 Zeilen Spaghetticode fabriziert

...willkommen im Club....

Ich bin durch eine Augen-OP seit einigen Wochen ziemlich eingeschränkt, daher weiß ich nicht, ob ich überhaupt bis zum Termin fertig werde. Aber die 50% habe ich schon (halbwegs locker) geknackt, sogar bei (*.unkomprimierteEXE-Binärdateien)

AspirinJunkie = Komprimat (gibts das Wort?)

Komprimat: [das] Substantiv, Neutrum
                     Zusammengefasstes, -gepresstes

Und selbst, wenn es das Wort nicht gegeben würde, würden wir dich aus dem Zusammenhang verstehen.

Und sonst haben wir die Möglichkeit nachzufragen, was es bedeuten würde. Ist ja alles auch nur Bewohner des blauen Planeten.

Ohje, wenn Andy die 50 geknackt hat muss ich wohl nochmal schrauben

Ich hatte einfach keine Lust auf alt bewährtes zurückzugreifen und hab meine Idee (Prediction geboosteter dynamischer Huffman Tree) weiterverfolgt. Leider hat das eine entscheidende Schwäche: Ganze Bits.

Egal wie gut die Vorhersage ist, im Regelfall kann man 3 Bit/Symbol nicht unterschreiten, da im Huffman-Tree, genauso wie bei Telefonnummern keine vollständigen 01-Ketten existieren dürfen die gleichzeitig der Anfang einer anderen Kette sind. Wenn es also eine 2Bit Kette gibt (z.B. "01"), dann kann es keine einzige weitere Kette geben die mit "01" beginnt. Der Tree wird "optimal" erstellt, und wird den Teufel tun, bei sämtliche anderen Zeichen die Bitketten um 1 zu verlängern, nur weil die Chance für ein "a" als nächstes Zeichen 20% ist (das wäre aber nötig um unter die 3Bit/Symbol zu kommen).

Der Ansatz ist super, rennt aber bei Huffman komplett gegen die Wand...

Nächste Idee ist dann: Prediction geboosteter arithmetischer Kodierer. Der sollte mindestens 10%-20% besser klarkommen (damit sollte auch 60% bei Text kein Problem sein).

Na da lag ich mit meiner Schätzung, dass mein Skript etwa im Mittelfeld landet ja perfekt richtig

Schade jedoch, dass es wirklich nur 3 Einsendungen gab.

Das Interesse daran schien anfangs ja größer zu sein (Andy? )

Hätte gerne weitere Ansätze gesehen.

Eventuell hatten einige Angst sich "zu blamieren", weil schon vorab Ergebnisse gepostet wurden?

Das wäre wirklich schade, denn z.B. bei mir lag die Optimierung rein aus persönlichen Interesse auf der möglichst optimalen Huffman-Kodierung.
Ich habe jedoch auch eine Vorkompilierung drin die wirklich simpel ist und in die ich nur wenig Zeit gesteckt habe.

Hier hatte ich auf Ansätze von anderen gehofft, welche bisschen mehr rausholen - das Potential ist definitiv da.

Am Ende hätte man ein kombiniertes Skript gehabt, welches noch höhere Kompressionsraten erreicht.

Also wer ein Skript geschrieben hat, welches den String wieder selbst in einen String komprimiert, der mag ihn bitte bitte mit uns teilen - auch wenn er nicht an die anderen Ergebnisse ranreicht.

Diese werden primär durch entsprechende Zeichenkodierung erreicht und eben nicht durch Veränderungen des Strings selbst - daher können uns solche Lösungen weiterhelfen.

Zum Thema: "Performance-Krone": Ganz ganz ehrlich: ich hab nicht im Mindesten auf Performance hin optimiert. Mir fallen auf Anhieb 4 Stellen ein, die man durch umcoden noch beschleunigen könnte. Klar über die Zeit hat man gelernt, was Performance frisst und was nicht und hat sein normales coden daraufhin angepasst.

Aber direkt auf Performance ist das Ding überhaupt nicht optimiert.

Ebenso gibt es so gut wie kein Error-Handling, keine hinreichende Codedokumentation/kommentierung und getestet wurde ausschließlich mit diesem String.

Bugs bei anderen Inputs halte ich für hinreichend wahrscheinlich.

So - nun schaue ich mir aber mal genauer an was die anderen so fabriziert haben.

Danke nochmal Oscar - hat wirklich Spaß gemacht!

Edit: Oscar : Genau genommen ist die Kompressionsrate von Mars noch besser. Bei Ahnungslos und mir wird die Anzahl an Bytes des Eingangsstrings als Vergleichsgröße genommen (6105). Bei Mars hingegen ist es die Stringlänge (6033). Die Kompressionsrate bei ihm sollte also zum Vergleich eher 50,762 % betragen.

Glückwunsch an Mars für die beste Komprimierung

AspirinJunkie für die auch sehr gute und sehr schnelle Komprimierung

Hier mal das Resultat mit externen Tools / DLLs:

Andy war wahrscheinlich verhindert, vielleicht kommt von ihm später noch etwas

Mein Skript funktioniert wie folgt (falls der Spaghetticode keinen Sinn ergibt, hier die Zusammenfassung):
- 1. Erzeuge ein Histogramm des gesamten Strings (256 Slots)
- 2. Komprimiere das Histogramm bestmöglich
    - 1. Speichere MinIndex und MaxIndex (z.B. 20 und 150) jeweils als 8 Bit, betrachte ab jetzt nur noch den relevanten Teil.
    - 2. Quantisiere auf 2 Bit (0 = Zeichen Existiert, 1 = Kleiner Wert, 2, Mittlerer Wert, 3 = Großer Wert, Empirisch bestimmt)
    - 3. Speichere das Histogramm Layerweise:
    ; | MinIndex                                                                                                       MaxIndex |
    ; 100100000000000000000011100100110011111111111111110000011111111111111111111111101101000111111111111111111111111110000000001
    ; 1  1                  100  0  00  1010100000000000     000000000000000000000000 00 0   11111111101111100111111001         0
    ; 0  0                  1           0 0 0                                                100110011 01010  111100  0
    ;                       1                                                                0  01  01  0 1   1000
    - In Layer 0 steht also immer eine 1 für: "Zeichen existiert"
    - In Layer 1 steht eine 1 für alle Zeichen die einen kleinen Wert haben
    - usw. Im Endeffekt kann man so eine 2Bit Kodierung benutzen, und insgesamt nur wenige Bits dafür verbrauchen.
        Das sieht beim Beispiel hier ggf. nutzlos aus (zu dicht), wenn man aber 100 aufeinanderfolgende Nullen betrachtet ergibt das Sinn.
    - 4. Benutze eine Lauflängenkodierung. Aus dem 01-String werden jetzt RLE-Tokens (also sowas wie 0 0 1 5 100 4 1)
    - Die Wahrscheinlichkeiten (nicht normiert) der Tokens entsprechen in etwa p(Index) = 14.7/((x+0.344)^0.94), empirisch bestimmt.
    - 5. Benutze einen Huffmantree (aus den oben gegebenen Wahrscheinlichkeiten) um die RLE-Tokens zu encodieren.
    - 6. Setze die Anzahl Tokens binär kodiert an den Anfang (das braucht der Decoder später)
    - Jetzt hat man eine (grobe) Wahrscheinlichkeitstabelle mit ca. 100 Einträgen in 200 Bit.
    - Im Nachhinein betrachtet hätte man vermutlich direkt eine RLE nutzen können und wäre damit besser bedient...
- 3. Erzeuge basierend auf dem (groben) Historgramm einen HuffmanTree
- 4. Für jedes Symbol:
    - 1. Hole eine Prediction über das nächste Symbol ein (Top15 Liste in meinem Fall wo auch die Konfidenz angegeben wird)
        - z.B. "C": 15, "A": 5, " ": 2 (das würde sagen: "C" ist am Wahrscheinlichsten, dann kommt A und dann das Leerzeichen)
    - 2. Booste das Histogramm (temporär) mit den Werten aus dem Predictor.
    - 3. Baue einen Huffmantree aus dem Histogramm
    - 4. Kodiere EIN Symbol
    - 5. Füge das kodierte Symbol zum Histogramm und zum Predictor hinzu (damit beide wissen was dekodiert wurde)
- 5. Return = Gesamte Stringlänge (braucht man für die Steuerung) & Komprimiertes Historgramm vom Anfang & Eigentliche Daten

Der Trick an der Sache war bei mir das Finetuning (was aber eigentlich auch Informationen über den zu Komprimierenden Inhalt braucht, also die eingestellten Parameter funktionieren gut für deutschen Text, aber vermutlich nicht so gut für andere Sachen).

z.B. Wie stark wird das Histogramm geboostet? (1 Parameter)

z.B. Wird der boost im Verlauf der Kodierung stärker oder schwäche (1 Parameter)

z.B. Wie arbeitet der Predictor intern? (2 Parameter (lässt sich zusammenfassen als Verhältnis))

z.B. Wie stark wird das Histogramm aktualisiert nachdem dein Zeichen dekodiert wurde? (1 Parameter)

Ich habe insgesamt 4 Magic Numbers die alle für gewisse Einstellungen verantwortlich sind. Die kann man auch so einstellen, dass der Text 5% schlechter Komprimiert wird und genaugenommen müsste ich diese Werte (die man quasi bruteforcen muss) mit in den kodierten String stecken was nochmal ca. 40 Bit braucht. Da ich aber ohnehin schon so knapp an den 50% war wollte ich das einfach nicht machen... Wenn man das berücksichtigt bin ich quasi gleichauf mit AspirinJunkie (nur noch ein paar Bytes besser), wobei sein Skript 50x schneller ist