[Wettbewerb] String komprimieren

  • Die Aufgabe besteht darin einen uebergebenen String so effektiv wie möglich (aber verlustfrei) zu komprimieren (keine externen Librarys, nur AutoIt-Code erlaubt).

    Dazu müsst ihr zwei Funktionen programmieren _StringCompress und _StringDecompress.

    Nachtrag 23.02.2022: Der Variablentyp fuer den komprimierten Text muss natürlich kein String sein. Dort könnt ihr euch ein eigenes Format ausdenken. Hauptsache am Ende von _StringDecompress kommt wieder der ursprüngliche String raus. Ich hab's im Beispiel mal angepasst.

    Nachtrag 24.02.2022: Um ein besseres Ergebnis beim komprimieren zu bekommen, habe ich den zu komprimierenden Text etwas erweitert. Die Länge beträgt nun 6033 Bytes und befindet sich in der Datei "original.txt" im ZIP-Archiv.

    Die Scripte als PN an mich.

    Einsendeschluss: 31. März 2022, 23:59:59 Uhr

    Gewonnen hat derjenige, der die beste Compress-Ratio erreicht.

    Ergebnis:

    Es hat drei Einsendungen gegeben und, soviel schonmal vorweg, alle drei haben mich sehr beeindruckt.

    Die Aufgabe bestand darin, die beste Kompressionsrate zu erreichen, ohne Rücksicht auf die Zeit (solange sie im "Rahmen" bleibt).

    Von daher erkläre ich Mars zum Sieger, weil er mit 50.174% tatsächlich die 50er Hürde übertroffen hat. Gratulation! :klatschen:

    AspirinJunkie mit 49.255% liegt nur knapp dahinter, hat aber ein Script abgeliefert, was ihm klar die Perfomance-Krone verleiht.

    Ahnungslos folgt dann mit 47.404% auf den dritten Platz.

    Die Ergebnisse im einzelnen:

    Spoiler anzeigen

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

    Result for "Mars"

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

    Decompressed = Original:True

    Length Original: 6033

    Length compressed: 3006

    Length decompressed: 6033

    Compress-Ratio: 50.174 %

    Time compressed: 57940 ms

    Time decompressed: 54119 ms

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

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

    Result for "AspirinJunkie"

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

    Decompressed = Original:True

    Length Original: 6105

    Length compressed: 3098

    Length decompressed: 6033

    Compress-Ratio: 49.255 %

    Time compressed: 1314 ms

    Time decompressed: 189 ms

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

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

    Result for "Ahnungslos"

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

    Decompressed = Original:True

    Length Original: 6105

    Length compressed: 3211

    Length decompressed: 6033

    Compress-Ratio: 47.404 %

    Time compressed: 5647 ms

    Time decompressed: 294 ms

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

    Das alle drei im Ergebnis nicht mal 3% auseinanderliegen, hätte ich so nicht erwartet. Zeigt aber, dass die Algorithmen wohl ziemlich ausgereizt sind.

    Ich habe mich vor dem Wettbewerb nie damit beschäftigt, wusste also nicht viel darüber. Unsere drei Kandidaten dagegen haben ein gutes Fachwissen

    bewiesen und es macht Spass, sich die Scripte mal genauer anzusehen (ich habe sie gepackt als "Scripte.zip" in den Anhang gelegt).


    Das AutoIt-Gerüst habe ich mal vorbereitet (auch als Anhang):

  • keine externen Library

    Hi Oscar,

    nette Idee.

    Eine Frage, was sind externe Libraries - sprich zählen dazu auch Windows Libs, wie z.B. GDI+, User32, etc.?

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

  • Ergänzung zum Template: Ggf prüfen, ob der String nachher wirklich identisch mit dem Input ist.

    Frage zu den Bedingungen:

    - Man kann davon ausgehen, dass "nicht nur der Text aus der Aufgabenstellung" bei der Bewertung ausprobiert wird oder? Welche "Art" von Text wird verwendet werden? (z.B. Base64String, Der Dateiinhalt einer Win32.exe, ein Foto, oder die lateinische Wikipedia?)

    - Kann man davon ausgehen, dass "zu langsame" Algorithmen nicht teilnehmen können? Ich habe vor langer Zeit mal etwas gebastelt (ein adaptiver Huffman Codierer mit coolem Tree der sich dynamisch anpasst), der läuft aber mit ca. 1 BYTE pro Sekunde^^ Also vermute ich, dass der Algorithmus in nativem AutoIt (ohne Dllcalls) mit sagen wir mal: 128+Byte/s klarkommen muss (habe ich jetzt willkürlich geraten), sonst kann er nicht teilnehmen.

    - Mit welcher Inputgröße muss man rechnen? Wenn ich z.B. weiß, dass es nur Strings kleiner als 200 Zeichen werden (Beispiel!), dann wird es kritisch soetwas wie eine Initialisierung am Anfang der komprimierten Daten zu haben (z.B. eine Wahrscheinlichkeitstabelle die mit dem zu komprimierenden String berechnet wurde. Die nimmt vorne schon ein bisschen Platz weg (selbst wenn es nur 2Bit/Eintrag sind) und bei "nur" 200 Zeichen lohnt sich das uust nicht. Bei 1000 aber z.B. schon).

    M

  • sprich zählen dazu auch Windows Libs, wie z.B. GDI+, User32, etc.?

    Alle Libs, die eine Komprimierung vornehmen.

    Es sollte schon reiner AutoIt-Code sein. Um schnellere Textsuchen zu ermöglichen würde ich das ScriptingDictionary-Objekt zulassen.

    Ggf prüfen, ob der String nachher wirklich identisch mit dem Input ist.

    Das geschieht bereits bei der Auswertung.

    Man kann davon ausgehen, dass "nicht nur der Text aus der Aufgabenstellung" bei der Bewertung ausprobiert wird oder?

    Zur Bewertung wird der Text aus der Aufgabenstellung benutzt. Die Funktionen sollten aber mit jeder Textdatei funktionieren. Also ASCII, keine Binaries.

    Kann man davon ausgehen, dass "zu langsame" Algorithmen nicht teilnehmen können?

    Sagen wir mal, dass _StringCompress für die 1274 Bytes unter eine Minute brauchen sollte.

  • Blöde Frage anbei: Ist das fehlende Leerzeichen bei "\nAt" Absicht oder ein Fehler im Text?^^

    Und: Global $iTimer = TimerInit() wurde 2mal eingesetzt :)

    2 Mal editiert, zuletzt von Moombas (23. Februar 2022 um 08:49)

  • Eine letzte Frage noch:

    In welcher Basis soll der komprimierte String sein? Wenn man nur die Länge vergleicht wäre ja die Kodierung (z.B. B216 oder B64, etc.) sehr ausschlaggebend trotz gleichem Inhalt.

    Ich würde bei sowas volle Bytes zählen (wobei es egal ist in welcher Form diese Vorliegen... Als HexString, ArrayOfBytes, etc. etc).

  • Ich habe mich jetzt mal selbst an der Aufgabe versucht. Dabei ist mir aufgefallen, dass man mit zu kurzen Texten Probleme bei der Effektivität bekommt.

    Deswegen habe ich jetzt mal einen längeren Text erstellt, der dann auch als Datei vorliegt (neue Version in Post #1).

    Mein bisheriges Ergebnis (außer Konkurrenz):

    Das ist zwar recht schnell, aber die Compress-Ratio noch verbesserungswürdig. ;)

  • Bei mir ist es das genaue Gegenteil: Kompression ist "okay" (winrar macht daraus 2700 Bytes... also geht hier noch was), Geschwindigkeit mmmmh :D

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

    Result for "Mars"

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

    Decompressed = Original: True

    Length Original: 6033

    Length compressed: 3949

    Length decompressed: 6033

    Compress-Ratio: 34.543 %

    Time compressed: 10277 ms

    Time decompressed: 9389 ms

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

  • Eigentlich wollte ich selbst ja gar nicht teilnehmen, aber ich musste feststellen, dass man einiges dabei lernt.

    Mein neuester Versuch ergibt dieses Resultat:

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

    Result for "Oscar"

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

    Decompressed = Original: True

    Length Original: 6033

    Length compressed: 5097

    Length decompressed: 6033

    Compress-Ratio: 15.515 %

    Time compressed: 43 ms

    Time decompressed: 3 ms

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

    Erstaunlich schnell! Hätte ich von AutoIt so jetzt nicht erwartet.

    Ok, das sind momentan "nur" Wörterbuch-Ersetzungen, aber trotzdem recht schnell.

  • Schönes Thema. Das muss ich mir irgendwie markieren !

    Lieben Gruß,
    Alina

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Geheime Information: ;)
    OuBVU5ebLhHu5QvlnAyQB4A7SzBrvWulwL7RLl2BdH5tI6sIYspeMKeXMSXl

  • Von WinRAR noch Welten entfernt, aber ansonsten gefallen mir die Werte schon ganz gut:

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

    Result for "Ahnungslos"

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

    Decompressed = Original: True

    Length Original: 6033

    Length compressed: 3616

    Length decompressed: 6033

    Compress-Ratio: 40.063 %

    Time compressed: 189 ms

    Time decompressed: 265 ms

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