Adaptiver Huffman Encoder

  • Moin,


    (Gleich zu Beginn mal ein Wiki-Link, jeder der nicht weiß worum es geht sollte den ggf. erst durchgehen :))


    Einen Huffman Encoder kann vermutlich jeder basteln (ist ja nicht so schwer) wo ich aber häufig Probleme beobachtet habe ist der Part mit dem Abspeichern der Wahrscheinlichkeitstabelle. Es ist nämlich so, dass der Decoder im Regelfall den Huffman-Baum zum dekodieren benötigt.


    Beispiel:

    Wenn ich jetzt aber meinen Text: "Hallo Test 123" verwende gibt es ein großes Problem: Der Text besteht aus vielen verschiedenen Zeichen (es ist ja nicht "aaaaaaabbabaaaa" oder soetwas) die jeweils auch nicht allzuoft vorkommen (Leerzeichen x2 und "l" x2), egal in welcher optimierten Darstellung ich den Huffman-Baum abspeichere, er wird in jedem Fall mehr Speicher verbrauchen als mein eigentlicher Text. Wenn ich jetzt den kodierten Text + Baum benötige um wieder meinen ursprünglichen Text zu erhalten ist nichts gewonnen. Hier kommt der adaptive Teil zum tragen.


    Ein adaptiver Kodierer beginnt mit irgendeiner vorgegebenen Wahrscheinlichkeitsverteilung (z.B. eine Gleichverteilung, dann hat jedes Zeichen beim erstmaligen auftreten 8 Bit, da es 256 theoretisch mögliche Asc Zeichen gibt), generiert daraus den Huffman-Baum und kodiert damit nur das allererste Zeichen des Textes. Dann wird dieses Zeichen mit einem gewissen Faktor zur Wahrscheinlichkeitstabelle hinzugefügt, ein neuer Baum generiert und damit das 2te Zeichen kodiert. usw usw. Das bedeutet, dass der Decoder KEINEN Baum benötigt, da dieser implizit durch die kodierte Nachricht selbst mitgeliefert wird. Das hat eine ganze Reihe Vor- und Nachteile.


    Vorteile:

    - Funktioniert auch für kurze Texte deren Huffman-Baum alleine schon größer wäre als der Text selbst

    - Falls man eine Dämpfung festlegt (in meinem Skript nicht enthalten) ist es möglich dass der Kodierer lokal besser arbeitet als wenn für den vollen Text die gleiche Verteilung angenommen werden würde.

    - Da die Wahrscheinlichkeitsverteilung laufend angepasst wird kann man von einem beliebigen Startpunkt aus loslaufen. Eine Gleichverteilung, oder ein Histogramm aller Zeichen in meinem UDF-Ordner, oder der Buchstabenverteilung in irgendeiner Sprache. In diesem Fall müsste man dem kodierten Text z.B. 2 bit voranstellen damit der Decoder weiß welche Verteilung er als Startwert nehmen soll. Man könnte auch die nicht adaptive Version so verwenden und statt einem Baum nur eine Baumnummer in den kodierten Text schreiben. Das wäre aber bei weitem suboptimaler, da dieser Baum dann nicht angepasst werden würde und man nicht für jeden beliebigen Text einen gut passenden Baum im Decoder hinterlegen kann. Eine Hand voll Verteilungen reichen bei der adaptiven Version aber vollkommen aus um immer ein gutes Ergebnis zu erzielen.


    Nachteile:

    - Da nach JEDEM ZEICHEN alles neu aufgebaut werden muss ist diese Methode unglaublich langsam (eine Version mit Min-Heap bastele ich gerade bin aber noch nicht zufrieden).

    - Da die Wahrscheinlichkeitstabelle laufend angepasst wird ist sie zu keinem Zeitpunkt "wirklich" optimal. Verglichen mit einem "normalen" Huffman-Code ist die adaptive Version je nach situation unterlegen und erzeugt längeren Output als notwendig.

    - Der Textanfang wird zwangsweise suboptimal kodiert, da die Startverteilung (z.B. die Gleichverteilung) nicht immer gut auf die vorliegende Zeichenfolge passt.

    - Habe ich langsam schon erwähnt? (auf meinem PC aktuell ca. 20-25 Zeichen/Sekunde)


    Villeicht kann ja jemand das Skript gebrauchen, daher landet es hier :)


    Edit: 12.03.19:

    Jetzt funktioniert das ganze mit Min-Heap und ist ca. 30% schneller als vorher. Es hat viel Spaß gemacht das Teil im Rahmen der Geschwindigkeit von AutoIt zu optimieren. Wenn man die Methode aber tatsächlich auch benutzen will sollte man es in einer anderen Sprache tun... 30 Zeichen/Sek ist unzureichend, alleine diesen Post hier zu kodieren würde ne Stunde dauern :D



    lg

    M

  • Hi,

    ist aber ADH_Build

    ich liebe diese Freud´schen "Versprecher":thumbup:


    Ansonsten halte ich diese Idee für sehr gut, habe etwas ähnliches auch schon bei Bildkomprimierung mit verschiedenen anderen Varianten zusammen eingesetzt. Im Deskstream-Programm wurde das aber letztendlich verworfen, später mehr dazu^^


    Wie du schon angesprochen hast, ist das "Problem" ja, die "passende" Kodier/Dekodiertabelle aufzubauen. Der "optimale" Baum muss zwangsläufig IMMER mitgesendet werden, wenn es richtig dumm läuft, unterscheidet dieser sich bei ähnlichen Bildern/Texten/Daten kaum, von daher könnte man direkt einige/mehrere "halboptimale" Bäume beim Empfänger abgespeichert lassen und dann nur noch die "Baumnummer" (passt in EIN Byte) mitsenden!

    Den Vorteil hast du klar erkannt, Rechenersparnis sowohl beim Sender als auch beim Empfänger!

    Bleibt die Zeit, die Nachricht zu übertragen, und letztendlich ist DAS das eigentliche Problem.

    Mit heutiger Prozessortechnik und Rechenleistung ist das aufbauen selbst eines "optimalen" Huffmann-Baums in Mikro/Millisekunden erledigt, sowohl beim Sender, als auch beim Empfänger. Aber der Versand/Übertragung per Netzwerk kostet Faktor hundert bis tausend mal so viel Zeit!

    Von Latenzen garnicht zu sprechen! Warum sehen denn Videokonferenzen immer noch bescheiden aus, trotz massiver Rechen/Rechnertechnik. Warum laden Videoportale/Streamingdienste massivst Daten vor, und hoffen inständig, dass der User eine "gute" Anbindung zu seinem Provider hat?!

    Der Weg zum Empfänger ist zzt. das Problem, nicht die Kodier/Dekodierroutine!

  • Hehehe,


    ich wollte die Sache erst "ADH = ADaptive Huffman" nennen, dann ist es aber "AHE = Adaptive Huffman Encoder" geworden. Wahrscheinlich wäre "AHC = Adaptive Huffman Code" noch besser. Namensfindung ist so kompliziert :(


    Den Baum aufspannen dauert (mit der jetzigen Methode) in AutoIt ca. 50ms. Schätze man kommt noch auf ca. 20-30ms wenn man ein wenig optimiert. Da ich alles so umgebaut habe, dass es inplace in einem Array stattfindet könnte man es 1 zu 1 in ASM übersetzen. Dann werden aus 20ms -> 20µs.


    //OT:

    Mit dem Internet stimmt wirklich etwas nicht. Ich wollte mir letztens einen Stream auf YT ansehen, der hat furchtbar gehackt ist andauernd stehengeblieben und konnte nur via F5 wieder für ein paar Sekunden am laufen gehalten werden. Dieses Totalversagen schiebe ich aber auf die Software. Meine Leitung hat einen Ping von ca. 25ms und kann ca. 5MB/s (wenn sie gute Laune hat), ich erwarte dass ein Stream damit flüssig läuft :thumbdown:

  • Mit dem Internet stimmt wirklich etwas nicht. Ich wollte mir letztens einen Stream auf YT ansehen, der hat furchtbar gehackt ist andauernd stehengeblieben und konnte nur via F5 wieder für ein paar Sekunden am laufen gehalten werden. Dieses Totalversagen schiebe ich aber auf die Software. Meine Leitung hat einen Ping von ca. 25ms und kann ca. 5MB/s (wenn sie gute Laune hat), ich erwarte dass ein Stream damit flüssig läuft :thumbdown:

    "Normales" Internet?! Schnell?! :rofl: Träumt alle mal weiter...


    Die Deutsche Börse (und auch andere Börsen weltweit) hat gerade erst ein "Tempolimit" für den Aktienhandel eingeführt, welches den Händlern eine Zeitbeschränkung von mindestens einer TAUSENSTEL Sekunde ermöglicht, innerhalb dessen sie kaufen/verkaufen können, ohne das das Handelsobjekt von sog. Hochfrequenzhändlern "weggeschnappt" wird.

    Da geht es um Mikrosekunden für die komplette Transaktion über zigtausend Kilometer, und du bist happy mit einem PING (*rofl*) von 25 ms. Bin mal gespannt auf deine Methode, diesen "Ping" zu MESSEN. Ja MESSEN. Anzeigen lassen kann man sich nämlich viel....8o


    Das "Internet" ist imho nur die sichtbare Spitze des Eisbergs. Da wird ein bissl rumgepickelt um den Anwendern mit YT/Facebook/Twitter/Streaming uswusf einige Brocken vorzuwerfen, die dankbar angenommen werden. Die "real" verfügbare Technik bleibt anderen vorbehalten, wer will das den Providern auch verdenken? Wenn DU mit Technik richtig viel Geld verdienen kannst, wieso sollst du dich um Leute kümmern, die 99% ihrer "Online"-Zeit mit hochgradig geistigem Dünnschiss verplempern? Und diese "Leistung" dann auch noch möglichst "umsonst" haben wollen?

    Da wird nach "Leistung" gequiekt und "schnellem" Internet. Mal angenommen, in Deutschland bestünden 80 Millionen Internetanschlüsse, und jeder würde im Monat 100€ Kosten. Das sind zusammen gerade mal 8 Milliarden. Im Vergleich zu den BILLIONEN, die "nur" allein die Deutsche Börse mit "schnellem" Handel in diesem Zeitraum umsetzt, ist das NICHTS!

    Überzeuge doch einfach deine 80 Millionen Mitinternetbenutzer, im Monat 1000€ für eine "schnelle" Leitung zu bezahlen, und das Geschwindigkeitsproblem ist sofort gelöst.

    Oder sollte nach diesem Vorschlag etwa rauskommen, dass die Nutzer für den Müll, den sie über die Leitung jagen, eigentlich gar kein "schnelles" und schon gar nicht kein "kostenloses" Internet brauchen/wollen?!:/

    Oder ist es etwa so, dass es dieses "schnelle" Internet bereits gibt, aber es kaum nachgefragt wird, weil es Geld kostet?:/


    Btw. hatte ich schon mal erwähnt, dass ich in keinem der sog. "Social-Media"-Dienste angemeldet bin? Und mir daher eine "langsame" aber stabile Internetleitung für meine Anwendungen (ja, auch Onlinezocken incl. TS ab und zu) völlig ausreicht?! Und ich trotzdem noch zufrieden lebe? 8o

  • :rofl:

    01010110101111100000000010101101010010000100110110001001010101111011010101001010011111010111000000001111000000111100010001010001100111000100011101110110110011011101111000001010101011011010010011001111101001110011111001011111111001000111100001001000111011101011010111001110000000100100101000010011011110111111111010101010000110011101110001111011111000110111000001011011100001100001001101100101101101001100010011110110000010001001011010000101111111111111100010010

    ...... Lieben Gruß, ........
    ...........
    Alina ............

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Ich habe die Deutsche Hilfe auf meinem PC und
    OrganizeIncludes ist beim Scripten mein bester
    Freund. Okay?

  • Welche Bedeutung haben die Zahlen im "Global $__AHE_aHistDefault". Ich habe da mal andere Zahlen reingeschrieben.

    Also statt , 0, 0, 0, 0, hab ich , 29, 2, 19, 50, genommen und es wurde einwandfrei codiert und decodiert.

    Habe ich da etwas den Sinn verpasst oder den Durchblick nicht gefunden? Häääääääääääääää :/:/:/:/

    ...... Lieben Gruß, ........
    ...........
    Alina ............

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Ich habe die Deutsche Hilfe auf meinem PC und
    OrganizeIncludes ist beim Scripten mein bester
    Freund. Okay?

  • Die Zahlen darin sind eigentlich vollkommen wurscht :D


    Das Verfahren funktioniert so:

    - "Habe" eine Wahrscheinlichkeitstabelle für jedes Zeichen (wenn man nichts weiß ist das eine Gleichverteilung, oder in diesem Fall das Default Histogramm)

    - Baue einen Baum aus der Tabelle, Kodiere/Dekodiere ein Zeichen und erstelle damit die Tabelle neu. -> solange bis keine Zeichen übrig sind.


    Was du da reinschreibst ist also egal, alles was sich dadurch ändert ist die Kompressionsrate zu Beginn. Allerdings kann man keinen Text dekodieren, wenn eine andere Tabelle benutzt wurde als im Encoder, also könnte man dieses 256 float Gebilde als eine Art "viel zu langes Passwort" missbrauchen :D


    Max Mustermann, Musterbergheimer Landstraße 1 99, 12345 Musterbergheim am Musterberg.


    Edit: Falls jemand das Teil nochmal angesehen hat, ich habe den Min-Heap ergänzt, somit ist es jetzt ca. 30% schneller als vorher. Da es immernoch inplace in einem Array funktioniert kann man das 1:1 in jede beliebige Sprache genauso übernehmen und es müsste immer ziemlich effizient arbeiten. Außerdem habe ich TreeToLookup optimiert, sodass sie statt 3ms nur noch 2ms benötigt, leider immernoch rekursiv...


    lg

    M

  • Hi Alina,

    Habe ich da etwas den Sinn verpasst oder den Durchblick nicht gefunden?

    im dänischen Wiki wird das Thema SEHR kurz behandelt^^ https://da.wikipedia.org/wiki/Huffman-kodning

    Das deutsche und englische Wiki behandeln das Thema sehr ausführlich. (Link im Startpost)


    Also statt , 0, 0, 0, 0, hab ich , 29, 2, 19, 50, genommen und es wurde einwandfrei codiert und decodiert.

    was auch nicht wundert, diese Zeichen werden im Text nämlich gar nicht verwendet...^^


    In einer Huffman-Tabelle befinden sich 255 Werte aus "binären Bäumen" , jeder entspricht einem ASCII-Zeichen. Im "richtigen" ASCII-Zeichensatz wird jedes Zeichen mit jeweils 8 Bit "kodiert", die ASCII-Codetabelle findest du überall, die hat jeder Programmierer unter dem Kopfkissen liegen^^ (auch in der AutoIt-Hilfe im Appendix)


    Der Sinn der Huffman-Kodierung ist, die am häufigsten vorkommenden Zeichen mit viel weniger als 8 Bit darzustellen. Stell dir einen binären Baum vor (ansonsten schau ins Wiki, da ist einer abgebildet), Die "Blätter" des Baums werden jetzt durch 1- und 0 "Zweige" beschrieben. Nach links gehts bei jedem Abzweig zur 1, nach rechts ist eine 0. Am "Ende" jeden Zweigs hast du dann eine Bitfolge, "oben" im Baum wenige Bits, unten viele Bits. Wenn du jetzt an jedes "Ende" eines Zweigs einen Buchstaben schreibst, dann entspricht dieser Buchstabe der Bitfolge bis da hin. Soweit klar?


    Im Beispiel im Wiki entspricht der Buchstabe "a" dem Bitcode 1, "b" entspricht 01, "c" 001, "d" 000

    "abcd" würde also entsprechen 101001000, also insgesamt 9 Bit. In ASCII- "Kodierung" wäre "abcd" aber 4*8Bit=32Bit lang!

    Mit der Huffman-Kodierung hättest du somit 23 Bit gespart! Oder nur 28% an Daten!


    Diese Komprimierung wird unter anderem auch bei JPEG, also Komprimierung von "Farben" in Bildern verwendet.


    Wenn du also die "Wege" im Baum zum Buchstaben veränderst ohne zu wissen was du da tust, veränderst du die KODIERUNG, was an sich kein Problem darstellt...

    Da dieser "Baum" aber auch zur DEKODIERUNG benutzt wird, hast du ggf. mit deinen " zufälligen" Werten die Wege zu Buchstaben beschrieben, die aber im Baum eventuell (sicher) gar nicht an dieser Stelle, oder genauso schlimm, doppelt existieren!


    Im Script von Mars entspricht das Array $__AHE_aHistDefault[$i] aber nicht einer Huffman-Tabelle, sondern einer Wahrscheinlichkeitsverteilung (ähnlich einem Histogramm in einem Bildbearbeitungsprogramm).

    Ändere die beiden 25 in der Tabelle auf bspw. 2555(willkürlich sehr hoch gewählt) . Dann ändert sich die Anzahl der Bits pro Char von 5,14 auf 5,10. Also eine Verbesserung:klatschen:. Aber nur für DIESEN Beispiel-Text!

    Die Frage ist ja, mit welcher Tabelle deckt man "am wahrscheinlichsten" möglichst viele Texte ab.

    Dann müsste man den Huffman-Baum nicht jedes Mal neu aufbauen (Anhand der Häufigkeit der Buchstaben) , sondern könnte eine "Universaltabelle" benutzen....:party:

    Aber da der Sinn einer "optimalen" Komprimierung darin besteht, IMMER den kleinst mögliche Größe zu erhalten, egal welche Daten vorliegen, MUSS für eine "optimale" Komprimierung die Tabelle immer neu aufgebaut werden.

  • DANKE DANKE DANKE ! ! !

    ...... Lieben Gruß, ........
    ...........
    Alina ............

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Ich habe die Deutsche Hilfe auf meinem PC und
    OrganizeIncludes ist beim Scripten mein bester
    Freund. Okay?