Huffman

Snakey

Hallo,
hat jemand von euch schon mal was mit Huffman gemacht

Lohnt sich das zum bilder komprimieren, bei mir kommt da hinten immer was grösseres raus als ich reinstecke.

Also Theorie:

256 verschiedene Zeichen =>kürzestes Zeichen=1 Bit, längstes = 256 Bit
Falls alle Zeichen gleichverteilt => 256*256/2*#(zuverschlüsselnde Zeichen) = Bits für alle Zeichen zusammen.

Das ist mehr als es vorher war, zumal man die codier-Infos auch noch mit reinpacken muss.

*grimmsen**

Deine Theorie ist nicht ganz richtig. Der Huffmann Algorithmus basiert auf einem binären Baum. Zum Packen werden nun die Häufigkeiten der einzelnen Zeichen ermittelt. Hier mal ein Beispiel:

Zeichenkette: AABBBCDDDD
folglich: A (2), B(3), C(1), D(4)

Jetzt beginnst du dir mit dieser Information einen binären Baum aufzubauen.
Als erstes nimmst du die Zeichen mit der geringsten Häufigkeit und erzeugst mit diesen einen Teil des Baums, indem du in der Wurzel die Summe der beiden Häufigkeiten angibst:

3
  / \
 A  C

Diesen Teilbaum nimmst du in deiner Liste mit auf und streichst A und C. In deiner Liste sind jetzt noch B, D und der Teilbaum den du gerade gebildet hast. Sowohl B als auch der vorige Teilbaum haben die Häufigkeit 3. Also werden auch die zwei zu einem Teilbaum zusammengefasst.

Diesen trägst du wieder in deiner Liste ein und streichst die den ersten Knoten und das B. Jetzt sind das D und der gerade entstandene Teilbaum in der Liste.
Wieder das gleiche Spiel:

10
   /  \
  D(0) 6(1)
      / \
     B(0)3(1)
        / \
       A(0)C(1)

Dein Baum ist fertig, denn es ist der letzte und einzige Eintrag in deiner Liste. Die Codes bilden sich daraus wie der Baum durchwandert wird. Geht man links runter kommt eine 0 geht man rechts runter eine 1. Folglich sind die Codes der einzelnen Zeichen:

A: 110
B: 10
C: 111
0

Die gepackte Zeichenkette: 1101101010101110 (16 Bits statt 80!!)

Mit diesem Baum kannst du deine Daten zurück erhalten, indem du den Baum einfach Bit für Bit durchwanderst.

Wenn du alles kapiert hast, solltest du merken, daß das häufigste Bit nicht zwingend 256Bit haben wird!!!

Für Bilder nimm lieber Algorithmen die auf der Diskreten Kosinus-Transformation beruhen. Die Ergebnisse sind dabei überwältigend!!

[ Dieser Beitrag wurde am 14.11.2002 um 16:54 Uhr von ºgrimmsenº editiert. ]

Snakey

Ok, dann probiere ich das nochmal.
Danke.

rapso

ich bekomme mit huffman wav dateien auf ca 75%
wenn ich noch ne prediction mache dann auf ca 60%

ich weiß nicht ob es etwas ähnliches wie bei sound gibt, damit man im nachhinein die datei noch kleiner "huffmanen" kann *g*

kennt jemand sowaS?

rapso->greetS();

*grimmsen**

Dann wärst du beim MPEG-Algorithmus. Dein Signal musst du in den Frequenzraum transformieren (wie bei Bildern, da aber 2-dimensional) und unwichtige Frequenzen streichen. Und dann mit normalen Packalgorithmen diese Daten packen.
Alles in allem ist das was du suchst MPEG oder MP3.
Diese Algorithmen sind aber nicht verlustlos. Das ist das Problem an den Verfahren JPEG, MPEG oder MP3.

[ Dieser Beitrag wurde am 15.11.2002 um 00:55 Uhr von ºgrimmsenº editiert. ]

rapso

sicherlich ist das nicht das was ich suche, bin auf verlustfreie kompression aus, wie eben die prediction bei wave.

MPEG MPEG ..beee.. :p

rapso->greets();