Algorithmen Teil IV (Software-Spielereien)

  • Abt. "Reif für die Klapse"
    -----------------------

    Problem: Wie findet man in einem Text mit lauter Querverweisen, die weitere Querverweise enthalten (, die weitere Querverweise enthalten...), eine bestimmte Zeichenkette, um darauf einen Querverweis zu machen? Ich würde sagen, ich dekodiere das ganze in einen Ringpuffer und sichere mir die "Rücksprungadressen" von den (längenbegrenzten!) Querverweisen in einen Stack. Außerdem muss ich mir die Adressen der Zeichen im Ringpuffer merken, damit ich später weiß, wo ich denn jetzt meine Zeichenkette gefunden habe. Der versierte Informatiker erkennt sicher schon: das wird ein Komprimierungsalgorithmus. Und ich bin bald reif für die Klapse. Leider kann ich nicht einfach den Huffman-Algo drüberlaufen lassen, da ich das in einem Mikrocontroller mit nur 2 kB RAM dekomprimieren muss und auch noch in den Daten rumspringen können muss. Deshalb auch die Verweise auf die bereits komprimierten Daten...

    So, ich hole jetzt erstmal Papier und Bleifisch und denke mir eine "Querverweisverfolgung" aus. Ich will ja nicht beim Debugging völlig wahnsinnig werden.


    Gruß
    Jonathan


    P.S.: Ach ja, den Code kann ich dann ja mal hier posten - sofern das was wird.

    P.P.S.: Und das ganze muss ich danach noch mit relativen Adressen machen, damit diese nicht so viel Platz brauchen.

    • Anzeige

    Hallo!

    Wenn du gerade an deiner Website arbeitest oder dein aktuelles Hosting überdenkst: Wir betreiben mit NetzLiving eine Hosting-Plattform, die speziell auf Performance, Sicherheit und einfache Verwaltung ausgelegt ist.

    • ✔️ Schnelle Ladezeiten (optimiert für WordPress, WoltLab & Co.)
    • ✔️ Deutsche Server & DSGVO-konform
    • ✔️ Persönlicher Support (kein 0815-Ticket-System)

    Mehr erfahren

  • Die Querverweise sind im bereits komprimierten Text (ja, ich will Text komprimieren) und verweisen auf andere Stellen im komprimierten Text, die dann auch noch weitere Querverweise enthalten können (und natürlich reinen Text). Byte-Recycling auf Fußpilz-Ebene... Ich kann leider nicht auf den unkomprimierten Text verweisen, weil der kleine Mikrocontroller mit seinen 2kB RAM das dafür ja erst komplett entpacken müsste - und das passt einfach nicht da rein. Deshalb muss ich auch in den komprimierten Daten rumspringen können und somit fällt Huffman flach.


    Gruß
    Jonathan

    P.S.: Danke, das Glück kann ich gut gebrauchen! :D ^^

  • Die Querverweise sind übrigens von der Art "lese da ein paar Bytes und dann dort ein paar Bytes". Also auch noch längenbegrenzt. Und diese längenbegrenzten Querverweise können auch noch weitere Querverweise enthalten. Halleluja! Die Version ohne "querverwiesene Querverweise" (also mit einfachem "@InStr()") schafft bereits Komprimierungsraten von ca. 30%.

  • Hm, scheint wohl zu funktionieren, braucht aber selbst für 1kB bereits mehrere Minuten:



    Suboptimal!


    Gruß
    Jonathan

  • Heißt das, du baust parallel zur Kompression so eine Art "Rainbow-Tables" der komprimierten Textteile auf?

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Nein, ich dekomprimiere einfach bei jedem Suchlauf nach bereits komprimierten gleichen Textteilen den gesamten bereits komprimierten Text. Schnarchlahm. Und außerdem hat sich da ein Fehler eingeschlichen. Aber ich werde den Fehler jetzt nicht suchen, mir ist da nämlich eine viel bessere Idee gekommen:

    Ich gebe jedem Byte des zu komprimierenden Textes eine Adresse, wo es im komprimierten Text vorkommt. Am Anfang steht da 1-2-3-4-5... Dann durchsuche ich den unkomprimierten Text nach dem zu komprimierenden Textstück und schaue, ob es vor dem zu komprimierenden Textstück bereits vorkommt. Wenn ja, dann nehme ich von dort die Adresse, wo es im komprimierten Text bereits vorkommt (ich habe ja jedem Byte eine Adresse zugeordnet), und verringere die Adressen aller noch zu komprimierenden Bytes um die Anzahl der rausgenommenen Bytes. Wenn nicht, dann kopiere ich die Bytes einfach an die Adresse, die ihnen zugeordnet ist. Klingt kompliziert, ist es auch. Ich bin dann mal am Tastatur-Quälen...


    Gruß
    Jonathan

  • Wir harren deiner Ergebnisse...


    Abt. Single&Double-Precision FloatingPoint Parallelverarbeitung nutzen
    ---------------------------------------------------------------------
    Wer inzwischen mit mm0 bis mm7 sowie xmm0-xmm7 umgehen lernen will, ist mit diesem Artikel hier recht gut bedient (Englisch).
    Gruss

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Hm, fast fertig. Nur der Dekomprimierungsalgo hat noch Bugs...

    Komprimieren kann man aber schon mal:



    Ändert aber nichts daran, dass das Teil schnarchlahm ist.


    Gruß
    Jonathan

  • 1. Geht´s da nur um Zahlen (Ich frage wegen "ZeichenKetteZuZahl")?
    2. Kann mans auch wieder de-fump2-en?

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Ok, funktioniert (für Quellcode besonders gut geeignet - viele Wiederholungen) :)

    Komprimieren:



    Dekomprimieren:



    So, und jetzt noch einen Huffman-Nachbrenner! :D


    Gruß
    Jonathan

  • Bin am testen...

    Abt. Multimediabefehle und Große Integerzahlen
    ------------------------------------------------------
    Nach längerer Zeit habe ich dieses gute Link zum Thema xmm-Befehle wiedergefunden.
    Grusz ;)

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Der hier kann sogar noch besser komprimieren :D

    Komprimieren:



    Dekomprimieren:




    Ganz brauchbar :-)... Allerdings nur für Texte, und außerdem dürfen in den zu komprimierenden Dateien keine Bytes mit dem Wert 0/1/2/3 vorkommen.


    Gruß
    Jonathan

  • Abt. 16-Byte-ALIGNMENT in XProfan gelöst
    ===========================
    Die SSE4.1 Multimediabefehle von XPIA's Assembler werden erst richtig schnell, wenn die entsprechenden Profan-Arrays an Speicherstellen beginnen die hexadezimal auf 0 enden. Man nennt das '16-Byte Alignment' (Ausrichtung).

    Meine sämtlichen Versuche haben bisher ergeben, daß im 11.2a-Interpreter das erste declarierte Element a![0,0] stets an einer Speicherstelle beginnt, die hexadezimal auf 8 endet, im Compiler dagegen auf 0 oder 8. Im Compilermodus haben vorher declarierte Elemente anderen Typs Einfluß auf die Speicherstelle des Arrays, im Interpreter nicht. Abhilfe soll nachstehendes Programm bieten, das auf der Annahme basiert, daß durch die Größe eines unmittelbar vorher declarierten 'Alignment-Arrays' gleichen Typs Einfluß auf die Speicherstelle des darauf folgenden genommen werden kann. Dummerweise verhält sich das erste dieser Elemente im Compilermodus paradox (genau verkehrt), was durch 'bedingte Declaration einer einfachen Floatvariable, nur im Compilermodus' aber kompensiert werden kann.

    P.S.: Schon klar, daß es beim Thema Alignment nur um den Compiler geht - mir gings aber ums Prinzip. Bitte um Eure Erfahrungsberichte, vor allem in anderen Versionen und Windows-Geschmacksrichtungen!!

    PPS: Prüfe gerade, ob im Compiler Bereichsvariable in Primzahlengröße das nachstehende Alignmentprogramm durcheinanderbringen können...(EDIT: Nö, scheint also OK zu sein)

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • UPDATE zum vorigen Beitrag ALIGNMENT, jetzt mit höherer Sicherheit
    ============================================

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Sooo... Jetzt da die Schule wieder angefangen hat, hab ich leider nicht mehr so viel Zeit zum proggen. Das hält mich aber trotzdem nicht davon ab, meinen Komprimierungs-Algo weiter zu verbessern :D

    Komprimieren:



    Dekomprimieren:




    Demnächst kommt noch ein Huffman-Nachbrenner (wie weiter oben schon angedroht). Jetzt muss ich aber erst mal meine mobile Stereoanlage (oder eher "Monoanlage" :D) fertigbauen... *Grins*


    Gruß
    Jonathan

  • Jonathan: Gratulation! Tolles Teil, überhaupt für einen Eigenbau!

    Ich für meinen Teil kämpfe mit Win7-64 am Laptop (CPU: P 6000, 2 Cores) um Berechtigungen, die unter XP längst gelöst waren. Nachstehend ein Beispiel für vereinzelte unerklärliche Abstürze ohne jegliche Rückmeldung (Bitte Vorsicht!):

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!