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. ;)
EyDu hat geschrieben: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.
Ohne Input kein Output.