動機
P2P ソフトウェアのように、部分的にダウンロードされるハフマン圧縮ファイルを想像してみてください。最初にファイル全体にディスク領域を割り当ててから、ランダムなファイル チャンクのダウンロードを開始します。ハフマン コードの 1 つ (ただしどれかはわかりません) は終了コードであるため、このコードがデコードされた場合は停止します。ファイルがいくつかの huffman 圧縮ストリームで構成されていると仮定すると、ダウンロードが完了する前にそれらのいくつかを解凍することを試みることができます。
ここで、ディスク スペースを事前に割り当てる方法が重要です。ハフマン ストリームが開始されたとしますが、まだ完了していないため、事前に割り当てられたディスク スペースが不足しているとします。通常、このスペースはすべて 0 なので、ハフマン コードでシンボルをデコードし続けます00..。これが最終コードでない場合、「無効な」データに気付かず、事前に割り当てられたスペースが 2 GB ある場合は、無駄なデコードを行っていることになります。
そのため、できるだけ早くデコードを停止する方法でスペースを事前に割り当てたいと考えています。
質問
「ハフマン ターミネータ」として機能する最短のビット文字列を探しています。つまり、この文字列をデコードすると、すべてのハフマン コードが少なくとも 1 回デコードされるため、確実に終了コードを受け取ることができます。これは、長さ1..nビットのハフマン コードのすべての組み合わせで機能するはずです。
00..注: 上記の仮想シナリオ (エンド コードとして使用、まだダウンロードされていないチャンクを検出するために P2P セグメント データを使用)に対する簡単な解決策があることは知っていますが、これは「ハフマン ターミネータ」の理論的な使用法を示すシナリオの例にすぎません。ビット文字列、私はこのシナリオを解決することに興味はありませんが、「ハフマンターミネーター」として機能するビット文字列を生成/見つけるためのアルゴリズム/方法/アイデアを探しています。
例
n = 2、[0, 1]、[00, 01, 1]、[0, 10, 11]の可能なハフマン コードの組み合わせを見てみましょう[00, 01, 10, 11]。1..n次に、可能なすべての長さのビット シーケンス( 0、1、00、01、10)を含むビット文字列から始めましょう11。
001011
さまざまなハフマン コードの組み合わせでデコードすると、次のようになります (ハフマン コードはシンボルに割り当てられますA..D)。
Combination Decoded symbols
[0, 1] AABABB
[00,01,1] ACBC
[0,10,11] AABC
[00,01,10,11] ACD
これは良いスタートであり、最初の 3 つのハフマン コードはすべて既にデコードされていますが、 でデコードすると[00, 01, 10, 11]、シンボルB(ハフマン コード01) が失われます。それでは、これをビット文字列に追加しましょう。
00101101
n=2これは、長さが 8 ビットの有効な「ハフマン ターミネータ」です。このバイトを使用してディスク領域を事前に割り当てておけば、2 ビットを超えないすべてのハフマン コードを確実に終了させることができます。各シンボルを 1 回デコードするn=2ための組み合わせの最小の長さであるため、より短いターミネータ文字列が存在しないこともわかっています。[00, 01, 10, 11]
n=3、 （43ビット）の「ハフマンターミネータ」も見つけました0001011001110100111010011100010101111101110が、それが正しいかどうか100％確信が持てず、最短のものかどうかもわかりません。
私が探しているもの
特定の のハフマン ターミネータを検索または生成するアルゴリズム/アイデア
n。私の試みは例に似ています: 開始文字列を生成し、必要に応じてビットを追加して、すべての異なるハフマン コードの組み合わせを満たします。しかし、もっと良い方法があると確信しています。特定のハフマンターミネータ
n=8およびn=16この問題 (または類似の問題) に関する論文/リンクがある場合。
ボーナス
「ハフマン ターミネータ」を見つけるためのボーナス ポイントは、ビット位置 から開始しても機能する1..nため、データが以前にデコードされた場合でも終了し、最初のビットで新しいハフマン コードに到達して開始することはありません。