Huffman-Kodierung + Helferfunktionen für Umgang mit binären Daten

  • Mit dieser UDF kann man einen String per Huffman-Kodierung kodieren bzw. komprimieren.
    Die Huffmantabelle wird hierbei ebenso Bestandtteil des kodierten Binaries, weswegen die kanonische Form der Huffmantabelle verwendet wird um den Overhead hierfür möglichst klein zu halten.

    Die UDF macht regen Gebrauch der integrierten UDF "BinaryHelpers.au3", welche Funktionen zum leichteren Umgang mit binären Daten in AutoIt enthält.
    Diese wurde bislang noch nicht gesondert von mir veröffentlicht und könnte für manchen auch alleine interessant sein.

    Wie verwendet man die UDF?

    folgendes Beispiel:

    erbringt folgende Ergebnisse:

    Code
    Original Size: 157081 Bytes
    Encoded Size:  102833 Bytes
    Compress ratio: 34.5 %
    $sString == $sStringDecoded: True

    Wie kann man die Komprimierungsrate noch weiter steigern?

    Die Huffmankodierung ist nur ein von mehreren möglichen Beispiel zur Komprimierung von Daten und kann mit diesen auch kombiniert werden.
    Wenn man z.B. den String erst auf Textebene vorkomprimiert (z.B. durch Wortwiederholungskomprimierung) und erst anschließend die Huffmankodierung darüber gießt, kann man sich seinen eigenen kleinen Komprimierer komplett in AutoIt schreiben.

    Das obere Beispiel habe ich mal um eine solche (simple!) Vorkomprimierung ergänzt:

    und hiermit erhalten wir nun folgende Ergebnisse:

    Code
    Original Size: 157081 Bytes
    Encoded Size:  73333 Bytes
    Compress ratio: 53.3 %
    $sString == $sStringDecoded: True

    >>Download und Quellcode auf GitHub<<

  • Du wusstest doch, dass ich hier jetzt irgendetwas poste :P

    Weil ich ja eine lustige Kompressionsmethode für Permutationen gebaut habe dachte ich: Das kann man doch bestimmt für deinen komprimierten Huffmantree verwenden (genauer: Für die Charliste), und siehe da: Nach mindestens 3-4 Stunden herumgebastel habe ich 15 Bytes rausgeholt (was bei der Dateigröße richtig sinnvoll ist... 73334 ->73319 Bytes, und ich bin stolz drauf :rofl: )

    Vermutlich gibt es einige deutlich einfachere und weniger Rechenaufwendige Methoden die vermutlich auch mehr als 15 Byte Gewinn abwerfen, aber wie heißt es so schön: Der Weg ist das Ziel.

    Ein Disclaimer direkt zu Beginn: Ich bin nicht sicher ob die Methode "immer" so performed. Ich bin nichtmal sicher ob sie "immer" korrekt decodiert. Habe nur ein wenig herumprobiert und es sah "okay" aus. 80% von der Datei im Anhang sind C&P, eigentlich habe ich nur etwas ganz kleines geändert (das CharArray), aber irgendwie musste ich dafür 500 Zeilen Code kopieren weil da so viel dranhängt :S


    Die Methode ist ganz einfach:
    Das CharArray besteht ja aus "irgendwelchen Chars an irgendwelchen Positionen in einem Array". Dabei ist kein Char doppelt.
    -> Man kann eine Permutation finden, sodass die Chars alle sortiert sind.
    -> Die Charliste besteht also aus [Permutation] + [SortierteCharliste], beides lässt sich ziemlich gut (dicht am Entropielimit) komprimieren.
    -> Die Permutation hat schöne Eigenschaften (z.B. nichts doppelt, in sortierter Form sind es die Zahlen 0 bis n-1, also ist im sortierten Zustand der Abstand zweier Werte immer 1, und so weiter), die sortierte Charliste hat quasi überall den Abstand 1 (den man via "Huffman im Huffman" entropiekodieren kann).

    lg

    M

  • Du wusstest doch, dass ich hier jetzt irgendetwas poste :P

    Hehe - du warst der eigentliche Grund warum ich meinen Huffman-Ansatz von damals nochmal hübsch in UDF-Form restauriert habe.
    Sonst wird sich kaum einer hierfür interessieren.

    -> Man kann eine Permutation finden, sodass die Chars alle sortiert sind.
    -> Die Charliste besteht also aus [Permutation] + [SortierteCharliste], beides lässt sich ziemlich gut (dicht am Entropielimit) komprimieren.
    -> Die Permutation hat schöne Eigenschaften (z.B. nichts doppelt, in sortierter Form sind es die Zahlen 0 bis n-1, also ist im sortierten Zustand der Abstand zweier Werte immer 1, und so weiter), die sortierte Charliste hat quasi überall den Abstand 1 (den man via "Huffman im Huffman" entropiekodieren kann).

    Ich habe noch (viele) Verständnisprobleme hierbei.
    Vielleicht mal mein bisheriges Verständnis + Fragen hierzu:

    • Bei der kanonischen Huffman-Kodierung hat man die Codes schön kompakt gespeichert.
      Die zugehörigen Zeichen sind aber weiter so wie sie sind einfach nur hintereinander geschrieben - ein String.
    • Diesen String kannst du nun ebenso weiter komprimieren?
    • Hierfür werden die Zeichen in eine andere Reihenfolge (Permutation) gebracht.
      Wie komme ich aber auf diese genaue Permutation oder gehen auch andere?
    • Nach was ist diese sortiert? So wie ich das erst einmal sehe, enthält die Permutation die Indizes der ursprünglichen Elemente in einer sortierten Menge - oder?
    • Wie diese dann zusammen komprimiert werden - da steck ich noch nicht drin.

    Kann man diesen Ansatz irgendwo nachlesen?
    Hat er einen Namen?

    Ansonsten bin ich mehr als schwer beeindruckt, dass du in dieser ganz kurzen Zeit meinen Code nicht nur offensichtlich verstanden hast, sondern ihn auch noch an den komplizierten Stellen signifikant erweitern/verbessern konntest.

  • Ob der Ansatz einen Namen hat weiß ich nicht, den habe ich mir spontan ausgedacht :D

    Warum ich überhaupt darauf gekommen bin (hätte vor einiger Zeit auch noch gesagt, dass man eine "zufällige" Zeichenkette nicht komprimieren kann) ist weil ich viel zu viel Zeit damit verbracht habe zu versuchen vollständig zufällige Permutationen zu komprimieren (was interessanterweise tatsächlich geht), sogar deutlich unter das intuitive Limit (z.B. hat eine Permutation der Länge 64 NICHT 6 Bit/Symbol Entropie, sondern nur ca. 4.6).

    Ein sehr einfaches Beispiel dazu klaue ich aus meinem eigenen Code:

    Man beginnt mit einer sortierten Liste (Entropie davon ist quasi null, die einzige Information ist die "Länge der Liste").
    Dann hat man einen laufenden Index ($i) der in jedem Schritt um eins erhöht wird.
    Nun sucht man die Zahl mit der man einen Swap durchführen muss, um Position $i in der Permutation zu restaurieren.

    Anschließend erhöht man $i um eins und geht solange weiter, bis man aus der sortierten Liste die zu kodierende Permutation gemacht hat.

    Der Trick ist nun der folgende: Die Zahlen die man im Swap angeben muss (Swap($n) bedeutet Tausche [$i] mit [$n]) werden mit der Zeit logischerweise kleiner, da $i größer wird und die Liste ihre Länge beibehält. Im obigen Beispiel muss man also [8, 7, 2, 0, 2, 0, 1, 1, 0] + Länge der Liste kodieren um die Permutation [8, 0, 4, 3, 6, 5, 7, 1, 2, 9] zu rekonstruieren (ja die Liste ist ein Symbol kürzer, das liegt daran, dass nach n-1 swaps das letzte Element automatisch richtig liegt). Hier kann man jetzt mit Huffman ansetzen, da die zu kodierenden Symbole nicht nur immer kleiner werden, sondern auch eine bestimmte Wahrscheinlichkeitsverteilung (die von der "Sortiertheit" der Restliste abhängt) haben. (Ich habe den Teil der die "Sortiertheit" berücksichtigt aber nicht implementiert, sondern immer eine Gleichverteilung angenommen, im Fall des CharArrays (das "fast" zufällig ist) klappt das jedenfalls ganz gut^^).

    So schafft man es eine Permutation der Länge 64 (Beispiel) mit ca. 4.9 Bit/Symbol (Compress4 schafft ca. Entropielimit + 0.5Bit/Symbol im worst case) zu speichern anstatt (wie intuitiv angenommen) 6 Bit/Symbol aufzuwenden.

    Jetzt kommt Schritt 2: Wie wende ich das auf ein CharArray an?
    - Wo sind die Informationen im CharArray? -> In der Anordnung (Permutation), In den Absolutwerten (also "welche Zahl ist wo" auf gut Deutsch)
    - Die Anordnung kann man trivial finden, da wir wissen, dass jedes Symbol nur 1x vorkommt. Also einfach eine Kopie der Liste sortieren und in O(n²) alles durchgehen (If $aList[$i] = $aCopy[$j] Then $aPerm[$i] = $j)
    - Die Sortierte Liste ist z.B. 9, 10, 27, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, ... -> (Abstandskodierung) -> 9, 1, 17, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

    - Was wir speichern müssen ist $iMin, $iMax und die Länge (die Länge kann man auch weglassen, wenn man es schlau anstellt, habe ich aber nicht gemacht)

    - Außerdem müssen die Zahlen 9, 1, 17, 5, 1, 1, 1, ... in dieser Reihenfolge gespeichert werden. Huffman freut sich, denn die 1 ist quasi 80% von allen Zahlen.

    - Für die Wahrscheinlichkeiten habe ich das hier gewählt, nachdem ich mir ein paar Daten geplottet habe $aHist[$i] = 1 / ($i+1)^3. Die 1 ist extrem wahrscheinlich, alles andere eher weniger.

    -> 10011 000101011 11111100001 001111100 1 001100000 001010 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 nach der Entropiekodierung.

    -> ($iMin, $iMax, $iUbound-1, 9, 1, 17, 5, ... jeweils binär). -> Man kann das sortierte CharArray also recht kompakt speichern. Mit einem arithmetischen Encoder wäre hier noch einiges drin, weil die vielen Einsen beim Huffman jeweils 1 Bit ergeben was eigentlich nutzlos ist.

    Beides Zusammen ergibt dann 15 Byte Ersparnis beim Text der englischen AutoIt Seite, und ganze 26 Byte beim Text der deutschen Seite :D

    Habe aber noch eine andere Idee (wo Anordnung und Absolutwerte nicht erst getrennt und dann getrennt kodiert werden), wenn ich Zeit habe bastel ich die mal.

    lg

    M

  • Hi,

    Sonst wird sich kaum einer hierfür interessieren.

    DOCH! :party:

    Wie komme ich aber auf diese genaue Permutation oder gehen auch andere?

    Ich hatte einen ähnlichen Ansatz "damals" bei der Text-Kompressions-Challenge.

    Dort hatte ich einfach wahllos (nach einfachen Regeln, bspw. ROL oder Bits vertauschen) Permutationen von Bitsequenzen verwendet und mit der besten (gefundenen) wurde weiterkomprimiert. Ich hatte keine Regel gefunden, um zielgenau zu permutieren (nennt man das so?)

    Wenn es theoretisch (!) diese Regel GÄBE (!), d.h vor der Kodierung über eine Analyse feststehen würde wie die optimale (!) Permutation aussehen würde, dann....ja dann wäre wohl ein Nobelpreis fällig! :klatschen:

    Dass es funktioniert ist klar, die Frage ist nur, wie gießt man die Regel zur optimalen Permutation so klein in die Wertetabelle, dass diese letztendlich kleiner ist wie vorher, was ja der Zweck der ganzen Aktion ist! Letztendlich wird es darauf hinauslaufen, etliche "Bit-verschiebe/tausch/rollieren/ergänzen"-Verfahren wahllos durchzuprobieren bis ein für Huffman "besserer" String entsteht.

    Und dann die Abfolge der durchgeführten Vorschriften vor den zu dekodierenden Binärstring hängen....

    Betrachtet man den String nämlich binär und nicht als bspw. 8-Bit-Ascii-Zeichen, potenzieren sich die Möglichkeiten....

    Das Ziel soll ja sein, aus vorgegebenen Bitsequenzen durch bestimmte Verfahren besser zu kodierende Bitsequenzen "herzustellen".

    Simples Beispiel ganz ohne Permutation von Bitsequenzen:

    Nicht gut zu kodierender/komprimierender String -> gut zu kodierender/komprimierender String

  • Jop, das was Andy anspricht war auch mein eigentlicher Plan für die Kompression (aber in Bezug auf Permutationen). Allerdings habe ich den erstmal auf Eis gelegt, weil mir keine gute Methode eingefallen ist um zu entscheiden welche Operation man jetzt durchführt.

    Mein bisheriger Ansatz war (aufbauend auf der Swap methode)

    Mögliche Operationen:

    - Swap(n) -> Vertausche [i] und [n], an Position [i] ist jetzt das gewünschte Symbol aus [n], danach i+=1 (Swap Methode, in meinem Anhang heißt sie Compress3, Compress4 ist die Huffman Version davon)

    - Rot(n) -> Rotiere das Subarray von [i] bis [n], sodass das Symbol aus [n] bei [i] landet, danach i+=1
    - Mirror(n) -> Kehre das Subarray von [i] bis [n] um. Jetzt liegt das gewünschte Symbol aus [n] bei [i], danach i+=1
    - Nop -> Lasse alles so wie es ist (symbol bereits am richtigen Ort), danach i+=1

    Jetzt müsste man eine Analyse des Restarrays machen die für jede mögliche Operation bestimmt, welche Operation das Restarray im "besten Zustand" hinterlässt. Das ist ansich ein typisches Optimierungsproblem das man mit verschiedenen Ansätzen (näherungsweise, müsste NP sein) lösen kann, sobald man eine gute Fehlerfunktion (die angibt wie "gut" das Restarray ist) & Heuristik (die spekuliert wie gut ein potentieller Schritt ist und damit den Entropieencoder füttert, sodass der weiß: "mit 22.5% Wahrscheinlichkeit kommt Mirror(24)") gefunden hat.

    Meine Swap-Methode jetzt ist eigentlich ziemlich schlecht (die funktioniert hier nur durch Zufall). Angenommen man hat die Permutation [1, 2, 3, 4, 5, 0]. Dann bräuchte das trotzdem 5 Swaps. Eigentlich müsste man also Rotationen auf jeden Fall mit einbauen. Gleiches gilt für Mirrors, angenommen ich habe [5, 4, 3, 2, 1, 0], dann brauche ich wieder 5 Swaps. (Das sind jetzt nur Extrembeispiele).




    Edit: Und die Idee für das CharArray ist folgendes:
    - Zerlege in: "Welche Chars sind vorhanden", und "in welcher Reihenfolge".

    - "Welche Chars sind vorhanden" kann man via iMin, iLen (incl Nullen) und 1Bit/Char speichern. Problem: Es gibt Lücken, diese Lücken enthalten sämtliche Information.
    - "In welcher Reihenfolge" ist eine Permutation. Da weiß ich noch nicht ob es sinnvoll ist die überhaupt getrennt zu betrachten.

    Ansatz:

    - Finde den "Schwerpunkt" in der 1Bit/Char Liste (z.B. 10 Symbole, davon sind 0, 3, 4, 5, 6, 7, 9 vorhanden -> 1001111101, Schwerpunkt = Jeder Ort an dem links und rechts davon gleich viele nullen stehen.
    - Finde eine Menge Swaps, sodass die Liste Lückenlos wird. (am Beispiel hier: Swap(0, 2) und Swap(8, 9)) -> Die Liste ist jetzt 0011111110
    - Speichere nur noch iMin, iLen, (iSchwerpunkt müsste sich daraus berechnen lassen wenn er vorher korrekt gewählt wurde) + Swaps anstatt die Liste selbst, denn die Liste kann daraus rekonstruiert werden. (die "Welche Chars sind vorhanden" Information ist damit kompakt gespeichert). Aus "1001111101" wird "2, 7, swap(0,2), swap(8, 9)", wobei ich bei den Swaps noch überlegen muss ob die lieber relativ zu iMin, zum Schwerpunkt, oder zu irgendwas anderem am besten sind.
    - Für die Reihenfolge kann man wieder entweder eine Permutation komprimieren, oder die liste direkt manipulieren. Was davon besser ist.... wer weiß, muss man ausprobieren.

    Alernativ könnte man auch RLE auf die vorherige Methode (sortiertesCharArray in binärform nach dem Huffman) anwenden. Das gibt bestimmt auch nochmal ein paar bytes.


    M

  • weil mir keine gute Methode eingefallen ist um zu entscheiden welche Operation man jetzt durchführt.

    Hehe, dann halt dich mal fest! 8|

    Man muss ja nicht unbedingt WENIGER Bits haben! Wenn man den fertig komprimierten bzw. enkodierten String mit Bits erweitert und dann dadurch (wieder) einen gut zu komprimierenden/encodierbaren String erhält, dann ist das Ziel erreicht!

    Ob das mit Bitrotation, Bitweise Vertauschen, Bitwasauchimmergedöns oder, wie im Beispiel unten mit Erweiterung von Bits an der Position von Primzahlen erreicht wird, ist unerheblich!

    Die Aufgabe ist: Finde die Methode, um den bereits komprimierten String weiter komprimieren zu können!

  • Alternativ könnte man auch RLE auf die vorherige Methode (sortiertesCharArray in binärform nach dem Huffman) anwenden. Das gibt bestimmt auch nochmal ein paar bytes.

    Hier wird erklärt, wie man (ich vermute im best case maximal!) ca. 1% mit Hilfe der RLE aus dem Bitstream herausholen kann. Ohne am Verfahren etwas zu ändern!

    1% "fühlt" sich jetzt nicht viel an, aber bei 1MB an kodiertem/komprimiertem String sind das 10kbytes.

    Da musst du dich bei den

    ist... 73334 ->73319 Bytes, und ich bin stolz drauf :rofl:

    noch ein bisschen strecken 8o (immerhin 0,02%, aber was solls, wie du schon bemerkt hast: Der Weg ist das Ziel! :thumbup: )

  • Ha! Sehr gut!
    Ich wusste doch, dass es sich lohnt das Ding zu veröffentlichen.
    Ich hatte damit gerechnet, dass effiziente Methoden zum effektiven preprocessing des Strings gepostet werden.
    Aber, dass an der Huffmantabelle noch weiter geschraubt werden kann, hatte ich nicht auf dem Schirm, da ich tatsächlich davon ausgegangen bin, dass die bei meinem Ansatz schon äußerst platzsparend ist.

    Tja und dann kommt ihr und haut Methoden raus um das Char-Array noch weiter einzudampfen.

    Allerdings müsst ihr mir noch nachhelfen, da ihr aktuell vom Methodenverständnis her noch einige Kilometer weit vor mir lauft.

    Ich versuche den Ansatz mal mit meinen Worten zusammenzufassen und ihr sagt ob ich es gerafft habe oder eben nicht:

    • Man nehme das originale Char-Array und sortiere es.
    • Die Berechnungsvorschrift um vom sortierten Array zum ursprünglichen Array zu kommen, kann als Abfolge von swaps beschrieben werden.
    • Je nach Umfang der Umsortierung ist dies mal eine kurze, mal eine lange Liste. Sie ist aber immer kürzer (geht auch gleich lang?) als das Gesamtarray.
    • Problem hierbei: Die Berechnungsvorschrift zwischen 2 Permutationen lässt sich 1. nicht mit einem allgemeingültigem Algorithmus finden und 2. nicht immer effektiv. (meine Recherche erbrachte, dass man diese Swapliste mit dem Pancake-Sorting-Algorithmus erhalten kann)
    • Diese Liste ist nun der erste Teil.
    • Dazu braucht es nun die Werte des Arrays. Diese werden folgendermaßen kodiert:
      • Nehme den kleinsten Wert als Ausgang.
      • Von diesem ausgehend speichere die relative Wertdifferenz zwischen den aufeinanderfolgenden Werten (Abstandskodierung)
      • Da die Abstände große Peaks enthalten, kann diese Liste gut per Huffman kodiert werden.
    • Man hat nun also die Swap-Liste + die Huffman-kodierte Char-Abstandsliste und beide zusammen können im Idealfall kleiner sein als das unkodierte Char-Array.

    Soweit verstanden?
    Die Abstandskodierung fand ich erst einmal sehr erhellend und dann fiel mir irgendwann auf, dass ich das ähnliche Prinzip bereits in der BinaryHelpers.au3 in der Funktion _bin_shrinkString2Bin() umgesetzt habe (dort sind es jedoch keine Abstände sondern Absolutlevel - von daher nur halb soweit gedacht).

    Einmal editiert, zuletzt von AspirinJunkie (24. Mai 2023 um 09:09)

    • Je nach Umfang der Umsortierung ist dies mal eine kurze, mal eine lange Liste. Sie ist aber immer kürzer (geht auch gleich lang?) als das Gesamtarray.
      • Die Liste hat (zumindest bei meinem Ansatz) immer die Länge n-1, da ich für die Swaps nur "eine einzige Zahl" Speichern will und nicht 2. Daher ist der eine Swap-Partner fix ($i ist immer der erste Parameter, also geht man das Array einfach linear durch), und der andere bekommt eine Zahl die man Huffman-kodiert. Man hat also immer n-1 Swaps, was außer bei vollständig zufälligen Arrays nicht optimal ist, aber jede andere Methode war mir zu kompliziert (bzw. dann brauchen die Swaps immer 2 Parameter, und da muss man erst noch untersuchen welche Eigenschaften die haben um die zu komprimieren, bei dem "Ein Parameter Swap" (also immer Swap($i, $n)) weiß man ja exakt welche Werte $n haben kann (immer im Bereich [0, $iLen - $i], und dieser Bereich wird kleiner wenn $i steigt), und das nutzt man zum komprimieren aus.
  • Tja und dann kommt ihr und haut Methoden raus um das Char-Array noch weiter einzudampfen.

    Hehe, naja, die Hauptarbeit hast du ja schon erledigt 8):thumbup:

    Mars´s Ansatz ist, auch für meine Begriffe, ziemlich abgefahren. Ich vermute, dass ich ansatzweise weiß um was es dabei geht, aber ehrlich gesagt sehe ich wenig Sinn in einer Optimierung im unteren Promillebereich! Daher konzentriere ich mich auf nicht ganz so esoterische Verfahren :saint:

    Interesse hatte ich seit Oscars Thread am Thema ! Leider war ich damals gehandicapped, hatte eine komplette Netzhautablösung und die hat mich dann einige Monate nach der OP noch beschäftigt. Wenn man nichts (richtig) sehen kann, ist auch nicht gut programmieren^^

    Aber das Problem sollte klar sein, wie oben schon gesagt! Den komprimierten String weiter komprimieren ist die eigentliche Aufgabe! Ich werde mal meine Ansätze Bitrotation/Bitverschiebung, Bitwasweißichgedöns exzessiv durchprobieren und schauen was dabei rumkommt....

    Btw. der Joke oben mit dem Primzahlscript geht mir seit gestern durch den Kopf....die anderen Bitmanipulationsverfahren geistern ja auch schon lange durch die Literatur, alle versuchen den bestehenden String so zu manipulieren dass er (minimal) kleiner wird....was aber, wenn man durch zusätzliche, ggf. auch reichlich eingestreute Bits einen Hebel für bspw. RLE / Lauflängenkodierung ansetzen könnte? :/ Auch in der Assembler-Trickkiste schlummern noch etliche, heutzutage kaum noch angewandte Bitmanipulationstricks, auch XOR ist einen Blick wert!

  • Der Grund warum ich niemals "sinnvolle" Sachen mache ist, weil ich genau weiß, dass es irgendwo irgendwen gibt der genau das Selbe schonmal gemacht hat. Wenn ich aber die Vernunft hinten anstelle wird die Chance etwas "neues" auszuprobieren höher ^^

    Und da wir alle in der Matrix leben wird "denen da oben" doch bestimmt langweilig wenn niemand aus der Reihe tanzt :thumbup:

    (Wobei man sich dann fragen muss wie viele Leute von der Sorte es gibt. Wenn es genügend sind wird es auch wieder langweilig, weil sich dann jeder nur einbildet etwas "neues" zu machen)

  • Bin ganz bei dir....manchmal muss man "out of the box" denken damit man nicht vollkommen verblödet^^

    Der Grund warum ich niemals "sinnvolle" Sachen mache ist, weil ich genau weiß, dass es irgendwo irgendwen gibt der genau das Selbe schonmal gemacht hat.

    Die Frage die ich mir dabei immer Stelle und was mich auch fasziniert ist: Was hat den "irgendwo irgendwen" dazu gebracht, genau DAS so zu machen?!

    Deshalb mach blos weiter mit deinen Permutationen! :klatschen:

  • AspirinJunkie

    In der Funktion _huff_decodeBinaryToString() versuchst du ganz zum Schluß per RegExReplace() etwas, was imho so nicht funktionieren kann...außer bei "Textdateien" aka Dateien ohne Nullbytes.

    Was aber funktioniert, ist diese Anzahl an aufgefüllten Nullbits als Byte an den enkodierten String anzuhängen und diese Anzahl Bits beim Dekodieren nicht zu berücksichtigen.

    Der enkodierte String wird damit zwar ein Byte länger, das hat aber den Vorteil, dass man beim Dekodieren beim Erreichen des "letzten Bytes" die angehängten Nullbits nicht "dekodiert", sondern das dekodieren beim Erreichen des letzten "echt kodierten" Bit abbricht.

    Dann funktioniert diese Funktion und auch die UDF nicht nur für Textdateien sondern für jede Art von Daten.

  • In der Funktion _huff_decodeBinaryToString() versuchst du ganz zum Schluß per RegExReplace() etwas, was imho so nicht funktionieren kann...außer bei "Textdateien" aka Dateien ohne Nullbytes.

    Doch doch. Das funktioniert schon für den Fall, für den es gedacht war.
    Nämlich folgender:

    AutoIt
    #include "Huffman.au3"
    
    $sString = "AABC"
    
    Global $bEncoded = _huff_encodeString($sString)
    Global $sStringDecoded = _huff_decodeBinary($bEncoded)
    
    ConsoleWrite($sStringDecoded & @CRLF)

    Führe das einmal mit dem StringRegExpReplace() aus und einmal ohne und du siehst welcher Fall damit gelöst werden soll.

    Beide Varianten scheitern jedoch weiterhin an diesem String: "ABCC"

    Die Lösung ist tatsächlich so wie du sagst: Man muss die Anzahl der aufgefüllten Nullbits mitspeichern.
    Das könnte man gleich am Anfang der kodierten Daten in 3 Bits packen (kann ja nur maximal den Wert 7 annehmen).
    Das war mir durchaus bewusst - ich war in dem Moment aber schlicht zu faul für diesen arg unwahrscheinlichen Sonderfall noch diese Anpassung mit reinzudängeln.

    Ich finde es aber echt geil wie ihr beiden tatsächlich diesen Code bis ins kleinste Detail verstanden habt.
    Ich selbst hatte ab und an schon Probleme zu verstehen was ich eigentlich gemacht habe aber in eurem Fall ist das gleich nochmal ein Zacken schärfer. :thumbup:

  • für diesen arg unwahrscheinlichen Sonderfall noch diese Anpassung mit reinzudängeln.

    Wieso Sonderfall? Die Anzahl der angehängten Nullbits entstehen doch immer, wenn die Summe der Anzahl der enkodierten Bits nicht glatt durch 8 teilbar ist. Und der Dekodierere "zufällig" beim angehängten Bitmuster ein Zeichen (Blatt des Huffman-Baums) erkennt.

    Aber das ist generell eine Designfrage....Maximal sind 7 Bits aufzufüllen. Man muss also nur eine Kombination von Bits zum Auffüllen verwenden, die NICHT zu einem zu dekodierenden Zeichen führt, also beim Erreichen eines Nodes endet. Aber mir persönlich wäre das zu kompliziert, ich würde die Anzahl in 3 Bit irgendwo unterbringen und auswerten.

    zu verstehen was ich eigentlich gemacht habe

    nanana... :D . Der/dein Code ist, wie üblich, einfach nur GEIL! Für mich jedenfalls ist es immer eine Inspiration, diese exzessive Beachtung sämtlicher(!) Design- und Coderegeln "debuggen" zu dürfen....so jedenfalls gehe ich an anderer Leute Code ran: Völlig ahnungslos und Unvoreingenommen zerlege ich die Struktur und setze mir (Scite und seinen Debug-Funktionen sei Dank) reichlich Infoausgaben, um herauszubekommen, was GENAU passiert. Und wenn man dabei über bspw. die o.g. "Kleinigkeiten" stolpert, um so besser! :thumbup: Code improvement FTW!

  • Wieso Sonderfall? Die Anzahl der angehängten Nullbits entstehen doch immer, wenn die Summe der Anzahl der enkodierten Bits nicht glatt durch 8 teilbar ist. Und der Dekodierere "zufällig" beim angehängten Bitmuster ein Zeichen (Blatt des Huffman-Baums) erkennt.

    Na der Sonderfall ist der, dass ein Zeichen den Code 0 besitzt und genau dieses Zeichen am Ende des Strings auftaucht. Das meinte ich mit Sonderfall. Indem ich alle Nullen hinten wegschneide habe ich das bisher umgangen.

    Nun habe ich tatsächlich die Anzahl der ungenutzten Bits noch mit hinzugefügt (gerade bei github hochgeladen).
    Jetzt wird die Größe des kodierten Streams in 37,5 % aller Fälle um 1 Byte ansteigen.
    Ich denke das ist verschmerzbar denn nun hat man den Sonderfall auch noch mit abgedeckt.

    diese exzessive Beachtung sämtlicher(!) Design- und Coderegeln

    Ich denke da sollte kein professioneller Programmier drüber schauen - dann würde die Aussage wohl ziemlich schnell zerpflückt werden.

  • Ich denke da sollte kein professioneller Programmier drüber schauen -

    Glaub mir eins, wenn du jahrelang mit "professionellen" Programmierern zu tun hast und teilweise MONATE(!) auf ein Update/Bugfix mit ähnlichem Umfang wie das von dir in Minuten/Stunden gefixte "Problem" warten musst, und dich dann selbst hinsetzt und programminterne Module ersetzt und erweiterst damit man mit dieser "gestrickten" Software überhaupt sinnvoll arbeiten kann, DANN kannst du einschätzen was "professionell" heißt!

    Ist jemand, der in 16 verschiedenen Programmiersprachen Code "klimpern" kann, und dabei absolut keine Ahnung hat, was die eigentlichen Anforderungen eines Kunden aks Anwenders sind, professionell? Definitiv nicht. Genau so wenig wie sich ein "professioneller" Automechaniker von einem der neuerdings verbreiteten "Teiletauscher" unterscheidet, der das eigentliche Problem nicht analysieren und beheben kann, sondern wahllos Möglichkeiten ausprobiert....

    Professionelles Arbeiten ist keine Sache des Programmierstils, sondern der Intention dahinter.

    Ja, ich kann auch meinen Namen klatschend auf einem Bein hüpfend ganz "hip" meine Problemlösung auf sämtlichen Mediakanälen verbreiten und mich dafür von den anderen Hüpfern und Klatschern feiern lassen, aber ob das in irgendeiner Art und Weise die Welt verbessert stelle ich doch sehr in Frage!