Wie erstellt man Huffman-Baum von FFC4 (DHT) Header in JPEG-Datei?

Question

Ich dachte, ich könnte das selbst ausprobieren, aber ich scheint mich überhaupt nicht zu bewegen.

Ok, der Hintergrund:

Ich brauche einen Huffman-Baum von Codes aus den Informationen der FFC4, DHT (Define Huffman Tabelle) Header in einer jpg-Datei zur Verfügung gestellt zu erstellen. Der DHT-Header definiert die Huffman-Tabelle auf diese Weise:

1) Eine Reihe von 16 Bytes. Jedes Byte definiert, wie viele Symbole einen Huffman-Code mit einer Anzahl von n Bits haben, wobei n die Position des Bytes in der Reihe ist. (Habe das Sinn machen? !!) Zum Beispiel die Rohdaten in hex:

00 01 05 01 01 01 ... 00

bedeutet dies, dass:

Num of bits: 1 2 3 4 5 6 7 ... 16 
Num of codes: 00 01 05 01 01 01 01 ... 00 

2) Nach der Liste der 16 Bytes kommen die eigentlichen Symbole selbst. Zum Beispiel:

00 01 02 03 04 05 06 07 08 09 0A 0B

3) Die Kombination der beiden Teile, die wir sehen, dass sie sind:
00 Codes mit 1 Bit.
01 Codes mit 2 Bits: nehmen, so das erste Symbol in der Liste: 00
05 Codes mit 3 Bits: so dass die nächsten 5 Symbole von der Liste nehmen: 01 02 03 04 05
.. usw.

4) Schließlich müssen wir die tatsächlichen Huffman-Codes aus den obigen Informationen herausarbeiten. Wenn Sie ein mathematisches Genie sind, haben Sie vielleicht schon bemerkt, dass diese Codes ausgearbeitet werden können, indem einfach eine Binärzahl mit der entsprechenden Anzahl von Bits für jeden neuen Code bei einer bestimmten Bitlänge inkrementiert wird. Wenn die Bitlänge zunimmt, erhöhen Sie einfach die Binärzahl und verdoppeln Sie sie dann und machen Sie weiter. Es wird für alle anderen offensichtlich, wenn Sie eine Anzahl dieser binären Bäume von Hand herausgezogen haben ...

5) Also das ist der Code, den ich verwendet habe, um die Huffman-Codes auszuarbeiten und sie in einem Array zu speichern: (zuerst habe ich gelesen, die Daten auf 1) und legen sie sie in einem Array: dhtBitnum)

  int binaryCode = 0; 
      count = 0; 
      StringBuffer codeString = new StringBuffer();    

      //populate array with code strings 
      for (int numBits=1; numBits<=16; numBits++) { 

       //dhtBitnum contains the number of codes that have a certain number of bits 
       for (int i=1; i<=dhtBitnum[(numBits-1)]; i++) { 

        //turn the binary number into a string 
        codeString.append(Integer.toBinaryString(binaryCode)); 
        //prepend 0s until the code string is the right length 
        for(int n=codeString.length(); n<numBits; n++) { 
         codeString.insert(0, "0"); 
        } 
        //put the created Huffman code in an array 
        dhtCodes[count]=codeString.toString(); 
        binaryCode++; 
        count ++; 
        codeString.delete(0, codeString.length()); 
       } 
       binaryCode = binaryCode << 1; 

      } 

Sobald ich die Huffman-Codes und gespeichert sie in der Reihenfolge erzeugt haben, kann ich nur die Symbole hinzufügen, die sie zu beziehen, um als sie kommen in 2). Das ist vielleicht nicht besonders elegant, aber es scheint zumindest zu funktionieren und schafft die richtigen Tabellen.

6) Wenn Ihnen noch jemand folgt, verdienen Sie eine Medaille.

7) Jetzt ist das Problem, ich möchte diese Informationen in einem Binärbaum speichern, so dass ich die JPG-Bilddaten später effizient dekodieren kann, anstatt jedes Mal durch Arrays zu suchen. Leider kann ich nicht eine nette saubere und effiziente Möglichkeit finden, dies direkt von den Informationen in den jpg-Kopfzeilen wie oben bereitgestellt zu tun.
Der einzige Weg, an den ich denken kann, ist, zuerst die Huffman-Codes wie oben auszuarbeiten, dann eine Methode zu implementieren, die Knoten nach Bedarf erstellt und die Symbole an der richtigen Stelle speichert, wobei die Codes als eine Art Adresse verwendet werden.Dies scheint jedoch ein so runder Weg zu sein, der auch die Informationen kopiert, die ich brauche, ich bin mir sicher, dass es eine viel bessere und einfachere Methode geben muss.

8) Also, wenn jemand mein Geschwafel verstehen würde, wäre ich sehr dankbar für einige Vorschläge. Ich weiß, dass dies ein sehr spezifisches Problem ist, aber wenn nichts anderes die obigen Informationen hilfreich für jemanden sein könnten. Ich bin immer noch sehr neu in dieser Entschuldigung, meine Ignoranz, leicht verständlicher Code ist besonders willkommen!

Answer 1

Wie ich dies direkt implementieren kann bin ich nicht ganz sicher, da es eine Weile dauert, um die Informationen zu verarbeiten, aber der Algorithmus sollte ziemlich einfach sein, wenn Sie über tries wissen. Es scheint von Punkt 7 aus, dass Sie nicht?

ich ein Beispiel hinzufügen werden:

  ° 
     /\ 
    / \ 
     °  ° 
    /\ /\ 
    a b c d 

In dieser einfachen Trie, wenn wir links gehen wir davon ausgehen, links ein 0, rechts ein 1 ist also Wenn Sie das Muster ‚00‘ begegnen das entspricht einem a. Das Muster '10' entspricht einem c. In der Regel mit Huffman-Bäumen wird die Trie unausgeglichen sein, das heißt

 ° 
    /\ 
    a ° 
    /\ 
    b ° 
     /\ 
     c d 

In diesem Fall wird der Präfix Code '0' entspricht eine a. Der Code 111 zu einem 'd'.

Answer 2

Wie @Wds sagte, versucht Hilfe. Der Kerngedanke bei der Huffman-Decodierung besteht darin, dass die Bits der Codesequenz verwendet werden sollten, um den Trie zu "laufen", wobei er eine linke, wenn der Code eine 0 hat, und eine rechte für eine 1 verwendet, bis das Codewort endet. Dann befinden Sie sich im Trie-Knoten und speichern die Ersatzdaten für diesen Code.