Beiträge von manakoDE

    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.

    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

    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!! :)

    Hallo, da es langsam in einen brauchbaren Zustand kommt suche ich ein oder zwei Beta-Tester für Twistedit.
    Zum Beta-Test gehören das Testen aller Funktionen (Stand-Alone und Zusammenspiel aller Funktionen).


    Natürlich kann man das auch verbinden indem man ein kleineres oder größeres Projekt damit umsetzt,
    der technische Support sollte jederzeit gegeben sein.


    Für alle die nicht wissen was Twistedit ist, hier nochmal der Beitrag.


    P.S.: Ignoriert die Bilder in dem Thread, die sind schon etwas älter.

    10000-0000.png


    Willkommen beim Projekt zu Parasite Eve.


    Ursprünglich war das Projekt damals in einer Facebook-Gruppe geplant, dort hatte ich gefragt welches Spiel die
    Mitglieder dort am liebsten übersetzt haben wollten, raus kam Parasite Eve, dicht gefolgt von Wild Arms 2.
    Anfangs lief es auch recht gut, aber wie das meist so ist sind nach und nach viele Leute vom Projekt
    abgesprungen, in Form von Null-Kommunikation oder einfach durch Nichtstun.
    Nach einer Weile war dann nur noch Bent[pG] aktiv an der Übersetzung dran und hat den Löwenanteil übersetzt.
    Mittlerweile konnten wir noch 2 Leute dazu gewinnen, von denen ich glaube dass sie in der Lage sind dieses Projekt
    auch wirklich zu Ende zu führen.
    Poe, der den Beta-Test zu Breath of Fire mit leitwolf gemacht hat und
    Celes, der sehr viel Arbeit in das Suikoden-Projekt gesteckt hat und es auch zu Ende bringen wird.


    Das Projekt läuft schon eine Weile und sollte nun langsam auch mal angekündigt werden.


    Der Status:
    Projektstart: 04.03.2019
    Projektende: Ende 2020 (Zumindest ist es so geplant)
    Tools für die Übersetzung: Google Docs (am Anfang), später TwistEdit
    Script: 100%
    Menüs: 100%
    Grafiken: 25%

    Also wenn du einen HotKey meinst um neue Zeilen und Boxen zu erstellen, dann ist das längst drin.
    Die TBL ist ziemlich variabel, sie erlaubt mehrere Einträge pro Wert, dadurch kann man das Verhalten
    des gesamten Scripts steuern, in diesem Fall ist deine Enter-Taste schon der HotKey.
    Am Ende einer Zeile kommt ein Zeilenumbruch und wenn man eine Leerzeile macht wird das
    was danach kommt automatisch als neue Textbox erkannt:



    fotos online hochladen



    TBL:

    fotos online hochladen

    Das ist bereits in Arbeit, das Tool arbeitet später mit einer Datenbank in der solche Sachen schon drin stehen und in neue Projekte mit übernommen werden.
    Wenn du also wie du bereits sagst in BoF "Herb" zu "Kraut" übersetzt, dann wird sowas automatisch auch übernommen falls jemand BoF4 übersetzt! :)


    Solche Ideen sind immer willkommen, bitte immer her damit!!!

    Hallo law36,
    wie das mit Allem ist ist auch das in Arbeit und dauert leider länger als erwartet.
    Zurzeit arbeite ich an dem Importeren/Exportieren von Datenbanken und an der Live-Vorschau.
    Sobald leitwolf wieder etwas mehr Zeit hat fangen wir an die Funktionen für eine Online-Datenbank weiter auszubauen.


    Ein bisschen was kann es aber schon, einige Reader wie für 16Bit-Pointer (SNES) sind bereits implementiert, ich
    teste das ganz gerne an Chrono Trigger und an EVO Search for Eden.


    Der Screenshot stammt aus dem Script von Breath of Fire 4.




    bilder hochladen link