Praktikum7

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Beitrag von sonothar »

marlic hat geschrieben:...

Außerdem sollte doch eigentlich in jedem fall die Bitlänge gleich - da optimal - sein, oder? Hat da jemand ne idee, woran das liegt?

Mal abwarten, was "corn" dazu sagt ;)
das hab ich mir auch gedacht, und kann mir auch keinen fall ausdenken, wo sowas passieren könnte.
Aber hab mir beim Faust die Bitlänge mal ausgeben lassen. Mit "<" kommen bei mir 1041303 bits raus und mit "<=" 1041302 bits. Sehr merkwürdig...
Bild

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

Beitrag von marlic »

HolgerF hat geschrieben:Ich bin mit einer PriorityQueue noch vor der Behebung dieses Fehlers durch gewesen, also das sollte allemal gehen...
Ja ... am Encode Algorithmus hab ich ja auch nichts geändert ... und vor der Änderung des Decode Tests hatte ich ein "passed" bei den Encode Tests. :)
"Copy & Passed"

Wahlspruch der Plagiatoren

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Beitrag von EisNerd »

Wenn ich mir die advices ansehe die bei den mitgelieferten Dateien aus nem SunBestPraktice-Checker fallen, möchte ich an dieser Stelle den Veranstalter bitten, die nächsten Aufgaben vorher entsprechend zuprüfen und möglichst viele Hinweise auch umzusetzen. Meiner Erfahrung nach hilft das auch Fehler zu vermeiden.
... und morgen gehts weiter.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

hi,

vielleicht kann mir mal jemand sagen, was ich falsch mache/verstehe, weil ich bekomm das irgendwie nicht hin.

wenn ich also in der uncompress methode mit per getCodeTable() die code abhole bekomme ich schonmal das:

100001010
10110
10101
11
10000100
10111
0
100001011
1010011100
10001110
10001111
1010011111
1000110
101001101
1010011001
10100001
1000100
1000101
1010011101
10100101
1001
1010011110
10100100
100000
1000011
1010001
1010011000
101000000
101000001

ein bisschen viel, wenn das nur einen smily ergeben soll. und dann lese ich einfach per hsr bitweise ein und verfolge den baum. er gibt mir dann auch schön die symbole aus nur es sind meisten $ oder leerzeichen und am ende hab ich dann 300 von den dingern in der datei stehen. und das mit dem EOF zeichen hab ich auch noch nicht so ganz verstanden. anscheinend soll das ja die 0 sein, die oben im table steht. soll ich jetzt also einfach noch ein blatt in dem baum anlegen, wo ich über einen zweig mit nur einer 0 hinkomme und wo das zeichen char(1) gespeichert ist? weil bisher breche ich dann ab, wenn ich ein bit einlese, das den wert -1 hat.
jemand eine idee?

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

Beitrag von Gnomix »

Die Codetabelle enthält die Bitstrings fuer alle Zeichen.
Ist der Bitstring == null, existiert das Zeichen nicht im Baum.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

ja das ist mir schon klar, ich habe mir da auch nur die kodierungen von den zeichen ausgeben lassen, die nicht null waren.

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

Beitrag von Gnomix »

Das Smiley besteht aus mehreren verschiedenen Zeichen und dann steht noch ein Text darüber, der hat auch mehrere verschiedene Zeichen.
Daher sind das so viele.

Benutzeravatar
R|ng0
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 24. Dez 2006 19:17

Beitrag von R|ng0 »

banshee hat geschrieben:[...] und das mit dem EOF zeichen hab ich auch noch nicht so ganz verstanden. anscheinend soll das ja die 0 sein, die oben im table steht. soll ich jetzt also einfach noch ein blatt in dem baum anlegen, wo ich über einen zweig mit nur einer 0 hinkomme und wo das zeichen char(1) gespeichert ist? weil bisher breche ich dann ab, wenn ich ein bit einlese, das den wert -1 hat.
jemand eine idee?
Nein es ist nicht 0 (!!!), sondern in den meisten Fällen das Längste (es dem es gibt noch mehrere mit Häufigkeit 1). mehr dazu:
http://www.fachschaft.informatik.tu-dar ... 1302#61302

Du behandelst das EoF-Zeichen GENAU SO wie du jedes andere Zeichen behandelst!
So wie du Beispielweise für das A die Häufigkeit 100 hast, hast du für das EoF-Zeichen eine Häufigkeit von 1, denn es tritt ja einmal auf (dürfte auch ungefähr so in der Aufgabenstellung sein).
Also musst du, GENAU SO wie du den Huffman Baum für deine anderen Knoten erstellst, schon zu Beginn einen Knoten (bzw. ein Blatt im Wald von Knoten) für das EoF-Zeichen mit der Häufigkeit 1 haben (für das A wäre das dann ein Blatt mit der Häufigkeit 100).
Ansonsten ist der Algorithmus wie in der Folie.

PS: Ich glaube du denkst der Smiley ist das Zeichen für einen Smiley; der Smiley ist ein aus Zeichen gemalter Smiley ;)

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

Beitrag von Gnomix »

@R|ng0/banshee: Wenn man das Zeichen im Baum findet, ist es int(0). Aber der Bitstring ist natuerlich nicht umbedingt 0 sondern sicherlich länger, außer bei einer leeren Datei, oder einer Datei mit nur einem Zeichen oder n-mal einem Zeichen.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

okay, wir kommen der sache etwas näher :)

also weiß ich jetzt schonmal, dass das EOF zeichen einen der längsten codes haben muss. aber woher weiß ich jetzt welchen? in der aufgabenstellung steht ja es hat den wert 0, also hätte ich es ja in table[0] vermutet aber da steht ein kürzeres drin...

PS: wenn schon aufm schlauch, dann richtig ^^

/edit: ich seh grad, ich hab genau die gleiche ausgabe wie du in diesem topic http://www.fachschaft.informatik.tu-dar ... php?t=9102

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Doch, das stimmt schon, die Codierung des EOF-Zeichens steht in table[0].

Nochmal: Das EOF-Zeichen ist in unkomprimierter Form das Zeichen mit dem Wert 0. Also ist seine komprimierte Darstellung als Bitfolge in table[0] abgelegt. Wenn du eine Datei dekomprimierst, dann bekommst du die komprimierte Darstellung ja durch die ausgelesene Codetabelle gegeben. Wenn du selbst komprimierst, dann setzt du die Häufigkeit des unkomprimierten Zeichens 0 auf 1 und lässt deinen ganz normalen Huffman-Algorithmus das Zeichen mit in den Baum verarbeiten. Darüber erhältst du dann aus dem Huffman-Baum die Repräsentation des EOF-Zeichens.

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

Beitrag von Gnomix »

@Banshee:
Du musst darauf achten, dass du kein Bit überlist.
Also kein Bit liest ohne es auszuwerten.

Beim erstellen des Huffmanbaumes musst du erstmal alle Zeichen im Text und ihre Häfugkeiten ermitteln.
Dann setzt du noch die Häufigkeit vom Zeichen 0 auf 1 und baust dann den Huffmanbaum.
wenn du dann den Baum gebaut hast, musst du noch die Bitstrings durch traversieren ermitteln.
Naja, und dann eben die datei richtig schreiben.

Beim dekomprimieren musst du halt darauf achten, dass du den baum richtig rekonstruierst.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

jetzt hab ichs endlich geschnallt :)

ich setzt mich jetzt nochma dran und nachher komprimier ich euch 4GB DVDs in 2kb textdateien :P

Benutzeravatar
R|ng0
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 24. Dez 2006 19:17

Beitrag von R|ng0 »

banshee hat geschrieben:jetzt hab ichs endlich geschnallt :)

ich setzt mich jetzt nochma dran und nachher komprimier ich euch 4GB DVDs in 2kb textdateien :P
Die Dekomprimierung will ich dann aber auch noch sehen! ;)

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

Gnomix hat geschrieben:@Banshee:
Du musst darauf achten, dass du kein Bit überlist.
Also kein Bit liest ohne es auszuwerten.
da mache ich noch irgendwas falsch. ich finde zwar nix, wo ich ein bit überlese, aber ich kriege den gleichen crap raus wie du.
also ich mache halt einfach reader.getCodeTable(), dann erstelle ich meinen baum und dann mache ich mit reader.readBit() weiter und folge dann dem baum. und da ich bis dahin ja nix überlesen habe, müsste die ausgabe doch zumindest bis zu der stelle stimmen, an der ich was überlese.
die beiden char(0)'s werden ja von getCode Table mitgelesen nehme ich an.

Antworten

Zurück zu „Archiv“