Seite 1 von 3

H6.9 c) und d)

Verfasst: 29. Mai 2007 04:46
von brotkasten
hi,
ich habe den huffman de/kodierungsbaum für die h6.9 c) erstellt. nun habe ich das tolle problem, dass der baum nicht eindeutig ist, d.h. ich bekomme unterschiedliche huffman bäume wenn ich beim verbinden zweier knoten A und B über einen Knoten C die knoten A und B entweder rechts oder links anhänge:

Code: Alles auswählen

    C

A       B  
oder

Code: Alles auswählen

    C

B       A
der algorithmus im härder skript ist da nicht eindeutig. ich habe jetzt z.b. immer den knoten mit dem kleineren wert links angehängt.
je nachdem wie man das macht fallen natürlich die ergebnisse von teilaufgabe d) aus. wie soll das jetzt gemacht werden ? und dann kann ich das "1001011101100001101111110101101000001100" nicht dekodieren, weil ich am ende ein 00 dekodieren muss ... und es gibt kein 00 Codewort in meinem Code.
Wie soll das denn nu gemacht werden! mal ein wort darüber zu verlieren, wie man diesen blöden baum konstruieren soll wäre vll. nicht verkehrt gewesen.

grüße

mhhhpf

Verfasst: 29. Mai 2007 12:36
von brotkasten
naja ... ich habe jetzt einfach mal zwei varianten des baums erzeugt, mit dem 2. baum kann ich wenigstens die nachrichten dekodieren auch wenn "ERFAOROFDAM" kein sinnvolles codewort ist :?

Verfasst: 29. Mai 2007 13:07
von giftnudel
Dekodier halt das was du kannst und schreib hin was du denkst das rauskommt.

Verfasst: 29. Mai 2007 14:39
von brotkasten
das problem dabei ist, dass da bits übrig bleiben, die man nicht weiter dekodieren kann. bei mir bleibt zum schluss 00 übrig und es gibt kein codewort 00... mittlerweile habe ich zwei varianten des dekodierungsbaums erstellt, mit dem einen kann ich das dekodieren ... da kommt aber auch nur müll raus, hab's oben gepostet ("ERFAOROFDAM")

Verfasst: 29. Mai 2007 19:51
von RomanSoldier
der Huffmann ist nicht immer Eindeutig - nur präfixfrei. Wenn du drei gleich große Werte hast, kannst du die auf 3 verschiedene Arten zusammen setzen und erhälst verschiedene Lösungen...

Verfasst: 29. Mai 2007 22:07
von Red*Star
brotkasten hat geschrieben:das problem dabei ist, dass da bits übrig bleiben, die man nicht weiter dekodieren kann. bei mir bleibt zum schluss 00 übrig und es gibt kein codewort 00... mittlerweile habe ich zwei varianten des dekodierungsbaums erstellt, mit dem einen kann ich das dekodieren ... da kommt aber auch nur müll raus, hab's oben gepostet ("ERFAOROFDAM")
Hehe, bei mir bleiben auch genau zwei Nullen übrig. Aber ich hab net das gleiche Wort.

Ist ja auch net schlimm... wie meine Vorredner schon sagten: Der Huffmann-Code ist nicht eindeutig (oder genauer: Ich schätze mal, er ist unter bestimmten Umständen eindeutig /bis auf Isomorphien/, und die Isomorphien sind gerade das, was ihn uns uneindeutig erscheinen lässt*) - aber legt diese Aussage bitte nicht auf die Goldschale, das würde ich nur mal intuitiv so behaupten), von daher bleibt halt hinten beim Decodieren der vorgegebenen Zeichenfolge was übrig oder nicht, was soll's.



*) Die bestimmten Umstände sind, in Prosa ausgedrückt: Man hat in jedem Schritt des Konstruktionsprozesses niemals die Wahl zwischen mehr als zwei Bäumen mit exakt dem gleichen Gewicht. Falls jemand ein Gegenbeispiel hat, wäre ich sehr erfreut, es hier zu sehen, ich bin mir nämlich net sicher ;)

Verfasst: 30. Mai 2007 17:00
von Gnomix
Habt ihr mal den kodierten Text invertiert, also alle Nullen mit Einsen ersetzt und umgekehrt ?
Vielleicht kriegt ihr ja dann einen sinnvollen Text heraus.

Verfasst: 30. Mai 2007 17:43
von RomanSoldier
Der Huffmann ist nie eindeutig; wie Gnomix es bereits andeutet, es kommt darauf an, an welchen Zweig man die 1 bzw. die 0 schreibt. Danke, das war das, was mir nicht einfallen wollte. :D

Verfasst: 31. Mai 2007 17:54
von ykaerflila
Soll denn überhaupt irgendetwas sinnvolles rauskommen?! Hier kommt nonsense raus...

Verfasst: 31. Mai 2007 18:02
von marlic
Folie 8 Seite 32
[...]
Auch andere "gültige" Lösungen sind möglich! Optimierte
mittlere Bitanzahl ist aber bei allen Lösungen gleich!
[...]

Ich probiers jetzt auch mal aus.

Verfasst: 31. Mai 2007 18:47
von RomanSoldier
ich habe mal 4 verschiedene dinge ausprobiert; alleine aufgrund der ungünstigen Codierung von I,A und E kann nichts vernünftiges heraus kommen. Aber viel mehr könnte ich mich über den unfähigen Tutor aufregen, der diese Übung gemacht hat.
Im Aufgabenteil e) könnte man so leicht die mittlere Bitlänge berechnen, wenn die Summe der Zeichenhäufigkeit nicht eine Primzahl wäre ... 9 weniger oder 1 mehr hätte es auch getan ... Dummerweise werden die falschen durch die Unfähigkeit einzelner bestraft: die Studenten ... Danke schön!

Verfasst: 31. Mai 2007 18:55
von marlic
Naja ... Ich wäre mir da nicht so sicher ...vielleicht sollte die Aufgabenstellung gerade die Nichteindeutigkeit der Kodierung klarmachen.

Mich würde eher mal interessieren, ob jemand einen Code findet, der nach Huffmann entsteht, aber das Wort gar nicht dekodieren kann, also am Ende etwas übrig bleibt :) ...
Mir fällt gerade kein Beweis ein, dass das nicht geht.

Edit:

Ah, ich sehe - Brotkasten hat den Thread ja aus dem Grund aufgemacht ...

Gut, dann ist es wohl widerlegt.

Allerdings vermute ich, dass es Codewörter gibt, die bei gegebenen Häufigkeiten IMMER decodiert werden können.

(Zumindest auf einelementigen Alphabeten ist das klar ;), für größere kann man etwa alle Häufigkeiten gleich wählen, dann entsteht ein Code von konstanter Länge, der dann ebenfalls immer zum dekodieren von Wörtern mit einer Bitlänge die ein vielfaches der Bitlänge eines Buchstabens ist, geeignet ist, egal wie man Huffmann anwendet.)


Um das dann noch eindeutig zu machen, kann man eventuell Vereinbarungen für die Implementierung von Huffmann treffen, welche Seite die 1 und welche die 0 zugewiesen bekommt und wie man vor zu gehen hat, wenn nach den Häufigkeiten nicht feststeht, welche Teilbäume zusammengefasst werden müssen.

Verfasst: 31. Mai 2007 21:22
von bruse
RomanSoldier hat geschrieben:Im Aufgabenteil e) könnte man so leicht die mittlere Bitlänge berechnen, wenn die Summe der Zeichenhäufigkeit nicht eine Primzahl wäre ... 9 weniger oder 1 mehr hätte es auch getan ... Dummerweise werden die falschen durch die Unfähigkeit einzelner bestraft: die Studenten ... Danke schön!
Ich sehe das Problem nicht: Wenn du die paar Zahlen nicht im Kopf rechnen magst, dann wirst du doch wohl einen PC oder Taschenrechner parat haben? Ich wüsste auch nicht, dass ein nicht glattes Ergebnis so dramatisch ist, willkommen im wirklichen Leben. schau dir mal die Numerik an, DA kommen krumme Zahlen raus...

Deine Ausdrucksweise ist meiner Meinung nach nicht angemessen.

(Und nein, die Aufgabe ist nicht von mir)

Verfasst: 31. Mai 2007 23:00
von Red*Star
RomanSoldier hat geschrieben:ich habe mal 4 verschiedene dinge ausprobiert; alleine aufgrund der ungünstigen Codierung von I,A und E kann nichts vernünftiges heraus kommen. Aber viel mehr könnte ich mich über den unfähigen Tutor aufregen, der diese Übung gemacht hat.
Im Aufgabenteil e) könnte man so leicht die mittlere Bitlänge berechnen, wenn die Summe der Zeichenhäufigkeit nicht eine Primzahl wäre ... 9 weniger oder 1 mehr hätte es auch getan ... Dummerweise werden die falschen durch die Unfähigkeit einzelner bestraft: die Studenten ... Danke schön!
Reg dich ab und reg dich lieber über was wirklich Schlimmes auf... Verletzung von Menschenrechten in sowieso, Leerfischen der Ozeane, es gibt so vieles wirklich /bedeutendes/. Wir Deutschen schaffen es wirklich, auf einem Niveau zu jammern... meine Güte.

Abgesehen davon: Primzahl. Ja und? Du kannst sie eh ausklammern, sprich wenn du keinen Taschenrechner hast (in der Klausur dann z.B.), schätzt du halt irgendwie ab: 1/109 ist ungefähr 1/100, also 0.01. Hab ich in der TGI-Klausur mit den 1/44 Hz oder was das war auch so gemacht.

Verfasst: 2. Jun 2007 16:09
von secretmojo
Bei mir kommt "ROONDDKOFND" raus mit Rest zwei Nullen :-)