Как лучше всего искать двоичные данные для битовых строк переменной длины?

Question

Может кто-нибудь сказать мне лучший способ декодировать двоичные данные с помощью битовых строк переменной длины в Java?

Например:

Двоичные данные: 10101000 11100010 01100001 01010111 01110001 01010110

Мне может понадобиться найти первое совпадение любого из следующих 01, 100, 110, 1110, 1010 ...

В этом случае совпадение будет 1010. Затем мне нужно сделать то же самое для оставшейся части двоичных данных. Строки битов могут иметь длину до 16 бит и выходить за границы байтов.

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

Прежде чем загружать все в строковые буферы, я пытался использовать только числа в двоичном формате, но, конечно, я не могу игнорировать начальные 0 в коде, подобном 00011. Я уверен, что должен быть какой-то умный способ, использующий побитовые операторы Я хотел бы сделать это, но я пялился на страницы, объясняющие битовые маски, сдвиги влево и т. д., и до сих пор не понимаю!

Большое спасибо за любую помощь!

EDIT:

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

Answer 1

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

Наконец, у вас будет только один конечный автомат в форме DAG, содержащий все ваши шаблоны.

Для его реализации используется шаблон состояния (http://en.wikipedia.org/wiki/State_pattern) или любая другая реализация конечного автомата.

Answer 2

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

Answer 3

Я бы предложил три . Он явно предназначен для поиска префиксов. В вашем случае это будет двоичный файл.

Answer 4

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

Если код Хаффмана находится в дереве, 1 == правый узел, 0 == левый узел.

for( int i =numbitsTotal; i > 0; --i )
{
   int bit = bigInt.testBit( i );
   if( bit == 1 )
   {
       // take right node -- if null accept code, apply from top
   }
   else
   {
      // take left node -- if null accept code, apply from top
   }
}

Answer 5

Вы можете использовать java.util.BitSet для хранения ваших двоичных данных, а затем реализовать некоторые функции поиска, чтобы найти позицию меньшего BitSet внутри большого ...