Huffman Encoding, Speichern von Codes und Schreiben von Binärdateien in C

Question

Ich habe ein Problem mit der Codierung einer Textdatei mit Huffman. Lassen Sie uns sagen, dass die Linie zu codieren, wie die folgende ist:

AAAABBBCCAABBCCDFF 

So ist die Frequenz Tabelle wie folgt aus:

A:6 
B:5 
C:4 
D:1 
F:2 

So baue ich einen Baum, ist die Struktur wie folgt aus:

typedef struct node { 
    struct node *left; 
    struct node *right; 
    unsigned char character; 
    unsigned int flag; //needed for nodes with no value in Huffman-tree 
    unsigned int occurences; 
} node; 

weiß, dass ich die Codes sein sollte:

A: 10 
B: 11 
C: 01 
D: 000 
F: 001 

Jetzt möchte ich diese Codes von meinem Baum bekommen, wie kann ich das leicht machen?

Zweitens möchte ich diese Codes speichern, damit ich die Codes leicht nachschlagen und sie in eine Binärdatei schreiben kann.

Wie kann ich diese Codes speichern und zum Schreiben, wie kann ich einzelne (oder 2 oder 3) Bits in eine Binärdatei schreiben, weil ich weiß, C will Bytes.

ich es so schreiben will (Codes für Byte und letzten Byte sortiert sind nur 7 Bits)

10101010 11111101 01101011 11010100 0001001 (only 7 bits) 

Answer 1

Im Folgenden ist ein Beispiel ein Bit-String-codiert zu einer Serie von hexadezimal in einem konvertieren Textdatei. Die sBoolText-Zeichenfolge wurde mit '0' oder '1' gefüllt und muss gefüllt werden, indem '0' für das letzte Byte abgeschlossen wird.

In Ihrem Fall wird "AAAABBBCCAABBCCDFF" als 101010101111 ... 001001 codiert und erzeugt einen Bitstring "101010101111 ... 001001", der mit "0" gefüllt ist.

Dies ist nicht genau das, was Sie brauchen, aber Sie können fputc() anstelle von fprintf() verwenden.

void BoolToHexFile(FILE *foutText,char *sBoolText) 
{ 
    int i,j,len,res; 

    len = strlen(sBoolText); 
    for(i=0;i<len;i+=8) { 
     res = 0; 
     // build one byte with 8bits as characters 
     for(j=0;j<8;j++) { 
      res *= 2; 
      if (sBoolText[i+j]=='1') res++; 
     } 
     // add a NewLine every 16 bytes 
     if ((i % 128) == 0) fprintf(foutText,"\n"); 
     // store the byte as 2 hexa-digits 
     fprintf(foutText,"%02X ",res); 
    } 
}