H6.9 c) und d)

brotkasten
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 17. Jan 2005 08:20

H6.9 c) und d)

Beitrag 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

brotkasten
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 17. Jan 2005 08:20

mhhhpf

Beitrag 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 :?

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag von giftnudel »

Dekodier halt das was du kannst und schreib hin was du denkst das rauskommt.

brotkasten
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 17. Jan 2005 08:20

Beitrag 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")

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag 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...

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag 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 ;)
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag 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.

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag 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

ykaerflila
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 9. Mai 2006 22:01
Wohnort: Mainz
Kontaktdaten:

Beitrag von ykaerflila »

Soll denn überhaupt irgendetwas sinnvolles rauskommen?! Hier kommt nonsense raus...
icq# 117752728
email: 7pinacoladas@gmx.net

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag 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.
"Copy & Passed"

Wahlspruch der Plagiatoren

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag 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!

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag 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.
Zuletzt geändert von marlic am 31. Mai 2007 21:40, insgesamt 1-mal geändert.
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Beitrag 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)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag 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.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Beitrag von secretmojo »

Bei mir kommt "ROONDDKOFND" raus mit Rest zwei Nullen :-)

Antworten

Zurück zu „Archiv“