Ricostruzione di un albero di huffman utilizzando le informazioni minime nell'intestazione

Ci sono 2 problemi separati, memorizza la topografia e assegna i nodi foglia

L'assegnazione dei nodi foglia può essere effettuata memorizzando i caratteri in un ordine predefinito in modo che possa essere estratto come necessario.

La memorizzazione della topografia può essere eseguita avendo un vettore bit con 2 bit per nodo principale nel livello precedente dove 1 rappresenta un nodo composto e 0 rappresenta un nodo foglia

quindi prima c'è 1 bit per la radice che è 1 e i prossimi 2 bit rappresenteranno il livello successivo in basso

per costruire l'albero usando l'impostazione node{char value; node* left, right;} sarà:

char[] chars;//prefill with the other array
int charIndex = 0;

node root;
vector<node*> toBuild(root);

while(!toBuild.empty()){
    node n = toBuild.popFront();
    bool bit = grabBit();
    if(bit){
        n.left = new node;
        toBuild.pushBack(n.left);
    }else
        n.value = chars[charIndex++];
    bit = grabBit();
    if(bit){
        n.right = new node;
        toBuild.pushBack(n.left);
    }else
        n.value = chars[charIndex++];
}
return root;

Questo è 2 * n bit nella topografia più la permutazione che è O (log n!) al minimo.

Innanzitutto, come discusso nei commenti, dovresti sbarazzarti delle frequenze poiché hai solo bisogno di loro per creare l'albero, non per riprodurre i codici per la decodifica. Nel tuo programma, ma non sul disco, la struttura ad albero potrebbe apparire come questa (notare l'assenza di frequenze):

struct Node {
  char value; // only used for leaf nodes
  // leaf nodes have BOTH child pointers NULL
  struct Node *left, *right;
}

Penso che il seguente schema dovrebbe permettere di riprodurre l'albero (sebbene non le frequenze) usando al massimo 2n * k bit per alfabeti in cui ogni carattere prende k bit (quindi k < = log2 n < = k + 1):

• Assegna indici consecutivi arbitrari a tutti i nodi interni dell'albero di Huffman.
• Per ogni carattere, scrivi l'indice del nodo genitore.
• Ordina i nodi interni secondo i loro indici. Per ogni nodo tranne la radice, scrivi l'indice del suo nodo genitore. Per il nodo radice, rendi il suo indice "genitore" uguale a stesso .

Dato che ci sono al massimo n-1 nodi interni, gli indici dei nodi si adattano ciascuno a k bit. Quindi i record del nodo interno più i record di caratteri, arriviamo a poco meno di 2n * k bit. La decodifica è relativamente semplice: prima leggi i record di carattere k, crea i nodi interni corrispondenti e aggiungi iterativamente i nodi scoperti di recente (quelli referenziati da altri nodi interni ma non ancora creati). È possibile riconoscere il nodo radice tramite il riferimento automatico.

Si noti che ciò richiederebbe una diversa struttura ad albero, una con riferimenti padre invece di riferimenti figlio e un flag per distinguere i nodi foglia (in memoria, è possibile utilizzare NULL per% root% co_de) Se questo rende più facile generare i codici, puoi invertire i puntatori genitore, cioè trasformare questa rappresentazione nella bella struttura top-down sopra menzionata.

Avvertenza: presumo che k sia noto a entrambe le parti (in caso contrario, un singolo byte in più dovrebbe essere sufficiente per qualsiasi applicazione pratica). Presumo anche un alfabeto di vettori bit a dimensione fissa, ma penso che sia il caso in quasi tutte le applicazioni (e se non è vero, è possibile aggiungere i metadati e andarsene via piuttosto bene).

Non è necessario memorizzare le frequenze effettive di ciascun simbolo o la topologia esatta dell'albero di Huffman. Hai solo bisogno di memorizzare abbastanza informazioni per codificare il livello sull'albero in cui si trova ogni simbolo.

È possibile modificare un albero di Huffman mescolando simboli e nodi interni delle filiali sullo stesso livello senza modificare l'efficienza di codifica dell'albero. Quindi ha senso mappare il tuo particolare albero di huffman alla sua versione canonica, quindi devi solo specificare quale degli alberi canonici stai usando. Suggerisco, partendo dall'alto e scendendo, spingere tutti i simboli a sinistra fino in fondo, quindi ordinali in ordine crescente.

Una volta che hai reso canonico l'albero, devi effettivamente codificarlo.

Se limiti la profondità dell'albero a 32 livelli, puoi semplicemente codificare una matrice da 256 a 5 bit (160 byte) dando il livello dell'albero huffman di ciascun simbolo.

Puoi avvicinarti al minimo teorico delle informazioni della dimensione di codifica di te codificare aritmeticamente il sottoinsieme di simboli disponibili ad ogni livello, ma immagino che dal momento che stai usando i codici di Huffman non sei ancora pronto per la codifica aritmetica.