Я думал, что смогу решить эту проблему сам, но мне кажется, что я вообще не двигаюсь вперед.
Хорошо, фон:
Мне нужно создать дерево кодов Хаффмана из информации, предоставленной заголовком FFC4, DHT (Define Huffman Table) в файле jpg. Заголовок DHT определяет таблицу Хаффмана следующим образом:
1) Серия из 16 байтов. Каждый байт определяет, сколько символов имеют код Хаффмана из n битов, где n - это позиция байта в ряду. (это имело какой-то смысл? !!) Например, необработанные данные в шестнадцатеричном формате:
00 01 05 01 01 01 ... 00
это означает, что:
Num of bits: 1 2 3 4 5 6 7 ... 16
Num of codes: 00 01 05 01 01 01 01 ... 00
2) После списка из 16 байтов идут сами символы. Например:
00 01 02 03 04 05 06 07 08 09 0A 0B
3) Объединяя две части, мы видим, что они:
00 кодов с 1 битом.
01 код с 2 битами: поэтому возьмите первый символ из списка: 00
05 кодов с 3 битами: поэтому возьмите следующие 5 символов из списка: 01 02 03 04 05
.. и так далее
4) Наконец, мы должны определить действительные коды Хаффмана на основе информации выше. Если вы математический гений, вы, возможно, уже заметили, что эти коды можно обработать, просто увеличив двоичное число на соответствующее число битов для каждого нового кода на определенной длине в битах. Когда длина в битах увеличивается, просто увеличьте двоичное число, затем удвойте его и продолжайте. Это станет очевидным для всех остальных, когда вы вытащите несколько этих двоичных деревьев вручную ...
5) Так что это код, который я использовал для разработки кодов Хаффмана и сохранения их в массиве: (сначала я прочитал данные в 1) и поместил их в массив: 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;
}
После того, как я сгенерировал коды Хаффмана и сохранил их по порядку, я могу просто добавить символы, на которые они ссылаются, в порядке их поступления в 2). Это может быть не очень элегантно, но, похоже, работает по крайней мере и создает правильные таблицы.
6) Если кто-то все еще следует этому, вы заслуживаете медали.
7) Теперь проблема в том, что я хотел бы сохранить эту информацию в двоичном дереве, чтобы впоследствии я мог эффективно декодировать данные изображения jpg, а не искать в массивах каждый раз. К сожалению, я не могу найти хороший чистый и эффективный способ сделать это непосредственно из информации, представленной в заголовках jpg, как указано выше.
Единственный способ, о котором я могу думать, - это сначала обработать коды Хаффмана, как описано выше, а затем реализовать некоторый метод, который создает узлы по мере необходимости и сохраняет символы в соответствующем месте, используя коды в качестве своего рода адреса. Тем не менее, это кажется таким круговым способом, который также дублирует информацию, в которой я нуждаюсь, я уверен, что должен быть намного лучший и более простой метод.
8) Так что, если бы кто-нибудь понял мои разговоры, я был бы очень благодарен за некоторые предложения. Я понимаю, что это очень специфическая проблема, но если ничто иное, информация выше может оказаться полезной для кого-то. Я все еще новичок в этом, так что извините за мое невежество, особенно приветствуется простой для понимания код!