keine eindeutige Lösung bei Huffman Codierung

  • C#
  • .NET 5–6

Es gibt 7 Antworten in diesem Thema. Der letzte Beitrag () ist von Bluespide.

    keine eindeutige Lösung bei Huffman Codierung

    Moinsen,

    ich würde gerne mal ein Übersetzer schreiben, der Buchstaben in Einsen und Nullen mit Hilfe der Huffman Codierung übersetzt.

    NUn habe ich eine Frage zur Übersetzung des Wortes mississippi

    ich kriege folgendes raus:
    m:100
    i:0
    s:11
    p:101 demnach lautet das Wort übersetzt --> 100 0 11 11 0 11 11 0 101 101 0

    schön und gut. Was ich nicht verstehe:
    das s und das i liegen jeweils 4 mal vor. also kann man sie doch bei der Übersetzung vertauschen oder nicht?
    m:100
    i:11
    s:0
    p:101 demnach lautet das Wort übersetzt --> 100 11 0 0 11 0 0 11 101 101 11

    Das sind nach chronologischer Reihenfolge zwei unterscihedliche Ergebnisse.

    Die einzige Rettung ist die Gesamtzahl der NUllen und Einsen. Das sind je an Einsen: 13 und an Nullen: 8 bei beiden Ergebnissen.

    Ist das dann die Lösung? Also dass es quasi Egal ist in welcher Reihenfolge die binären Daten vorliegen, sondern zum Ende die Gesamtanzahl?

    Visual_Prog schrieb:

    also kann man sie doch bei der Übersetzung vertauschen oder nicht?
    Was genau schwebt Dir vor zu tauschen?
    Letztenendes erstellst Du ein Dictionary<char, byte[]> und bekommst für jeden Buchstaben einen Code. So etwas wie ein Morse-Alphabet.
    Frage: Ist diese Codierung reversibel?
    Bekommst Du aus der 0-1-Folge den Ursprungstext generiert?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Was genau schwebt Dir vor zu tauschen?

    Das s und das i habe ich in meinen beiden Beispielen vertauscht, weil das bei der Huffman Codierung egal ist, von welchem Buchstaben de Rede ist sondern nur wie oft er vorkommt.

    Ja das habt ihr schon vorgegriffen das Ganze ist also anscheinend reversibel das ist natürlich erfreulich. Auch, dass es in meinem Beispiel egal ist, ob i und s vertauscht werden.

    Ich glaube, du solltest die Kraftsche Ungleichung beachten de.wikipedia.org/wiki/Kraft-Ungleichung : Und ja, wer immer diesen Artikel geschrieben hatte, wollte es auf möglichts unverständliche weise formulieren.

    Das sieht sehr spannend aus vielen dank.

    Letztenendes erstellst Du ein Dictionary<char, byte[]> und bekommst für jeden Buchstaben einen Code. So etwas wie ein Morse-Alphabet.


    Ja danke für die Idee werde das vermutlich so erstellen

    Für mich gibt es eine Lösung, wie das Beispiel auch zeigt (siehe Anhang).

    Als Beispiel in der Tabelle gibt es keine 10 der im code 100011110111101011010 passt. Genau so auch z.B. bei "110" nicht.

    Das wunderbare an der Sache ist, dass es nähmlich die einzelnen Konstellationen nur jeweils einmal in der oberen Tabelle gibt, wenn man von Links nach Rechts geht. 100-0-11-11-0-etc. Die Baumstrukture macht das so möglich. Daher kann es problemlos aufgelöst werden

    Nachteilig ist aber, dass die obige individuell dafür erstellte Tabelle gebraucht wird, um den Huffman-Code aufzulösen. Sie muss also dem Compress-Code mitgeliefert werden.

    Auch interessant ist, wie man erkennen kann, die Gesamtlänge beträgt 21. Um so mehrmals ein Buchstabe in der Menge vorkommt, um so kleiner ist die daraus resultierende Länge nach Huffman. I = 1; S = 2; P = 3; M = 4;
    Das ist auch genau der Grund warum der Hoffman-Code "komprimiert".3

    Freundliche Grüsse

    exc-jdbi
    Dateien

    • HuffmanCode.pdf

      (160,64 kB, 19 mal heruntergeladen, zuletzt: )

    Also ich habe deine Frage jetzt noch nicht so richtig verstanden.

    Zur Dekodierung eines Huffman-kodierten Datenstroms ist beim klassischen Verfahren das im Kodierer erstellte Codebuch notwendig

    Du kannst nicht nur aus dem Übersetztem das Wort decoden. Dazu brauchst du das Wörterbuch. Das wird festgelegt oder mitgesendet. Und wenn du dann die Buchstaben tauscht, dann hast du ja auch das neue Wörterbuch mit den getauschten Buchstaben drin? Bin verwirrt. Ich verstehe die Frage noch nicht :D .