Ho pensato che avrei potuto lavorare da solo, ma non mi sembra di andare avanti.Come creare l'albero Huffman dall'intestazione FFC4 (DHT) nel file jpeg?
Ok, lo sfondo:
Ho bisogno di creare un albero di Huffman di codici dalle informazioni fornite dal FFC4, DHT (Define Huffman Table) un colpo di testa in un file jpg. L'intestazione DHT definisce la tabella di Huffman in questo modo:
1) Una serie di 16 byte. Ogni byte definisce quanti simboli hanno un codice Huffman di n quantità di bit dove n è la posizione del byte nella serie. (Ha fatto che ha alcun senso !!?) Ad esempio i dati grezzi in esadecimale è:
00 01 05 01 01 01 ... 00
ciò significa che:
Num of bits: 1 2 3 4 5 6 7 ... 16
Num of codes: 00 01 05 01 01 01 01 ... 00
2) Dopo l'elenco di 16 byte vengono gli stessi simboli effettivi. Per esempio:
00 01 02 03 04 05 06 07 08 09 0A 0B
3) Combinando le due parti si vede che loro sono:
00 codici con 1 bit.
01 codici con 2 bit: in modo da prendere il primo simbolo dalla lista: 00
05 codici con 3 bit: in modo da prendere i prossimi 5 simboli dalla lista: 01 02 03 04 05
.. e così via
4) Infine dobbiamo elaborare i codici Huffman effettivi dalle informazioni di cui sopra. Se sei un genio della matematica, potresti aver già notato che questi codici possono essere risolti semplicemente aumentando un numero binario con il numero appropriato di bit per ogni nuovo codice a una certa lunghezza di bit. Quando la lunghezza del bit aumenta, basta incrementare il numero binario e quindi raddoppiarlo e proseguire. Diventa ovvio per tutti gli altri quando hai estratto un numero di questi alberi binari a mano ...
5) Quindi questo è il codice che ho usato per elaborare i codici Huffman e memorizzarli in un array: (prima ho letto i dati a 1) e metterlo in un 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;
}
volta ho generato i codici di Huffman e memorizzate in ordine, posso solo aggiungere i simboli che si riferiscono in ordine come arrivano in 2). Questo potrebbe non essere terribilmente elegante ma sembra funzionare almeno e crea le tabelle corrette.
6) Se qualcuno lo sta ancora seguendo, meriti una medaglia.
7) Ora il problema è che mi piacerebbe memorizzare queste informazioni in un albero binario in modo da poter decodificare in modo efficiente i dati delle immagini jpg in seguito, piuttosto che cercare ogni volta gli array. Purtroppo non riesco a capire un modo pulito ed efficiente per farlo direttamente dalle informazioni fornite nelle intestazioni jpg come sopra.
L'unico modo che posso pensare è elaborare i codici Huffman come sopra prima, quindi implementare un metodo che crea nodi come necessario e salva i simboli nella posizione appropriata, usando i codici come un indirizzo di sorta.Tuttavia questo sembra un modo tondo che duplica anche le informazioni di cui ho bisogno, sono sicuro che ci deve essere un metodo molto migliore e più semplice.
8) Quindi se qualcuno capisse le mie divagazioni, sarei molto grato per alcuni suggerimenti. Mi rendo conto che questo è un problema molto specifico, ma se non altro le informazioni sopra potrebbero rivelarsi utili a qualcuno. Sono ancora molto nuovo in questo, quindi scusate la mia ignoranza, il codice facile da capire è particolarmente benvenuto!
Questo mi ha aiutato molto. Grazie amico, sei il re: D – MrD