Huffmanncodierung| Einsparung in % |
| 20.01.2017, 16:32 | Auf diesen Beitrag antworten » | ||
| minf0185 | Huffmanncodierung| Einsparung in % Meine Frage: Gegeben: Zeichenfolge: D B A E C D E A B D F A C E A D D E C B E A D F C G D E A D E B C D E Ermitteln Sie für den aufgeführten Text eine Code-Tabelle nach dem HuffmanVerfahren durch Bestimmung des Code-Baumes. Komprimieren Sie die ersten fünf (5) Zeichen des Textes mit der von Ihnen bestimmten Code-Tabelle. Sie haben nun die Aufgabe einen Text, bestehend aus 150.000 Zeichen, mit dem von Ihnen ermittelten Code zu kodieren. Wieviel Platz werden Sie in etwa einsparen, wenn Sie das Ergebnis mit einem Fixed Length Code minimaler Länge kodieren? (ca. Länge Huffmann, Länge Fixed Length, Einsparung in %) Meine Ideen: A = 6, B = 4, C=5, D = 9, E = 8, F=2, G=1, Spaces = 34 Baum Siehe Anhang A = 1111, B = 1001, C=1110, D = 110, E = 101, F=10001, G=10000, Spaces = 0 "Komprimieren Sie die ersten fünf (5) Zeichen des Textes mit der von Ihnen bestimmten Code-Tabelle." Ist damit "D B A" gemeint? "D B A" = 1100100101111 Wie berechne ich die Ersparnis? [ 1 - (neue Codelänge) / (alte Codelänge)] ? Doch was ist die Alte Codelänge? Ist die neue Codelänge die Länge des Zeichens mit der kleinsten Wahrscheinlichkeit? G kommt einmal dran (G=10000) == Neue Codelänge = 5? |
||
|
|
|||
| 20.01.2017, 17:42 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Ich habe die Zeichen jetzt nicht nachgezählt, aber dein Baum sieht gut aus. Bei fixed length ist denke ich gemeint, dass jedes Zeichen die selbe Länge hat (in ASCII wären das 8 Bit). Hier etwa: A = 000, B=001, C=010, ..., Space=111 (Reihenfolge ist willkürlich). Die Länge eines Zeichens wäre also 3 Bit. Mit dem Huffman Code hättest du (34*1 (Space) + 6*4(A) + ... + 1*5 (G))/69 |
||
| 20.01.2017, 18:15 | Auf diesen Beitrag antworten » | ||
| minf0185 | Sie haben nun die Aufgabe einen Text, bestehend aus 150.000 Zeichen, mit dem von Ihnen ermittelten Code zu kodieren. Wieviel Platz werden Sie in etwa einsparen, wenn Sie das Ergebnis mit einem Fixed Length Code minimaler Länge kodieren? (ca. Länge Huffmann, Länge Fixed Length, Einsparung in %) 150000 Zeichen Ich habe 8 Zeichen also müsste ich bei fixed bit ja eine länge von (8-1 in Bits => 111 => Länge = 3) nehmen also wäre das ersparnis 1-[150000*3 Bit ]/[150000*8 Bit] 1-[3/8] = 0,625 62,5% Ersparnis sollte richtig sein oder? |
||
| 20.01.2017, 18:48 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | "mit dem von Ihnen ermittelten Code zu kodieren" So wie ich das sehe, sollst du einen 3Bit/Zeichen Code mit dem Huffman Code vergleichen. |
||
| Anzeige | |||
|
|
|||
| 20.01.2017, 18:56 | Auf diesen Beitrag antworten » | ||
| minf0185 |
wie würdest du vorher? meinst du jetzt 01000001 = A 1111 = A oder meinst du die maximal länge von meinen codebaum ist die länge des seltensten Zeichen = 10000 = G => Länge = 5 Also hätte ich eine minimale Einsparung von 1 - 5/8 = 37,5% |
||
| 20.01.2017, 19:03 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Bei fixed length hast du 3Bit/Zeichen, also insgesamt 150000*3Bit = 450000 Bit. Mit Huffman (unter der Annahme, dass die Buchstabenverteilung im langen Text der aus dem Auszug entspricht): 150000 * 1/69 * (6*4(=A) + 4*4(=B) + 5*4(=C) + 9*3(=D) + 8*3(=E) + 2*5(=F) + 1*5(=G) + 34*1(=Space)) = 347826.0869 Huffman braucht also etwa 7/9 von 3Bit Kodierung. |
||
| 20.01.2017, 19:07 | Auf diesen Beitrag antworten » | ||
| minf0185 | danke dir! |
||
|
|