Ich versuche, einen binären Suffix-Code für einen gegebenen Satz von Zeichen mit ihren Wahrscheinlichkeiten effizient zu konstruieren (d. h. einen Satz von Wörtern, von denen keiner ein Suffix eines anderen ist).
Meine Grundidee besteht darin, einen Präfix-Code mit einer Implementierung des Huffman-Algorithmus zu konstruieren. Durch Umkehren der Codewörter erhalte ich einen Suffix-freien Code. Während diese Lösung funktioniert, scheint es nicht optimal zu sein, weil ich Codewörter mit variabler Länge umkehren muss (daher brauche ich eine Nachschlagetabelle kombiniert mit Bit-Shifts).
Gibt es eine Möglichkeit, den Huffman-Algorithmus zu modifizieren, um einen Suffix-Code effizienter zu erstellen?
Ich würde den HuffmanNode als
implementieren %Vor% Diese Klasse repräsentiert einen einzelnen Knoten in einem Huffman-Baum.
Es hat bequeme Methoden, um alle Blätter von einem (Unter-) Baum zu erhalten.
Sie können dann einfach den Baum erstellen:
%Vor%Durch Ändern der Methode, die den Code erstellt (z. B. die nächste Ziffer voranzustellen, anstatt sie anzuhängen), können Sie die erzeugten Codes ändern.
Tags und Links compression huffman-code