Упрощение энтропийного декодирования таблицы Хаффмана (на С) - PullRequest
2 голосов
/ 25 декабря 2011

Впервые использую этот сайт, чтобы задать вопрос, но я получил много много ответов!

Справочная информация:

Я декодирую видеопоток переменной длины, который был закодирован с использованием кодирования RLE и Хаффмана. Длина потока составляет от 10 до 20 килобайт, и поэтому я стараюсь «выжать» как можно больше времени из каждого шага, чтобы его можно было эффективно декодировать в реальном времени.

Прямо сейчас шаг, над которым я работаю, включает преобразование потока битов в число, основанное на таблице Хаффмана. Я делаю это путем подсчета числа ведущих нулей, чтобы определить количество конечных битов для включения. Таблица выглядит так:

       001xs    range -3 to 3
      0001xxs   range -7 to 7
     00001xxxs  range -15 to 15

И до 127. s - это знаковый бит, 0 означает положительный, 1 означает отрицательный. Так, например, если clz = 2, я бы прочитал следующие 3 бита, 2 для значения и 1 для знака.

Вопрос:

Прямо сейчас неприятное выражение, которое я создал для этого:

int outblock[64];
unsigned int value; 
//example value 7 -> 111 (xxs) which translates to -3

    value=7;

outblock[index]=(((value&1)?-1:1)*(value>>1));    //expression

Есть ли более простой и быстрый способ сделать это?

Спасибо за любую помощь!

Тим

РЕДАКТИРОВАТЬ: выражение отредактировано, потому что оно не генерирует правильные положительные значения. Теперь генерирует положительные и отрицательные значения.

1 Ответ

0 голосов
/ 01 января 2012

Я просто быстро погуглил «эффективное декодирование Хаффмана» и нашел следующие ссылки, которые могут быть полезны:

Кажется, самый эффективный способ декодирования Хаффмана - это использование поиска по таблице.Вы пробовали такой метод?

Мне было бы интересно посмотреть ваши времена оригинального алгоритма, прежде чем делать какие-либо оптимизации.Наконец, на каком оборудовании / ОС вы работаете?

С уважением,

...