Ricerca efficiente dell'albero di Huffman ricordando il percorso intrapreso

Question

Come domanda di follow-up relativa alla mia relativa al modo efficiente di conservare l'albero di huffman Mi chiedevo quale sarebbe stato il modo più rapido ed efficiente di cercare un albero binario (basato sull'output del codice Huffman) e memorizzare il percorso portato a un nodo particolare.

Questo è quello che ho attualmente:

• Aggiungi nodo radice alla coda
• mentre la coda non è vuota, elimina l'elemento dalla coda
  • controlla se è quello che stiamo cercando
    • Sì: Segui un puntatore a testa indietro al nodo principale, mentre su ogni nodo visitiamo controllando se è a sinistra o a destra e prendendone nota.
    • uscire dalla ricerca
  • accoda sinistra e nodo destro

Dato che questo è un albero di Huffman, tutte le voci che sto cercando esisteranno. Quanto sopra è una prima ricerca ampia, che è considerata la migliore per gli alberi di Huffman poiché gli elementi che si trovano nella fonte più spesso sono più in alto nell'albero per ottenere una migliore compressione, tuttavia non riesco a trovare un buon modo per tenere traccia di come siamo arrivati ??a un nodo particolare senza tornare indietro usando il puntatore head che ho inserito nel nodo.

In questo caso, sto anche ottenendo tutti i percorsi destra / sinistra in ordine inverso, ad esempio se seguiamo la testa alla radice e scopriamo che dalla radice è destra, sinistra, sinistra, veniamo a sinistra, a sinistra, a destra. o 001 in binario, quando quello che sto cercando è di ottenere 100 in modo efficiente.

È stato anche suggerito di memorizzare il percorso dalla radice al nodo come valore separato all'interno del nodo, tuttavia ciò si romperebbe se avessimo mai un albero che era più grande di quanti bit la variabile creata a tale scopo potesse contenere, e a quel punto la memorizzazione dei dati occuperebbe anche enormi quantità di memoria.

Answer 1

Crea un dizionario di valore - > bit-string, che ti darebbe la ricerca più veloce.

Se i valori hanno una dimensione nota, probabilmente puoi cavartela solo con una matrice di stringhe di bit e cercare i valori in base al loro indice.

Answer 2

Se stai decodificando i dati codificati Huffman un bit alla volta, le tue prestazioni saranno scadenti. Per quanto tu voglia evitare di utilizzare le tabelle di ricerca, questo è l'unico modo di procedere se ti preoccupi delle prestazioni. Le modalità di creazione dei codici Huffman sono univoche da sinistra a destra e si prestano perfettamente a una rapida ricerca da tavolo.