¿Cómo crear un árbol Huffman desde el encabezado FFC4 (DHT) en un archivo jpeg?

votos
5

Pensé que podría solucionar esto yo mismo, pero parece que no avanzo en absoluto.

Ok, el fondo:

Necesito crear un árbol de códigos Huffman a partir de la información provista por el encabezado FFC4, DHT (Definir Tabla Huffman) en un archivo jpg. El encabezado DHT define la tabla Huffman de esta manera:

1) Una serie de 16 bytes. Cada byte define cuántos símbolos tienen un código Huffman de n cantidad de bits donde n es la posición del byte en la serie. (¿Eso tenía sentido? !!) Por ejemplo, los datos brutos en hex son:

00 01 05 01 01 01 ... 00

esto significa que:

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

2) Después de la lista de 16 bytes vienen los símbolos reales. Por ejemplo:

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

3) Combinando las dos partes vemos que son:
00 códigos con 1 bit.
01 códigos con 2 bits: así que tome el primer símbolo de la lista: 00
05 códigos con 3 bits: así que tome los 5 símbolos siguientes de la lista: 01 02 03 04 05
.. y así sucesivamente

4) Finalmente, tenemos que calcular los códigos reales de Huffman a partir de la información anterior. Si eres un genio matemático, es posible que ya te hayas dado cuenta de que estos códigos se pueden resolver simplemente incrementando un número binario con la cantidad adecuada de bits para cada nuevo código a una cierta longitud de bit. Cuando la longitud del bit aumenta, simplemente incremente el número binario y luego duplíquelo y continúe. Se hace obvio para todos los demás cuando se han extraído varios de estos árboles binarios a mano ...

5) Así que este es el código que utilicé para calcular los códigos de Huffman y almacenarlos en una matriz: (primero leí los datos en 1) y los puse en una matriz: 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;

            }

Una vez que he generado los códigos de Huffman y los he almacenado en orden, puedo agregar los símbolos a los que hacen referencia en el orden en que aparecen en 2). Esto puede no ser terriblemente elegante, pero parece funcionar al menos y crea las tablas correctas.

6) Si alguien todavía está siguiendo esto, te mereces una medalla.

7) Ahora el problema es que me gustaría almacenar esta información en un árbol binario para poder decodificar de manera eficiente los datos de la imagen jpg más adelante, en lugar de buscar en las matrices cada vez. Lamentablemente, no puedo encontrar una manera limpia y eficiente de hacerlo directamente a partir de la información provista en los encabezados de jpg como se indica arriba.
La única forma en que puedo pensar es en elaborar primero los códigos Huffman como antes, luego implementar algún método que cree nodos según sea necesario y guardar los símbolos en el lugar apropiado, utilizando los códigos como una especie de dirección. Sin embargo, esto parece una ronda de manera que también está duplicando la información que necesito, estoy seguro de que debe haber un método mucho mejor y más simple.

8) Entonces, si alguien entendiera mis divagaciones, estaría muy agradecido por algunas sugerencias. Me doy cuenta de que este es un problema muy específico, pero la información anterior puede ser útil para alguien. Todavía soy muy nuevo en esto, así que disculpe mi ignorancia, ¡el código fácil de entender es especialmente bienvenido!

Publicado el 19/03/2009 a las 16:12
fuente por usuario
En otros idiomas...                            


2 respuestas

votos
2

En cuanto a cómo implementar esto directamente, no estoy del todo seguro, ya que lleva un tiempo procesar la información, pero el algoritmo debería ser bastante sencillo si conoce los intentos . Parece desde el punto 7 que no?

Agregaré un ejemplo:

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

En este trie simple, si vamos a la izquierda asumiremos que la izquierda es un 0, la derecha es un 1. Entonces, si encuentras el patrón '00', esto corresponde con un a. El patrón '10' se corresponde con una c. Por lo general, con árboles huffman, el trie estará desequilibrado, es decir,

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

En este caso, el código de prefijo '0' corresponde a un a. El código 111 a a 'd'.

Respondida el 19/03/2009 a las 17:00
fuente por usuario

votos
0

Como dijo @wds, intenta ayudar. La idea central con la decodificación de Huffman es que los bits de la secuencia del código se deben usar para "caminar" el trie, tomando a la izquierda cuando el código tiene un 0, y un derecho para un 1, hasta que la palabra del código finalice. Entonces estarás en el nodo trie almacenando los datos de reemplazo para ese código.

Respondida el 19/03/2009 a las 17:05
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more