Huffman

[F0rris]

Hallo zusammen,

ich beschäftige mich grade mit dem Huffman Algorythmus und das kratz grade irgendwie an meinem Selbstvertrauen. Mir ist bewusst das es fertig class dafür gibt und ich davon den Code abkupfern könnte aber das will ich eigentlich nicht.

Bis jetzt bin ich soweit, dass ich mir den string zerlege, Zähle und nach Häufigkeit sotiere. Die Aktuelle ausgabe sieht so aus:

Char    Count   frequ   Bytecode    
a       9       0,36    
b       5       0,20    
c       4       0,16    
d       3       0,12    
e       2       0,08    
f       1       0,04    
g       1       0,04    

Char Sum     25
Value 1 Char 0,04

Leider stehe ich grade etwas auf der Leitung, wie ich den tree Aufbaue, um den Bytecode für eine hohe Komprimierung erzeuge.

Unter http://wwwlehre.dhbw-stuttgart.de/~sto/public/stud_arb/huffman/huffman.html habe ich einen Huffman rechner gefunden jedoch, verstehe ich wie gesagt den aufbau nicht. Nach welchen Kritieren muss ich den Tree aufbauen, hat da vielleicht jemand einen Tipp für mich?

Greez F0rris

 

[Steiner_B]

Hallo,

Look at Google, erster Link. Wäre aber auch selbst zu finden gewesen.

 

[guenter024]

Habe hier was interessantes gefunden:
http://www.inf.fh-flensburg.de/lang/algorithmen/code/huffman/huffman.htm

Ich verstehe es zwar auf die schnelle auch nur zum Teil, aber ich habe soviel an wichtiger Information herausgelesen:
Du musst nun praktisch für jedes vorkommende Symbol einen Knoten erzeugen und dann immer die beiden Knoten mit den minimalsten Markierungen miteinander verbinden.
Damit erhältst du dann automatisch den Baum mit den Markierungen:

f + g,
dann (f+g) + e,
dann ((f + g) + e) + d,
dann b + c,
dann (((f + g) + e) + d) + (b + c),
zuletzt ((((f + g) + e) + d) + (b + c)) + a

Daraus kannst du dann den Code erzeugen.

Aber darf ich fragen, wofür du das benötigst - und gehört das hier ins php-Forum?

 

[guenter024]

Hallo,

Look at Google, erster Link. Wäre aber auch selbst zu finden gewesen.

... ja, den habe ich auch gleich gefunden...

 

[F0rris]

Ich schreibs in PHP, deswegen habe ich es mal hier postet. Die Aussage "[...]Knoten mit den minimalsten Markierungen[...]" waren der Perfekte Denkanstoß, danke .

Ich Skripte grade aus langeweile verschiedenste sachen. Nach DTaus und SEPA wollte ich mich mal an einen Algorythmus heran wagen. Möchte ich gerne in meine Bewerbung einfließen lassen, als Beispiel code.