Entwickeln von einem "kompakten Huffmann Code"

[martin1561 (Gast)]

Hallo zusammen

Kann Jemand mir helfen beim Entwickeln von einem "kompakten Huffmann 
Code" über {0,1}" ?

Hier ist offenbar : Y = 0,1 und "C" ist gesuch, wobei X = (x1, x2, x3, 
x4, x5, x6) und P=(1/3, 1/4, 1/6, 1/12, 1/12, 1/12). Leider kann ich im 
Internet keine klare bzw. einfache Methode finden um den Code zu 
entwickeln!

Danke im Voraus

[Martin (Gast)]

Ist auf der Wikipedia gut erklärt:

https://de.wikipedia.org/wiki/Huffman-Kodierung

https://en.wikipedia.org/wiki/Huffman_coding

[martin1561 (Gast)]

Vielen Dank für die Antwort. Ich verwende diese Methode. Ich stecke 
bleiben nachdem ich x5 und x6 addiere und zu 0.16 komme. Soll ich diese 
0.16 zu X4 oder X3 addieren ?

Danke nochmals

[npn (Gast)]

martin1561 schrieb:
> Soll ich diese
> 0.16 zu X4 oder X3 addieren ?

Folge den schwarzen Linien :-)

[martin1561 (Gast)]

Folge den schwarzen Linien :-)

Welche Lienie :D kannst du bitte ein kleines bisschen ausführlicher 
erklären?

Ist es auch richtig so weit?

Danke

[martin1561 (Gast)]

Ich weiß , dass es einen Fehler irgendwo gibt, aber ich weiß nicht ab 
welchem Schritt!

[Egon D. (Gast)]

Martin schrieb:

> Ist auf der Wikipedia gut erklärt:
>
> https://de.wikipedia.org/wiki/Huffman-Kodierung
>
> https://en.wikipedia.org/wiki/Huffman_coding

Komische Erklärungen.
Wenn ich nicht schon wüsste, wie's geht, wüsste ich
nach dem Lesen immer noch nicht, wie's geht.

[Egon D. (Gast)]

martin1561 schrieb:

> Vielen Dank für die Antwort. Ich verwende diese
> Methode.

Nicht wirklich :)


> Ich stecke bleiben nachdem ich x5 und x6 addiere
> und zu 0.16 komme. Soll ich diese 0.16 zu X4 oder
> X3 addieren ?

Hmm. Also ich kenne das so:

1. "Erstelle eine Liste mit allen Symbolen und ihren
   relativen Häufigkeiten!"

Die Liste ist m.o.w. vorgegeben; ich schreibe sie nochmal
hin und verwende aus Gründen der Schreibfaulheit die
Symbole A...F statt x1...x6. Die gegebene Liste lautet:

A     1/3   0.333 
B     1/4   0.250 
C     1/6   0.166 
D     1/12  0.083 
E     1/12  0.083 
F     1/12  0.083

2. "Sortiere die Liste nach fallender Häufigkeit!"

Das ist zufällig schon der Fall.


3. "Fasse die letzten beiden Symbole der Liste (d.h.
   die beiden Symbole mit der geringsten Häufigkeit)
   zu einem Ersatzsymbol zusammen!"

Die beiden letzten Symbole der Liste sind E und F;
diese werden zum Ersatzsymbol EF zusammengefasst. Die
Häufigkeiten werden natürlich addiert.
Die Liste sieht jetzt so aus:

A     1/3   0.333 
B     1/4   0.250 
C     1/6   0.166 
D     1/12  0.083 

EF    1/6   0.166

4. "Füge das neu entstandene Ersatzsymbol so in die
   Liste ein, dass die Sortierung wieder korrekt ist!"

EF am Ende der Liste ist offensichtlich falsch, weil
D eine noch geringere Wahrscheinlichkeit als EF hat.
Es zeigt sich aber das Kuriosum, dass man EF vor oder
nach C in die Liste schreiben könnte, denn die
Häufigkeiten von EF und C sind identisch.
Der Witz ist: Das ist egal; es entstehend zwar unter-
schiedliche Codes, aber deren mittlere Wortlänge ist
gleich.
Wir entscheiden uns willkürlich, EF nach C einzuordnen.
Die neue Liste lautet somit:

A     1/3   0.333 
B     1/4   0.250 
C     1/6   0.166 
EF    1/6   0.166 
D     1/12  0.083

5. "Falls noch mehr als zwei (Ersatz-)Symbole in der Liste
   stehen, setze bei 3. fort; andernfalls gehe zu 6."

Es entstehen schrittweise die Listen

A     1/3   0.333 
B     1/4   0.250 
DEF   1/4   0.250 
C     1/6   0.166

CDEF  5/12  0.416 
A     1/3   0.333 
B     1/4   0.250

CDEF  5/12  0.416 
AB    7/12  0.583

6. "Vergib für die beiden (Ersatz-)Symbole in der Liste
   willkürlich die Codeworte 0 und 1!"

Die Liste sieht jetzt so aus:

CDEF  5/12  0.416    "0" 
AB    7/12  0.583    "1"

7. "Zerlege das zuletzt entstandene Ersatzsymbol der Liste
   wieder in seine Bestandteile und hänge 0 bzw. 1 an die
   zugeordneten Codeworte an!"

Das zuletzt entstandene Ersatzsymbol der Tabelle ist AB;
wir erhalten jetzt wieder folgende Liste:

CDEF  5/12  0.416    "0" 
A     1/3   0.333    "10" 
B     1/4   0.250    "11"

8. "Wiederhole 7. so lange, bis keine Ersatzsymbole mehr
   in der Liste stehen!"

Man erhält nacheinander die Listen:

A     1/3   0.333    "10" 
B     1/4   0.250    "11" 
DEF   1/4   0.250    "01" 
C     1/6   0.166    "00"

A     1/3   0.333    "10" 
B     1/4   0.250    "11" 
C     1/6   0.166    "00" 
EF    1/6   0.166    "010" 
D     1/12  0.083    "011"

A     1/3   0.333    "10" 
B     1/4   0.250    "11" 
C     1/6   0.166    "00" 
D     1/12  0.083    "011" 
E     1/12  0.083    "0100" 
F     1/12  0.083    "0101"

Keine Gewähr für Korrektheit.
HTH

[c-hater (Gast)]

Egon D. schrieb:

> Komische Erklärungen.
> Wenn ich nicht schon wüsste, wie's geht, wüsste ich
> nach dem Lesen immer noch nicht, wie's geht.

Dann hast du ein echtes Problem. Das Prinzip ist klar und einfach 
dargestellt und ziemlich trivial.

Alles, woran man noch scheitern kann, ist das Verständnis des Prinzips, 
und dessen praktischer Implemetierung.

Beides ist allein dein Ding. Die praktische Implementierung erfordert 
einzig das Verständnis des Prinzips und grundlegende 
Programmierfähigkeiten.

Was also ist dein Problem? Vermutlich nur: keine passende Wichsvorlage 
für C&P gefunden...

[Erwin D. (Gast)]

c-hater schrieb:
> keine passende Wichsvorlage

Bist du mal wieder auf deinem Niveau angelangt?

[c-hater (Gast)]

Erwin D. schrieb:

> Bist du mal wieder auf deinem Niveau angelangt?

Wenn du damit meinst, dass es meinem Niveau entspricht, dieses 
unsägliche C&P-Programmierertum anzuprangern, dann ja: da bin ich wohl 
wieder angelangt!

Wäre mir selber auch lieber, wenn das seltener passieren würde. Nur 
leider wächst halt die Herde der C&P-Idioten wohl unaufhörlich...

[Kastanie (Gast)]

c-hater schrieb:
> Egon D. schrieb:
>
>> Komische Erklärungen.
>> Wenn ich nicht schon wüsste, wie's geht, wüsste ich
>> nach dem Lesen immer noch nicht, wie's geht.
>
> Dann hast du ein echtes Problem. Das Prinzip ist klar und einfach
> dargestellt und ziemlich trivial.
>
> Alles, woran man noch scheitern kann, ist das Verständnis des Prinzips,
> und dessen praktischer Implemetierung.
>
> Beides ist allein dein Ding. Die praktische Implementierung erfordert
> einzig das Verständnis des Prinzips und grundlegende
> Programmierfähigkeiten.
>
> Was also ist dein Problem? Vermutlich nur: keine passende Wichsvorlage
> für C&P gefunden...

Sorry hater, du machst deinem Namen alle Ehre - nur dass du dein 
Hassfeld willkürlich erweiterst.
Egon hat das m.E. wunderbar dargestellt und er hat eben kein Problem, 
sondern hat das einfach nochmal etwas ausführlicher erläutert.
Was ist hingegen dein Problem?
Dass du nicht so schön erklären, sondern nur so schön stänkern kannst?
O.k. das ist auch eine Kunst!