Pomyślałem, że sam mógłbym sobie z tym poradzić, ale wydaje mi się, że wcale nie posuwam się naprzód.Jak utworzyć drzewo Huffman z nagłówka FFC4 (DHT) w pliku jpeg?
Ok, background:
muszę utworzyć drzewa Huffman kodów z informacji dostarczonych przez FFC4, DHT (Definiuj Huffman tabela) nagłówka w pliku jpg. Nagłówek DHT definiuje tabelę Huffmana w następujący sposób:
1) Seria 16 bajtów. Każdy bajt określa, ile symboli ma kod Huffmana liczby bitów, gdzie n jest pozycją bajtu w serii. (Czy to ma jakiś sens? !!) Na przykład surowe dane w hex jest:
00 01 05 01 01 01 ... 00
oznacza to, że:
Num of bits: 1 2 3 4 5 6 7 ... 16
Num of codes: 00 01 05 01 01 01 01 ... 00
2) Po liście 16 bajtów przychodzą same rzeczywiste symbole. Na przykład:
00 01 02 03 04 05 06 07 08 09 0A 0B
3) połączenie dwóch części widzimy, że ich są:
00 kody o 1 bit.
01 kody o 2 bity SO się pierwszy symbol z listy: 00
05 kodów z 3 bitów: tak się następne 5 symboli z listy: 01 02 03 04 05
.. itd
4) Na koniec musimy obliczyć aktualne kody Huffmana z powyższych informacji. Jeśli jesteś geniuszem matematycznym, być może już zauważyłeś, że kody te można opracować po prostu zwiększając liczbę binarną o odpowiednią liczbę bitów dla każdego nowego kodu o określonej długości bitowej. Kiedy długość bitów rośnie, po prostu zwiększ liczbę binarną, a następnie ją podwoj i kontynuuj. Staje się oczywiste dla wszystkich, gdy ręcznie wyciągnęliście kilka tych drzew binarnych ...
5) Więc to jest kod, którego użyłem do opracowania kodów Huffmana i zapisania ich w tablicy: (pierwszy odczyt danych na 1) i umieścić go w tablicy: 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;
}
Raz mam generowane kody Huffman i przechowywać je w kolejności, mogę tylko dodać symbole, które odnoszą się one w kolejności, przychodzą w 2). To może nie być strasznie eleganckie, ale wydaje się działać co najmniej i tworzy prawidłowe tabele.
6) Jeśli ktoś nadal to śledzi, zasługujesz na medal.
7) Problem polega na tym, że chciałbym zapisać te informacje w drzewie binarnym, aby później móc wydajniej dekodować dane obrazu w formacie JPG, a nie przeszukiwać tablice za każdym razem. Niestety nie mogę znaleźć ładnego, czystego i wydajnego sposobu na wykonanie tego bezpośrednio z informacji zawartych w nagłówkach jpg, jak wyżej.
Jedyny sposób, jaki mogę wymyślić, to opracowywanie kodów Huffmana jak powyżej, a następnie implementacja pewnej metody, która tworzy węzły w razie potrzeby i zapisuje symbole w odpowiednim miejscu, używając kodów jako adresów sortów.Jednak wydaje mi się, że jest to tak okrągły sposób, że również powielam potrzebne informacje, jestem pewien, że musi istnieć znacznie lepsza i prostsza metoda.
8) Więc jeśli ktoś zrozumiał moje gadki, byłbym bardzo wdzięczny za pewne sugestie. Rozumiem, że jest to bardzo specyficzny problem, ale jeśli nic więcej powyższe informacje mogą okazać się pomocne dla kogoś. Nadal jestem bardzo nowy w tym tak usprawiedliwić moja ignorancja, łatwy do zrozumienia kod jest szczególnie mile widziany!
Bardzo mi to pomogło. Dziękuję człowieku, jesteś królem: D – MrD