Über die String-Dekompression

  • Somit wäre die Methode meiner Ersetzungskompression sehr ähnlich, aber wesentlich schneller.
    Jetzt noch Kombinationen mit 2, 3, n Bytes rein und die Kompression steigt nochmal an. Einpackzeit wird sich verhunderttausendfachen, Auspackzeit bleibt gleich.
    Bsp:
    Ersetzungen: 2, 2, 2, 2, 2, usw -> Komp (60%)
    Ersetzungen: 3, 2, 2, 2, 2, usw -> Komp (65%)
    ...
    Ersetzungen n, n, n, n, n, usw -> Komp (5%)
    Jetzt nach Effizienz sortieren und den Besten anwenden.

  • Hi,

    Zitat

    Jetzt noch Kombinationen mit 2, 3, n Bytes rein und die Kompression steigt nochmal an. Einpackzeit wird sich verhunderttausendfachen, Auspackzeit bleibt gleich.

    ja, das ganze habe ich aber schon hinter mir, bzw. verworfen aus einem einfachen Grund:
    Mehrfach, d.h. 3er, 4er, 5er usw. -Kombinationen aus unterschiedlichen Token (123abc345abc88abc) kommen idR SEHR selten vor.
    Die häufigste vorkommende 3er-Kombination kommt jedenfalls zwangsläufig seltener vor, als die am wenigsten festgestellte (und bereits komprimierte) 2er-Kombination (in abc ist nämlich schon ab enthalten) !
    Ich hatte dazu in einer Schleife 3er,4er und 5er Permutationen berechnet und deren Vorkommen im String gezählt (siehe Grund des asm-Scripts)
    Durch die etwas höhere Kompressionsrate und reichlich reservierte Token (die dann natürlich für die 2er wieder fehlen^^) kam ich zu einer Kompressionsrate von 49%. Die Laufzeit war allerdings mehrere Stunden, bis ich irgendwann abgebrochen hatte. UEZ komprimiert in seinem Script übrigens bei LZNT in der höchsten Stufe, und das ist kompressionstechnisch kein Stück besser als das AutoIt-Pendant!!!


    Sinn würde es ggf. machen, die Mehrfachkombis am Anfang zu testen und dann zu komprimieren. Allerdings ist man dann Laufzeittechnisch auch wieder angeschmiert, lediglich die Kompression würde sich verbessern, aber das tut sie ja ohnehin, wenn man die Laufzeit verlängert :P
    Also muss ein Algorithmus her 8o , der mit einfachen Funktionen arbeitet (AND/OR/XOR) oder den bereits komprimierten String nochmal völlig durcheinanderwürfelt (XOR würde sich da anbieten^^ )
    Wenn man mit einem wie auch immer produziertem zusätzlichen String XORed und nachher wieder einen sehr gut zu komprimierenden String erhält, dann könnte sich das lohnen.
    Mit Zufallsstrings XORen und nachher die Häufigkeit (s. asm-script) ermitteln, geht jedenfalls sauschnell 8o

  • Wer Lust hat, kann ja mal hier rein schauen (siehe Anhang) - ist vom 7-Zip Entwickler.


    Zitat


    UEZ komprimiert in seinem Script übrigens bei LZNT in der höchsten Stufe, und das ist kompressionstechnisch kein Stück besser als das AutoIt-Pendant!!!


    Ist eben "nur" Built-In.


    Gruß,
    UEZ

  • Eine "Zufällige" Kompression habe ich auch schonmal angetestet.
    Allerdings kam ich da nie zu einem fertigen Skript. Vorher hat das Tempo verhindert, dass man es wirklich an ein paar KB testen konnte.


    nochmal zum Ersetzen: Die 3 ist wahrscheinlich ungünstig, es kommt halt immer darauf an was man komprimiert.
    z.B. bei 24 Bit Bitmaps sind 6er sehr häufig, bei 32ern (gibt's häufiger) kann zu Beginn ein Paar Durchläufe mit 8ern machen um die Häufigen Farben schonmal kleinzubekommen.


    Bei Text wie z.B. diesem Beitrag" Kommen auch einige Wörter/Zeichenkombinationen mehrfach vor. Mit anfänglichen 16Byte Tests macht man idr nichts verkehrt. Im Späteren Kompressionsverlauf sind natürlich alle großen Kombinationen überflüssig. Nach dem 20ten Durchlauf wird man keinen einzigen 16er mehr finden.


    Optimal wäre glaube ich eine breite Fächerung zu Beginn (Maximalwert abhängig von einer anfänglichen Redundanzanalyse) die direkt stark abnimmt, bis man bei Runde X nur noch 2er benutzt.


    Edit: Wenn bei mir die Klausuren rum sind bastele ich mal ein schönes Skript. Dann schauen wir mal wie 7Zip aussieht :D

  • hehe....64bit....
    Ich wollte damals beim Deskstream einen Huffmann-Baum mit 64Bit bzw sogar 128Bit-Verweisen aufziehen. Das Problem ist aber bei JEDER Implementation das gleiche: Für wenig mehr an Kompression muss man einen gigantischen Aufwand betreiben. Und die gängigen Komprimierer haben ja alle mehrere Verfahren am Start. Und gerade beim Deskstream hat sich gezeigt, dass es eben nicht egal ist, ob man in 20ms oder in 500ms zum Ergebnis kommt! Bei den gängigen Verfahren ist das aber völlig egal! Da gibt es ganz andere Prioritäten! Würde man da nach schnellster Kompressionszeit wählen müssen, würden per se schon 90% der Verfahren aus der Auswahl rausfliegen!


    Im Deskstream-Thread gibts sogar von mir eine Anleitung, wie man die gängigen Komprimierer einbinden und testen kann...letztendlich hat´s nichts gebracht, sobald die Kompressionsrate verbessert wurde, ist die Zeit unverhältnismässig gestiegen, siehe diesen Thread^^.
    Ausserdem sollte das alles noch überschaubar bleiben. Wenn man erkennt, dass man die Codegrösse verhundertfachen muss um 5% besser zu komprimieren, dann lässt man als Hobbycoder die Finger davon^^


    In OpenCl/OpenGl sollte da noch etwas gehen, aber die gängigen Algorithmen sind nicht sehr gut bzw einfach zu parallelisieren. Für eine Framerate von 25FPS hat man dezente 40ms für den TRANSPORT der Daten (24MB bei 1024x1024x24bpp) übers Netz, und fürs Entpacken. Mal angenommen, 20ms gehen fürs Entpacken drauf, dann hat man 20ms übrig für den Transport der 24MB (die eingestampft auf ein Viertele bleiben 20ms für 6mb) was nach Adam Riese eine Leitung von 300Mb/s entspricht 2400Mbit NETTO. Macht erfahrungsgemäss Brutto locker das doppelte bzw das dreifache.... bei einem Viertel der Full-HD-Auflösung ^^
    Ergo kommt man sehr schnell auf den Trichter, dass es heutzutage garkeine Simultan-Übertragung geben kann (für den Otto-Normalverbraucher) und man doch lieber zu einem bis zum Anschlag komprimierten Video greift, dass (s. YT und Konsorten) mit einer bescheidenen Qualität erstmal minutenlang vorgepuffert werden muss. WzBw ;-)

  • Zitat

    Edit: Wenn bei mir die Klausuren rum sind bastele ich mal ein schönes Skript. Dann schauen wir mal wie 7Zip aussieht

    Yo, lass uns mal was machen, eine schöne Anwendung für OpenCl wäre noch der Knaller :thumbsup:


    Zitat

    Mit anfänglichen 16Byte Tests macht man idr nichts verkehrt.

    doch^^, ich hatte anfangs auch nach bis zu 30 Byte langen Ketten gesucht. Da ist die Kompressionsrate natürlich gigantisch, aber die kommen definitiv viel zu selten vor....sucht man ab maximal 6-Byte Ketten, verringert sich die Kompressionszeit um die Hälfte! Bei gerade mal ca. 1-2% schlechterer Kompressionsrate! Praktisches Bsp s. oben
    Bei Bildern sieht das anders aus, im Deskstream habe ich imho 1024 gleiche Pixel durch 5 Byte ersetzt....

  • Das Erste, was ich bemerkt habe: StringRegExpReplace() ist ca. 6x schneller als StringReplace()


    Hier hab ich jetzt aufgehört, weiterzulesen. Verzeiht also, wenn das dann doch schon gepostet wurde.


    Schalte mal bei StringReplace das Case-Sensitivity-Flag auf 1! Dann siehst du mal, wieviel schneller StringRegExpReplace dann noch sein sollte

  • SEuBo,
    RegEx ist bei weitem schon aus dem Rennen, da hättest du schneller sein müssen bzw. weiterlesen sollen ;-)
    Aber vielleicht hast du trotzdem eine Antwort auf mein RegEx-Problem im Post 17?
    Ich gehe davon aus, dass mein Code wesentlich schneller ist, aber für kurze Strings bzw. andere ähnliche Anfragen wäre ein RegEx schnell getippert. Ausserdem muss man ja nicht dumm sterben, ich lerne trotz meines hohen Alters gerne immer noch dazu :D

  • :D , das ist nicht neues...Problem ist (wie üblich bei den gängigen Kompressionen), die ZEIT.
    Kein Mensch (der eine SCHNELLE Kompression/Dekompression) braucht, wandelt Binärdaten in eine Bitmap (ok, DAS ist das einzig schnelle, die 54 Byte Header davorzusetzen^^) , um diese Bitmap dann in eine JPG/JPEG/PNG oder wasauchimmer umzuwandeln bzw zu komprimieren. Wieso dann nicht direkt ein Verfahren (Deflate) nehmen, dass für die Kompression dieser Daten geeignet ist?
    Da Deflate bei allen gängigen Kompressionsverfahren bzw. Zippern Verwendung findet, braucht man sich nicht zu wundern, dass auch die Ergebnisse ähnlich sind.
    Im Endeffekt läuft dann doch wieder alles auf die Huffmann-Kodierung raus :thumbsup: , jaja Räder neu erfinden wird auch immer schwerer...

  • Ich finde die Idee einfach cool, wobei die Idee vielleicht nicht neu ist, aber die Implementierung ist sehr ansehnlich.


    Die Idee ist einfach, dass man nicht den "lahmen" AutoIt Interpreter nimmt, sondern Built-In Funktionen.


    Oben von mir das Beispiel mit der ntdll.dll und von trancexx die gdiplus.dll als Alternativen.


    Natürlich ist der Königsweg zum Komprimieren der von die genannte Weg, aber manchmal sind die alternativ Wege einfach nur genial...


    Gruß,
    UEZ

  • Zitat

    Natürlich ist der Königsweg zum Komprimieren der von die genannte Weg, aber manchmal sind die alternativ Wege einfach nur genial...

    Ja, du hast natürlich völlig Recht!
    Wenn es schon eine "native" AutoIt-Funktion gibt, die etwas ähnliches macht, dann sollte man die auch benutzen!
    Aber wo bleibt denn da der Spass 8o ?
    Letztendlich gibt es alles schon irgendwo, man muss nur noch die Funktion runterladen und aufrufen, aber der Reiz am Programmieren ist doch (jedenfalls bei mir) auch mal eigene Gedanken einfließen zu lassen und eine Lösung weit abseits vom C&P zu erarbeiten.

    Zitat

    Die Idee ist einfach, dass man nicht den "lahmen" AutoIt Interpreter nimmt, sondern Built-In Funktionen.

    hehe, ;) , es lebe die WIN API :thumbsup:

  • Ich bin völlig bei dir, wenn es darum geht, den Reiz am Coden zu erhalten! Aber in diesem Fall fand ich die Idee GDI+ zum Komprimieren zu benutzen, einfach genial. Erst mal auf diese Idee zu kommen, denn mir war die Idee noch "fremd".


    Ich würde diese Art (GDI+) zum komprimieren nicht benutzen, doch die Möglichkeit zu haben ist einfach faszinierend.


    Gruß,
    UEZ

  • Hi


    Da meine ersten Tests vielversprechend aussahen, hab ich auch eine Funktion geschieben, um Binäre Daten als String zu komprimieren.
    Das Endergebnis ist dann doch nicht ganz so rosig, wie ich am anfang dachte ^^


    AutoIt3.exe kann ich auf gut 48 % zusammenschrumpfen.
    Das ist nicht wirklich viel mehr Kompression, als etwa Andys AutoItOnly Version.


    Bei Daten, wo viele gleiche Wiederholungen auftreten (etwa Bitmaps mit großen einfärbigen Flächen), steigt die Kompressionsrate aber enorm.
    Das Array 10000 mal 0xFF112233 schrumpft so auf 0.04%
    Zugegeben, solche Daten kommen eher selten vor :D


    Und Bitmaps mit großen einfäbigen Flächen sollte man dann doch zuerst als Jpg speichern und dann erst komprimieren...


    Nun ja, vielleicht findet ja trotzdem jemand Verwendung dafür...



    E

  • Hi,


    um einen schnellen Blick auf den Code zu werfen, einfach diesen Online-Disassembler benutzen (das führende 0x nicht mit kopieren^^)
    https://www.onlinedisassembler.com/odaweb/

  • Hab nur das hier gefunden, weiß jetzt auf die schnelle nicht, ob das auch der richtige Code ist... (schon lange her)