Effiziente Baumsuche Huffman während Remembering Weg beschritten

Question

Als Frage folgt in Bezug auf meine Frage in Bezug auf effiziente Art und Weise Huffman Baums zu speichern ich habe mich gefragt, was der schnellste und effizienteste Weg sein würde, einen binären Baum des Suchens (bezogen auf dem Huffman-Kodierung Ausgang) und Speichern Sie den Pfad zu einem bestimmten Knoten gemacht.

Das ist, was ich derzeit haben:

• Fügen Sie Root-Knoten in der Warteschlange
• während Warteschlange nicht leer ist, pop Artikel aus Warteschlange
  • überprüfen, ob es ist, was wir suchen
    • ja: Folgen Sie einen Kopf auf den Wurzelknoten-Zeiger zurück, während auf jedem Knoten besuchen wir überprüfen, ob es an der linken oder rechten Seite und macht eine Notiz davon.
    • Ausbrechen der Suche
  • enqueue linken und rechten Knoten

Da dies ein Huffman-Baum ist, alle Einträge, die ich suche existieren. Das Vorstehende ist eine Breitensuche, die das Beste für Huffman Bäume da Elemente in Betracht gezogen wird, die häufiger in der Quelle sind in dem Baum sind höher ein bessere Kompression zu bekommen, aber ich kann nicht einen guten Weg finden, um im Auge zu behalten wie wir zu einem bestimmten Knoten bekamen ohne Rückzieher des Kopfzeiger mit mir in den Knoten setzen.

In diesem Fall bin ich auch all die rechten / linken Pfaden in umgekehrter Reihenfolge, zum Beispiel immer, wenn wir den Kopf in die Wurzel folgen, und wir erfahren, dass von der Wurzel es richtig ist, links, links, wir gehen nach links, links, rechts. oder 001 in binärer, wenn das, was ich suche ist 100 auf effiziente Art und Weise zu erhalten.

Das Speichern der Pfad von der Wurzel zu dem Knoten als separater Wert innerhalb des Knotens wurde auch vorgeschlagen, jedoch würde diese brechen, wenn wir jemals einen Baum hatte, die größer als jedoch viele Bits war die Variable, die wir zu diesem Zweck erstellt halten konnte, und an diesem Punkt die Speicherung der Daten würden auch große Mengen an Speicherplatz.

Answer 1

ein Wörterbuch des Wertes erstellen. -> Bit-String, das würden Sie die schnellste Lookup

Wenn die Werte eine bekannte Größe sind, können Sie wahrscheinlich mit nur einer Reihe von Bit-Strings erhalten, indem die Werte und durch ihren Index nachschlagen.

Answer 2

Wenn Sie Decodierung Huffman-codierte Daten ein Bit zu einer Zeit, wird Ihre Leistung schlecht sein. So viel wie Sie Lookup-Tabellen vermeiden möchten, verwenden, das ist der einzige Weg zu gehen, wenn Sie über die Leistung kümmern. Die Art und Weise Huffman-Codes erstellt werden, werden sie von links nach rechts einzigartig und eignen sich perfekt zu einem schnellen Nachschlagen in einer Tabelle.