可変長ビット文字列のバイナリデータを検索する最善の方法は？

StackOverflow https://stackoverflow.com/questions/656175

  •  19-08-2019
  •  | 
  •  

質問

Javaの可変長ビット文字列を使用してバイナリデータをデコードする最適な方法を教えていただけますか？

例：

  

バイナリデータは10101000 11100010 01100001 01010111 01110001 01010110

     

次の01、100、110、1110、1010のいずれかの最初の一致を見つける必要があるかもしれません...

     

この場合、一致は1010になります。その後、残りのバイナリデータについても同じようにする必要があります。ビット文字列は最大16ビット長で、バイト境界を越えることができます。

基本的に、ヘッダーのHuffmanテーブルから作成したビット文字列を使用してjpegをHuffmanデコードしようとしています。私はそれを行うことができますが、それは非常に面倒です、バイナリデータを含むすべてを最初にStringbuffersに変換していますが、それが正しい方法ではないことを知っています。

すべてを文字列バッファーにロードする前に、バイナリの数字だけを使用しようとしましたが、もちろん00011のようなコードの先頭の0は無視できません。ビット単位の演算子とこれをしたいのですが、私はビットマスクや左シフトなどを説明するページを見つめていましたが、まだ手がかりがありません！

ご協力いただきありがとうございます！

編集：

すべての提案に感謝します。それはハフマンのものの標準的な方法であるように思われるので、私は二分木アプローチに行きました。ハフマンコードはツリーを使用して作成されるため、本当に意味があります。また、大きな整数で検索する必要があるバイナリデータの格納についても調べます。複数の回答を正解としてマークする方法がわかりませんが、すべて同じように感謝します。

役に立ちましたか？

解決

ハフマンのエンコードされたデータをデコードしているので、デコードされたビット列をデータとして保持するバイナリツリーを作成する必要があります。各ハフマンコードのビットは、対応するデータへのパスです。ハフマンコードのビットは、ビットシフトおよびビットマスク操作でアクセスされます。リーフに到達すると、そのリーフでデータを出力し、ツリーのルートに戻ります。非常に高速で効率的です。

他のヒント

0と1を消費するステートマシンを使用できます。ステートマシンには、検出するすべてのパターンの最終状態があります。最終状態のいずれかに入ると、一致したパターンでメッセージが送信され、初期状態に戻ります。

最後に、すべてのパターンを含むDAGの形式のステートマシンは1つだけです。

それを実装するには、状態パターンを使用します（ http://en.wikipedia.org/wiki/State_pattern ）またはステートマシンの他の実装。

に詰め込んでみてください。 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
   }
}

トライを提案します。プレフィックス検索用に明示的に設計されています。あなたの場合、それはバイナリトライです。

java.util.BitSetを使用してバイナリデータを保存してから、いくつかの検索関数を実装して、大きなBitSet内の小さなBitSetの位置を見つけることができます...

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top