Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
huffman-bitstring-codierung
ok, der titel sagts ja fast schon:
ich hab keine idee :wand: wie man den bitstring codiert, den man nach dem huffman-algorithmus erhält. kann mir das bitte jemand erklären?
naja zuerst musst halt den Baum codieren (O als 1 und [] als 0), danach musst alle Buchstaben codieren in genau der Reihenfolge, wie sie im Baum verwendet werden, also z.B. A = 000, B = 001 usw.
ich meine irgendwo gelesen zu haben, dass man wie folgt agiert:
zuerst baum umgestalten, dass dieser mit einem hang zu einer seite expandiert. dann werden die zeichen nach ihrer bitlänge angeordnet. was der tiefe im baum entspricht.
das beispiel
a : 1
b : 010
c : 011
d : 001
e : 0000
f : 0001
ergibt:
ein zeichen der länge 1: 1a
kein zeichen der länge 2: 0
3 zeichen der länge 3: 3cbd
2 zeichen der länge 4: 2fe
die reihenfolge (z.b. cbd) ergibt sich aus einer < oder > relation, welche von der formatierung des baumes abhängt (linker oder rechter ast mit 0 bzw 1 codiert, von links oder rechts auffüllen)
ergebnisstring: 1a03cbd2fe
diesen dann noch entsprechend codieren:
z.b.
0 = 00
…
3 = 11
a = 000
b = 001
…
oder mit ascii-codes
damit kann man nun entgegen des expansionshanges die ebenen des baumes wieder auffüllen.
aber wie schon erwähnt, stammt das nicht aus einer übung. offeriert aber eine alternative zum nichtwissen.
schon wesentlich besser, danke 