4

谁能告诉我在java中使用可变长度位字符串解码二进制数据的最佳方法？

例如：

二进制数据为 10101000 11100010 01100001 01010111 01110001 01010110

我可能需要找到以下 01、100、110、1110、1010 中的任何一个的第一个匹配项...

在这种情况下，匹配将是 1010。然后我需要对其余的二进制数据执行相同的操作。位串最长可达 16 位并跨越字节边界。

基本上，我正在尝试使用从标题中的 Huffman 表创建的位字符串对 Huffman 解码 jpeg。我可以做到，只是它非常混乱，我首先将包括二进制数据在内的所有内容都转换为 Stringbuffers，我知道这不是正确的方法。

在我将所有内容加载到字符串缓冲区之前，我尝试只使用二进制数字，但我当然不能忽略像 00011 这样的代码中的前导 0。我确信必须有一些聪明的方法使用位运算符等来做这个，但我一直盯着解释位掩码和左移等的页面，我仍然不知道！

非常感谢您的帮助！

编辑：

感谢所有的建议。我已经采用了二叉树方法，因为它似乎是 Huffman 东西的标准方法。确实有意义，因为霍夫曼代码是使用树创建的。我还将研究存储需要在大整数中搜索的二进制数据。不知道如何将多个答案标记为正确，但同样感谢。

4

5 回答 5

4

您可能会使用消耗零和一的状态机。状态机将具有您想要检测的所有模式的最终状态。每当它进入最终状态之一时，就会使用匹配的模式向您发送一条消息并返回到初始状态。

最后，您将只有一个 DAG 形式的状态机，其中包含您的所有模式。

要实现它，请使用状态模式 ( http://en.wikipedia.org/wiki/State_pattern ) 或状态机的任何其他实现。

于 2009-03-17T22:08:11.987 回答
3

由于您正在解码 Huffman 编码数据，因此您应该创建一棵二叉树，其中叶子将解码的位字符串作为数据保存，每个 Huffman 代码的位是相应数据的路径。霍夫曼码的位通过位移位和位掩码操作访问。当你到达一个叶子时，你输出那个叶子的数据并回到树的根部。它非常快速和高效。

于 2009-03-17T23:41:59.687 回答
1

您可以尝试将其填充到BigInteger中，然后使用 shift 和 test 方法。然后使用循环遍历并接受每个子模式。

如果霍夫曼代码在树中，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
   }
}
于 2009-03-17T22:07:46.620 回答
1

我建议尝试一下。它专为前缀搜索而设计。在你的情况下，这将是一个二元树。

于 2009-03-17T23:57:36.047 回答
0

你可以使用 java.util.BitSet 来存储你的二进制数据，然后你可以实现一些搜索功能来找到一个较小的 BitSet 在大的​​里面的位置......

于 2009-03-17T22:18:19.637 回答