4

簡単に言うと、正規のハフマン リストからハフマン コードを生成しようとしています。基本的に、次の 2 つのループが実行され、バイナリ文字列が生成されます。コードは次のとおりです。

for (int i = 1; i <= 17; i++) {
        for (int j = 0; j < input.length; j++) { 
            if (input[j] == i) {
                result.put(allocateCode(i, j), j); //update a hashmap
                huffCode += (1 << (17 - i)); //Update the huffman code
            }
        }

    }

基本的に、コードは長さが 1 のすべてのコードを探し、それぞれのハフマン コードを生成する必要があります。たとえば、長さ 1 は (順番に) 0、1 になります。また、長さ 3 は 100、101、110 になります。

このallocateCode関数は、結果を示す文字列を返すだけで、最初の実行で次のようになります。

Huffman code for code 2 is: 0 (0) length was: 1
Huffman code for code 6 is: 10 (2) length was: 2
Huffman code for code 0 is: 1100 (12) length was: 4
Huffman code for code 3 is: 1101 (13) length was: 4
Huffman code for code 4 is: 1110 (14) length was: 4
Huffman code for code 7 is: 11110 (30) length was: 5
Huffman code for code 1 is: 111110 (62) length was: 6
Huffman code for code 5 is: 111111 (63) length was: 6

これは正しく、正しいハフマン コードが生成されています。ただし、長さの 2 番目の配列で実行すると、次のようになります。

Huffman code for code 1 is: 0 (0) length was: 1
Huffman code for code 4 is: 1 (1) length was: 1
Huffman code for code 8 is: 100 (4) length was: 3
Huffman code for code 9 is: 100 (4) length was: 3
Huffman code for code 13 is: 101 (5) length was: 3
Huffman code for code 16 is: 1011000 (88) length was: 7
Huffman code for code 10 is: 10110001 (177) length was: 8
Huffman code for code 2 is: 101100011 (355) length was: 9
Huffman code for code 3 is: 101100011 (355) length was: 9
Huffman code for code 0 is: 1011001000 (712) length was: 10
Huffman code for code 5 is: 1011001000 (712) length was: 10
Huffman code for code 6 is: 1011001001 (713) length was: 10
Huffman code for code 7 is: 10110010011 (1427) length was: 11
Huffman code for code 14 is: 10110010011 (1427) length was: 11
Huffman code for code 17 is: 10110010100 (1428) length was: 11
Huffman code for code 19 is: 10110010100 (1428) length was: 11
Huffman code for code 18 is: 101100101010000 (22864) length was: 15

ご覧のとおり、同じコードが複数回生成されています。たとえば、コード 8 と 9、およびコード 2 と 3 です。

私の問題はネストされたループ内にあると思いますが、ある実行では完全に機能し、別の実行では失敗する理由がわかりません。

明らかな何かが欠けているだけかもしれませんが、見てもわかりません。

アドバイスをいただければ幸いです。

ありがとう

アップデート

自分のコードを調べてみると、最初にデータを読み込むときに実際に小さな間違いを犯していたようです。そのため、間違ったハフマン コードを取得していました!!

4

1 に答える 1

1

2 番目の例の最初の 2 つのコードの長さは両方とも 1 です。これにより、最初の 2 つの後に他の可能なコードは残りません。すべてのプレフィックス パターンが使用されました。

コードは、誤った入力を検出するために、使用可能な残りのコードの数を保持する必要があります。各コードのカウントを単純に減らし、現在の長さよりも 1 つ多い次の長さに移動するたびにカウントを 2 倍にします。(例えば、長さ 3 のコードから長さ 5 のコードに移動する場合、長さ 4 のコードがなくてもカウントを 2 倍にするなど、その長さのコードがない場合でも 2 倍にすることを確認してください。) 2 でカウントを開始します。長さ 1 コードの場合。

そのカウントが負になると、エラーが発生し、そこで停止できます。その長さのセットにコードを割り当てることはできません。

プロセスの最後にカウントがゼロでない場合は、コードが不完全です。アプリケーションによっては、エラーになる場合とそうでない場合があります。これは、コードが最適化されていないことを意味し、これらのシンボルをコード化するために使用できるビット数を減らすことができた可能性があります。

于 2013-05-12T17:02:50.517 に答える