Pensé que podría solucionar este problema yo mismo, pero parece que no avanzo en absoluto.¿Cómo crear un árbol Huffman desde el encabezado FFC4 (DHT) en un archivo jpeg?
Ok, el fondo:
Necesito crear un árbol de Huffman de los códigos de la información proporcionada por el FFC4, DHT (Definir Huffman tabla) encabezado 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. (DID que tiene sentido !!?) Por ejemplo los datos en bruto en hexadecimal es:
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) La combinación de las dos partes, vemos que su son:
00 códigos con 1 bit.
01 códigos con 2 bits: a fin de tomar el primer símbolo de la lista: 00
05 códigos de 3 bits: a fin de tomar los próximos 5 símbolos 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 Huffman y almacenarlos en una matriz: (primero leí los datos a 1) y lo puso 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 haya generado los códigos de Huffman y los almacena en orden, sólo puedo añadir los símbolos que se refieren en el orden que vienen 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, usted merece 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 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 se me ocurre es resolviendo primero los códigos Huffman como antes, y luego implementando algún método que crea nodos según sea necesario y guarda los símbolos en el lugar apropiado, usando 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) Así que si alguien entendió 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!
Esto me ayudó mucho. Gracias, hombre, eres el rey: D – MrD