Декодирование таблицы Хаффмана JPEG

Question

Я ищу способ получить minCode, maxCode и valPtr из произвольной таблицы Хаффмана.

Например, ниже представлена ​​таблица DC Хаффмана, сгенерированная JpegSnoop:

      Destination ID = 0
  Class = 0 (DC / Lossless Table)
    Codes of length 01 bits (000 total): 
    Codes of length 02 bits (001 total): 00 
    Codes of length 03 bits (005 total): 01 02 03 04 05 
    Codes of length 04 bits (001 total): 06 
    Codes of length 05 bits (001 total): 07 
    Codes of length 06 bits (001 total): 08 
    Codes of length 07 bits (001 total): 09 
    Codes of length 08 bits (001 total): 0A 
    Codes of length 09 bits (001 total): 0B 
    Codes of length 10 bits (000 total): 
    Codes of length 11 bits (000 total): 
    Codes of length 12 bits (000 total): 
    Codes of length 13 bits (000 total): 
    Codes of length 14 bits (000 total): 
    Codes of length 15 bits (000 total): 
    Codes of length 16 bits (000 total): 
    Total number of codes: 012

А вот его Mincode, MaxCode и valPtr соответственно:

      { 0, 0, 2, 14, 30, 62, 126, 254, 510, 0, 0, 0, 0, 0, 0, 0 },//YDC
{ -1, 0, 6, 14, 30, 62, 126, 254, 510, -1, -1, -1, -1, -1, -1, -1 },//YDC
{ 0, 0, 1, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0, 0, 0, 0 },//YDC

Теперь я действительно смущен тем, как были получены эти значения.

Проверил файл itu-t81 , но там не очень понятно.

Answer 1

Чтобы сгенерировать биты кода, вы начинаете со всех нулевых битов. В пределах каждой длины кода увеличивайте код как целое число для каждого символа. При увеличении длины кода увеличивайте, а затем добавляйте нулевой бит в конец.

Итак, для вашего примера кода у нас есть каждая длина, за которой следуют соответствующие коды в двоичном формате:

      2: 00
3: 010, 011, 100, 101, 110
4: 1110
5: 11110
6: 111110
7: 1111110
8: 11111110
9: 111111110

Преобразовывая их в соответствующие целочисленные диапазоны для каждой длины в битах, мы имеем:

      2: 0..0
3: 2..6
4: 14..14
5: 30..30
6: 62..62
7: 126..126
8: 254..254
9: 510..510

Вы можете увидеть именно эти диапазоны в векторах MinCode и MaxCode.

У вас также есть список символов, соответствующих кодам. В этом примере этот список просто:

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

(Конкретные значения символов не имеют отношения к вектору valPtr. Это может быть что угодно.)

Коды присваиваются символам от самого короткого до самого длинного и в пределах каждой длины в целочисленном порядке. Вектор valPtr — это просто индекс первого символа в этом векторе, который соответствует каждой битовой длине. Чтобы сгенерировать вектор, начните с нуля и добавьте количество символов каждой длины кода, чтобы получить начальный индекс для следующей длины кода.

      1: 0, 0 symbols
2: 0 + 0 = 0, 1 2-bit symbol
3: 0 + 1 = 1, 5 3-bit symbols
4: 1 + 5 = 6, 1 4-bit symbol
5: 6 + 1 = 7, 1 5-bit symbol
6: 7 + 1 = 8, 1 6-bit symbol
7: 8 + 1 = 9, 1 7-bit symbol
8: 9 + 1 = 10, 1 8-bit symbol
9: 10 + 1 = 11

Пример вектора valPtr — это числа после указанных выше знаков равенства.

Answer 2

Спасибо, я создал код, который декодирует таблицы и возвращает нужные значения. Код можно найти на моем GitHub здесь .