Posts by manakoAT

    Mach ich gerne.

    Wollte das Thema schon länger machen, hab mich dann vor 4 Tagen rangesetzt und einfach angefangen.

    Ich werde das aber noch überarbeiten, mit einem leichteren Beispiel, damit es auch wirklich alle verstehen.

    Ohne Fachbegriffe und höhere Mathematik :-)

    Name: Huffman-Coding

    Typ: Präfixfreie Komprimierung

    Verlustfrei: Ja

    Beispiel: Beliebig

    Link: Wikipedia

    Andere Tutorials: LZSS



    0.) Generelle Infos

    1.) Zählen aller Zeichen im Eingabestrom

    2.) Sortieren aller Einträge

    3.) Positionen im Huffman-Baum festlegen

    4.) Huffman-Bits ermitteln

    5.) Stärken und Schwächen von Huffman-Komprimierung



    0.) Generelle Infos

    Diese kleine Einführung soll euch dabei helfen zu verstehen wie die Huffman-Kodierung funktioniert,

    ich werde versuchen alles, wie immer, ohne Fachchinesisch und komplexe Berechnungen zu erklären.


    Falls jetzt jemand denkt: "Oh Gott, Huffman, das mit diesem komischen Baum!", oder sowas, bitte lest einfach weiter,

    das Wort "Baum", oder "Tree" wird sicher fallen, aber er ist sehr simpel zu erstellen, auch ohne dass man ihn versteht.


    Falls ihr das Gelesene an einem praktischem Beispiel ausprobieren und selbst einen Kompressor basteln wollt,

    ist natürlich etwas Kenntnis in Sachen Programmierung erforderlich, ansonsten könnt ihr mit meinem kleinen Test-Tool

    verschiedene Sachen ausprobieren.


    Download: Huffman-Kodierung



    1.) Zählen aller Zeichen im Eingabestrom

    Als Erstes zählen wir die Häufigkeit aller Zeichen in unserem Eingabestrom, in unserem Beispiel wollen wir den

    String "snes-projects" in Huffman-Bits umwandeln.

    Unser Eingabestrom hat 13 Zeichen, 13 x 8 Bit = 104 Bit.


    Hier eine Liste der Zählung:

    CharCount2.png


    Wie wir unschwer erkennen kommt das "s" und das "e" häufiger vor als die anderen zeichen, diese Häufigkeit macht sich die

    Huffman-Kompression zunutze.



    2.) Sortieren aller Einträge

    Im nächsten Schritt müssen wir alle Einträge sortieren und aus diesen "Zweige" und "Blätter" erstellen.


    Ein "Zweig" teilt sich immer in 2 weitere Ableger, dieses können weitere "Zweige", oder "Blätter" sein,

    "Blätter" sind immer das Ende eines Huffman-Codes, unser dekomprimiertes Zeichen.


    Sortiert wird immer auf- oder absteigend, nach der Häufigkeit der Buchstaben, in meinem Programm ist es absteigend.

    Wir nehmen uns jetzt die beiden kleinsten Einträge, in dem Fall "-" und "c", packen diese beiden zu einem

    "Zweig" zusammen und packen ihn hinten an die Liste.

    Unsere beiden "Blätter" "-" und "c" packen wir in eine neue Liste.


    Wichtig hierbei ist, dass die Liste nach JEDEM Durchlauf neu nach Größen sortiert wird!!!


    1.) Sortieren

    2.) Die beiden kleinsten Werte nehmen und zusammenzählen

    3.) Den erstellten "Zweig" an die Liste hängen

    4.) Die beiden "Blätter" in eine zweite Liste packen

    5.) Löschen der beiden "Blätter" aus der ersten Liste

    6.) Wieder bei Schritt 1 anfangen, bis nur noch ein Eintrag in der ersten Liste übrig bleibt.


    Hier wie es aussieht nach der ersten Sortierung:

    Sorted1.png



    Nach der 6. Sortierung:

    Sorted6.png



    Nach der letzten Sortierung:

    SortedFinal.png


    Jetzt haben wir einen Huffman-Baum in Form einer Liste, sieht nicht aus wie ein Baum, oder? :)


    3.) Positionen im Huffman-Baum festlegen


    Jetzt kommen wir zum spaßigen Teil.

    Unser Decoder braucht später einige Infos um zu wissen wie was zu lesen ist, daher müssen wir alle "Blätter" und

    "Zweige" markieren, das stellt aber kein Problem dar, weil unser "Baum" in der ersten Spalte als Liste durch die Sortierung vorhanden ist.


    Als erstes legen wir alle Positionen fest, so wie die Daten später in der Datei liegen aus der der Huffman-Baum gelesen wird.

    Wir starten bei der Position 0x4, die ersten 4 Bytes sind für unsere beiden Haupteinträge reserviert, mehr dazu später.

    Jedes Eintrag mit einem einzelnen Zeichen (Blatt) ist 2 Bytes lang und jeder andere Eintrag, mit mehr als einem Zeichen, ist 5 Bytes lang.


    Zur Erklärung, aber hier erstmal unwichtig:

    Jeder Eintrag braucht eine eindeutige Identifizierung, deswegen ist jedem einzelnen Zeichen ein Byte mit dem Wert "0x00" und jedem andren Eintrag ein Byte mit

    dem Wert "0xFF" vorgesetzt.


    0x00 = Unkomprimiertes Zeichen (Blatt)

    0xFF = Ein Eintrag der tiefer in den Baum führt (Zweig)


    So sieht die Zuordnung aus wenn sie fertig ist:

    Positions.png




    4.) Huffman-Bits ermitteln


    Jetzt ermitteln wir die Huffman-Bits, dies ist auch recht einfach, weil sie durch die Sortierung in der Liste sehr leicht zu ermitteln sind.

    Die beiden letzten letzten Einträge sind immer unsere Teilbäume, "rts" ist der Teilbaum der nach Links führt und "e-cjnop" ist der Teilbaum

    der nach Rechts führt.


    Was könnte man anstatt "Links" und "Rechts" nehmen um einem Prozessor die Entscheidung zu erleichtern was was ist?

    Richtig "0" und "1" ...!


    "rts" ist also "0" und "e-cjnop" ist "1"


    ...


    Zur Info:

    Die Anzahl der Einträge in einem Huffman-Baum, egal ob als Liste oder sonstwie gespeichert, ist immer durch 2 teilbar,

    daher können wir immer sagen dass ein Eintrag, dessen Position in der Liste eine gerade Zahl ist, eine Linke (0) Abzweigung,

    und ein ungerader Index eine Rechte (1) Abzweigug darstellt.

    Nicht vergessen: Es wird immer bei Index 0 angefangen.


    Hier ein Beispiel:

    BitIndexes.png


    Nehmen wir als Beispiel das "s", wir suchen jetzt von unten nach oben wo das "s" auftaucht.

    Als erstes taucht es in dem "Zweig" "rts" auf, also ist das erste Bit eine "0", wenn wir jetzt weiter suchen,

    taucht das "s" das nächste Mal alleine auf (Position 42), dies ist eine Rechte Abzweigung.


    Das "s" hat jetzt also die Bits "01" bekommen, da es alleine steht ist das Festlegen der Bits für diesen Buchstaben auch fertig,

    wir haben hier nämlich einen einzelnen Buchstaben (ein Blatt) erreicht.



    Nehmen wir als Nächstes das "n", dieses finden wir in "e-cjnop", einer Rechten Abzweigung, also "1".

    Als Nächstes finden wir es in "jnop", wieder eine Rechte Abzweigung, also wieder "1".

    Im nächsten Schritt finden wir es in "jn", einer Linken Abzweigung, also "0".

    Und im letzten Schritt steht es alleine in einer Rechten Abzweigung, also "1".


    Das "n" bekommt also die Bitfolge "1101"



    Wenn wir alle Buchstaben durch haben, sieht das Ganze so aus:

    CalculatedBits.png

    Es hat sich ein wenig getan, die Beta-Phase ist erreicht!


    Auch wenn immer nur Screenshots vom Test zu BoF4 gezeigt werden, es kann trotzdem mehr. :)


    Einige Lesemethoden wurden implementiert, das reicht von Standardpointern, über Virtuelle Dateisysteme bis zu Custom-Readern wie für Fire Emblem IV.

    Zurzeit testen wir die Anbindung an eine SQL-Datenbank, bisher läuft alles fehlerfrei, schnell und zufriedenstellend.


    Ein paar nette Sachen wie die Fortschrittsanzeige unten sind neu, dazu das Ganze nochmal oben in Prozenten, diese beiden Sachen motivieren etwas wenn man dran sitzt.

    Jetzt fehlt eigentlich nur noch die Anzeige der Charakterbilder, falls welche vorhanden sind und der Inserter der sich allerdings auch schon im Test befindet.



    Im zweiten Bild könnt ihr den TBL-Editor nochmal sehen, dieser ist noch nicht wirklich schick, das Besondere an dem eigenen TBL-Format ist eigentlich

    dass man mehrere "Commands" auf einen Eintrag legen kann. Somit kann man sich die Darstellung im Script-Editor beliebig anpassen, Regeln für die TBL

    gibt es fast keine.


    Sobald wir etwas weiter sind (März/April) wird es hoffentlich schon einen ersten Release geben.


    Auf diesem Wege vielen Dank an leitwolf und Poe, die mich mit vielen Ideen und Testläufen unterstützen! :)


    TE_BETA.png



    TE_TBL.png

    Danke für die Info, das wusste ich nicht. Ist interessant da ich viel mit der api selbst baue und bis jetzt bin ich da ganz umsonst rum gekommen :D und wenn man für jede textbox eine eigene Anfrage an Google sendet, umgeht man da nicht die Mengen Begrenzung 8)


    Auch das wurde probiert, nur da Google nicht dumm ist wird nach einer Weile die anfragende IP gesperrt und die API gibt nichts mehr zurück.

    Statusupdate:
    Der Test ist beendet und es wurden nochmal ca. 300 Vorschläge und Mängel abgearbeitet.
    Ein paar Sachen müssen noch getestet werden, aber so lange sollte das (hoffentlich) nicht mehr dauern.


    Der Font sieht schon schick aus, aber Fonts ändern ist irgendwie so 90er, genau wie der Font wahrscheinlich. :)


    Ich werde das aber mal anstoßen, denn lesbarer ist der auf jeden Fall.



    MfG

    Sorry, ich wollte längst ein Statusupdate machen.


    Es ist ALLES im Spiel drin was man nur rein machen konnte, also alle Texte, alle Grafiken, das Intro wurde ausgetauscht, diverse Bugs aus dem Original behoben, etc, etc, etc.
    Zurzeit wird allerdings noch massiv getestet, denn wir wollen sicherstellen dass es auch so läuft wie es laufen soll.



    Der Beta-Test läuft derzeit noch und ich bin sehr zufrieden was dort an kleineren Fehlerchen, aber vorallem an Verbesserungsvorschlägen dokumentiert wird.
    Der Test in dem diese Vorschläge aufgenommen und bearbeitet werden soll laut Plan noch bis zum 31.12.2019 laufen, danach gibt es noch einen 100% Durchlauf von 2 Spielern die alles nochmal auf Herz und Nieren prüfen werden.


    Ich gebe jetzt mal eine ganz vage Prognose ab wann die Übersetzung öffentlich wird: März-April 2020, das ist allerdings keine Garantie dass es dann dort auch erscheinen wird.



    Hier noch eine kleine Übersicht was wir zurzeit machen:

    Vielen Dank für euer Interesse.


    Also für die Übersetzung der Texte brauchen wir niemanden mehr, vielleicht beim nächsten Projekt.


    RetroDima , kannst du dich über Skype bei mir melden? Die Drehgrafik für Suikoden war einfach mega gut, vielen Dank nochmal dafür!! :)