Canonical Huffman Code

[BeRsErKeR]

Hi ich bräuchte mal eure Hilfe. Ich möchte aus Werten und ihrer Häufigkeit einen CHC generieren und zwar in der Form, dass ich aus den Längen (in Bits) der Codes über folgenden Pseudocode wieder die korrekte Zuordnung schaffen kann:

Code: Alles auswählen

code = 0
sort list of symbols by encoded bit length and by symbol index afterwards
while symbols remaining
	if code = 0
		assign code (0) to symbol with highest probability
		last bit length = lowest found bit length
	else
		code = (code + 1) << (current bit length - last bit length)
		assign code to first symbol that was not processed with this length

Mein Hauptproblem ist festzustellen wieviele Bits ich am besten zum Kodieren nutze. Als Beispiel:

Ich habe 8 verschiedene Symbole, mit verschiedenen Häufigkeiten. Eine mögliche Kodierung wäre nun:

Code: Alles auswählen

symbol0	00
symbol1	01
symbol2	10
symbol3	1100
symbol4	1101
symbol5	1110
symbol6	11110
symbol7	11111

Also maximal 5 Bits. Die Frage ist ob man das ganze auch zweckmäßig mit maximal 4 Bits kodieren kann (also das Beispiel unten tut dies ja, aber ich brauch halt was allgemeingültiges, nicht nur für 8 Symbole) und wie ich das allgemein aus der Menge der unterschiedlichen Werte ableiten könnte.


Zum Beispiel könnte ich in 4 Bits bequem 8 Werte unterbringen:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Das lohnt sich aber z.B. nur wenn die beiden ersten Symbole sehr viel häufiger auftreten. Gibt es da Formeln, Faustregeln oder ähnliches für?


Wikipedia bietet da Pseudocode für, allerdings ist mir nicht ganz klar was "base D" hier bedeutet und mein Test mit D=4 brachte einen sehr schlechten Baum und zudem auch einen, der nicht zum obigen Pseudocode kompatibel ist. Genauer brachte er die obigen Codes (mit bis zu 5 Bits) hervor, allerdings noch in anderer Ausprägung, da das einsortieren der Zusammenschlüsse teilweise auch dazwischen erfolgt und somit die Reihenfolge nicht mehr so ist wie vom Dekomprimierer erwartet (siehe Pseudocode oben).

[LONy]

Hi,
beim deutschen Wikipedia Artikel ist es find ich recht anschaulich erklärt:
http://de.wikipedia.org/wiki/Shannon-Fano-Kodierung

1. Erstelle einen Wald mit einem Baum für jedes Zeichen. Jeder dieser Bäume enthält nur einen einzigen Knoten: das Zeichen. Schreibe die Häufigkeit an die Kante.
2. Suche die beiden Bäume, die die geringste Häufigkeit haben. Fasse beide Bäume zusammen, indem sie die Teilbäume einer neuen Wurzel werden. Benutze die Summe der Häufigkeiten dieses neuen Baumes zur weiteren Analyse.
3. Wiederhole Schritt 2 so oft, bis nur noch ein Baum übrig ist.

Man muss halt vorher wissen, mit welcher Wahrscheinlichkeit welches Symbol auftritt.

[BeRsErKeR]

Naja ich dachte halt es geht ohne Baum, wenn die Einschränkung "canonical" gilt. Hab es jetzt auch erstmal mit einem Baum gemacht. Danke trotzdem.

[EyDu]

base D wird wohl die Basis der Kodierung sein, in diesem Fall also D=2. Viel mehr Zustände sind bei einem Bit auch nicht drin ^^ Ich habe mir den letzten Algorithmus nicht genau angeschaut, sieht für mich aber wie die übliche Huffman-Kodierung aus, vielleicht steckt da noch irgendwo etwas im Detail. Wenn du aber eh schon einen Baum hast, dann lohnt sich weiterer Aufwand wahrscheinlich nicht. Die kanonische Variante ist ja nur eine Optimierung um das Codebuch zu verkleinern.

[BeRsErKeR]

Die kanonische Variante ist ja nur eine Optimierung um das Codebuch zu verkleinern.

Ja und man braucht zum Dekodieren halt keinen Baum, da man aus den Längen einfach die Codes generieren kann und über ein Mapping von Code zu Wert einfach dekodieren kann. Ich hatte gehofft dass auch das Kodieren ohne Baum möglich ist. Hab nun halt nen Pseudo-Baum, der eigentlich nur kurz zur Generierung der Baumtiefen genutzt wird und dann gleich wieder weggeworfen wird. Die Tiefen entsprechen ja den Bitlängen. Ich achte beim Einfügen in den Baum auf gleicher Tiefe einfach darauf, dass Knoten mit Werten links von Verbundknoten eingefügt werden und bei zwei Verbundknoten jener weiter links ist, der die Symbole mit niedigerem Index enthält. Damit gewährleiste ich dann den kanonischen Aufbau. Also es läuft nun super. Performancekritisch wird das wohl nicht daher lass ich das wohl so. ;) Aber danke für die Mühen.

[EyDu]

Du hast da etwas falsch verstanden: der Code wird lediglich so umgestellt, dass das Codebuch nur mit den Codelängen erzeugt werden kann. Die Längen der Codewörter bleiben die selben, nur die Bits wurden angepasst. Zum Dekodieren brauchst du weiterhin einen vollständigen Baum. Da du Bit für Bit lesen musst, entscheidet sich für jedes einzelne Bit ob das Wort noch weiter geht oder ob es vollständig ist. Es gibt keine magische Funktion, mit der du ein Codewort sofort auslesen könntest.

[BeRsErKeR]

Ich glaub du hast mich falsch verstanden. Mir ist das schon klar. Ich meinte mit "kein Baum", dass man beim Dekodieren keinen Baum (mit Knoten usw) anlegen muss, sondern die Bitlängen ausreichen um die Codes für die einzelnen Werte zu generieren. Dass diese Bitlängen prinzipiell den Baum repräsentieren ist mir schon klar, aber ich kann halt z.B. einen Baum mit 20 Elementen und 4 Bit pro Bitlänge bequem in 80 Bit speichern und brauch keinen Baum konstruieren. ;)

Da du Bit für Bit lesen musst, entscheidet sich für jedes einzelne Bit ob das Wort noch weiter geht oder ob es vollständig ist. Es gibt keine magische Funktion, mit der du ein Codewort sofort auslesen könntest.

Da gibt es 2 recht einfache Varianten. Entweder du peekst in einer Schleife von minlen bis maxlen jeweils die Werte und guckst im Lookup ob sowohl Wert als auch Länge stimmen (Länge ist eigentlich nur bei Werten mit Länge minlen entscheidend beim kanonischen Tree, da diese mit einer 0 beginnen können) oder du baust dir eine Lookup in der du bei einem Peek mit maxlen in jedem Fall den richtigen Wert erhälst. Geht schneller aber man muss je nach maximaler Bitlänge viele Werte in der LookupTable speichern. Nach dem Peek seekst du einfach im Bitstream um die Länge des Matches weiter (darum kein Read sondern Peek). ;)

Als Beispiel für die zweite Variante mit dem Beispiel von oben:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Zugehörige Lookup:

Code: Alles auswählen

[0] -> symbol0
[1] -> symbol0
[2] -> symbol0
[3] -> symbol0
[4] -> symbol1
[5] -> symbol1
[6] -> symbol1
[7] -> symbol1
[8] -> symbol2
[9] -> symbol2
[10] -> symbol3
[11] -> symbol3
[12] -> symbol4
[13] -> symbol5
[14] -> symbol6
[15] -> symbol7

Wenn du jetzt immer maxlen (4) Bits liest dann erhälst du direkt das richtige Symbol. Dann musst du nur gucken wie die wirkliche kodierte Länge des Symbols ist und die Position im Bitstream entsprechend anpassen. Die Lookup kann man recht simpel über Bitgeschubse in einer Schleife bauen. Ich gehe aber den anderen Weg mit dem Peek in der Schleife. Da für meine Zwecke maximal 16 Bit für die Codelänge reichen, sehe ich das nicht so kritisch. Ich steh nicht so auf riesige dynamische Lookup-Tabellen. :D

Aber um auf deine Aussage mit der magischen Funktion zurück zu kommen. Damit kann man das Codewort direkt aus dem Stream lesen. Man muss halt danach nur nochmal seeken falls das gefundene Symbol nicht die Maximallänge aufweist.


Mein Huffman Tree speichert intern nur ein Dictionary mit dem Code als Key und der Node als Value. Ob die Nodes untereinander "verbunden" sind ist eigentlich unwichtig. Beim Dekodieren ist es sowieso unnötig, beim Schreiben ist es kurzzeitig mal nötig wobei das sicher auch ohne ginge. Ich brauche die Knotenverbindungen eigentlich nur um festzustellen wieviele Ebenen über einer ValueNode liegen und berechne nach dem temporären Baumaufbau darüber die Tiefen bzw. Bitlängen. Die kann ich dann speichern. Über das genannte Mapping kann ich sowohl die Codes für bestimmte Symbole ermitteln als auch aus einem Bitstream die Werte dekodieren. Und mehr braucht man zum Kodieren und Dekodieren nicht. ;)

Prinzipiell sind Nodes größtenteils Ablagen für Werte wie Tiefe oder Symbolwert.