1

ハフマン エンコーディングを行っていますが、fwrite() を使用してエンコーディングを出力に書き込む方法がわかりません。

これらのエンコーディングがあるとしましょう：

Character A (65) gets an encoding of 101
Character B (66) gets an encoding of 1100111

ただし、これらのエンコーディングは整数として保存されるため、

101 actually has a decimal value of 5 which is saved in memory as 00000101
1100111 actually has a decimal value of 103 which is saved in memory as 01100111

したがって、fwrite() を使用してそれらを書き出す場合は、バッファを使用するとします。

int buff[4]

次のように始まります

buff[0]    buff[1]    buff[2]    buff[3]
XXXXXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

(X を使用して初期化されていないことを示します) なぜ 4 バイトを使用するのですか? 非常に長いエンコーディングを考慮する必要があるためです。27 ビット長のエンコーディングがある場合はどうなるでしょうか。これらのバイトの 3 つと 4 番目のバイトを少し埋める必要があります。

ここで、この一連の文字をエンコードして出力ファイルに書き込む必要があるとします。

「ABB」

まず、A をエンコードすると、buff[] は次のようになります。

buff[0]    buff[1]    buff[2]    buff[3]
101XXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

次に、B をエンコードする必要があるため、buff[] は次のようになります。

buff[0]    buff[1]    buff[2]    buff[3]
10111001 - 11XXXXXX - XXXXXXXX - XXXXXXXX

ここで、buff[] の 1 バイトがいっぱいになったので、そのバイトをエンコードして、buff[] の他のスロットを下にシフトする必要があります。

fwrite(buff[0], 1, 1, fptOutput);
/* insert code to shift buff down */

したがって、バフは次のようになります。

buff[0]    buff[1]    buff[2]    buff[3]
11XXXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

次に、別の「B」をエンコードすると、buff[] は次のようになります。

buff[0]    buff[1]    buff[2]    buff[3]
11110011 - 1XXXXXXX - XXXXXXXX - XXXXXXXX

次に、再度 fwrite() buff[0] を実行し、シフトを再度実行します。

しかし、エンコードするものが他にないため、残りのバイトを 0 で埋める必要があるため、バフは次のようになります。

buff[0]    buff[1]    buff[2]    buff[3]
10000000 - XXXXXXXX - XXXXXXXX - XXXXXXXX

そして、その最後のバイトを書き込めば完了です。

問題は、それを体系的にプログラムする方法がまったくわからないことです。ビット操作を理解しています。たとえば、最初の「A」エンコーディングでは、「00000101」を左に 5 桁シフトして「101-----」にする必要があります。その手順は理解できますが、その後はわかりません。次のエンコーディングをどこにシフトするかを追跡する方法。

手動で行っている場合、必要に応じて各変数をシフトする方法を理解できますが、非常に長いファイル内の一連のエンコーディングごとに機能する一連の方程式を考え出す方法がわかりません.

4

1 に答える 1

0

各文字のエンコーディングの配列と、各文字エンコーディングのビット数の配列を格納する必要があります。これらはすべて異なるためです。

次に、バフ配列に残っているビット数を追跡​​する必要があります。

次に、文字を追加するたびに、その文字エンコーディングを別の一時バッファーにコピーします。次に、バッファ配列に既に残っているビット数だけ、そのエンコードを上にシフトします。次に、シフトされたエンコーディングをバフ配列にビットごとに OR します。

次に、バフ配列からデータを書き込み、残りのバフ データを下にシフトし、バフ配列に残っているビット数を調整します。

以下は、16 ビット int (short int) の配列をビット単位で上下にシフトする関数です。ビットを上下にシフトするため、少しやり過ぎです。バイトまたはロングで動作するように変更できます。

void 
shiftBits(unsigned short int *buffer, int bufferSize, int bitsToShiftUp)
{
int wordsToShift;
int bitsToShift;
int backBitsToShift;
int iTo;
int iFrom;

if (bitsToShiftUp > 0)
{
    //Shift up
    wordsToShift = bitsToShiftUp / 16;
    bitsToShift = bitsToShiftUp - (wordsToShift * 16);

    iTo = bufferSize - 1;
    iFrom = iTo - wordsToShift;

    if (bitsToShift == 0)
    {
        while (iFrom >= 0)
        {
            buffer[iTo] = buffer[iFrom];
            iTo--;
            iFrom--;
        }
        while (iTo >= 0)
        {
            buffer[iTo] = 0;
            iTo--;
        }
    }
    else
    {
        backBitsToShift = 16 - bitsToShift;
        while (iFrom >= 1)
        {
            buffer[iTo] = (buffer[iFrom] << bitsToShift) | (buffer[iFrom-1] >> backBitsToShift);
            iTo--;
            iFrom--;
        }
        if (iFrom >= 0)
        {
            buffer[iTo] = buffer[iFrom] << bitsToShift;
            iTo--;
        }
        while (iTo >= 0)
        {
            buffer[iTo] = 0;
            iTo--;
        }
    }
}
else if (bitsToShiftUp  < 0)
{
    //Shift down
    wordsToShift = (-bitsToShiftUp) / 16;
    bitsToShift = (-bitsToShiftUp) - (wordsToShift * 16);

    iTo = 0;
    iFrom = wordsToShift;

    if (bitsToShift == 0)
    {
        while (iFrom < bufferSize)
        {
            buffer[iTo] = buffer[iFrom];
            iTo++;
            iFrom++;
        }
        while (iTo < bufferSize)
        {
            buffer[iTo] = 0;
            iTo++;
        }
    }
    else
    {
        backBitsToShift = 16 - bitsToShift;
        while (iFrom < bufferSize - 1)
        {
            buffer[iTo] = (buffer[iFrom] >> bitsToShift) | (buffer[iFrom+1] << backBitsToShift);
            iTo++;
            iFrom++;
        }
        if (iFrom < bufferSize)
        {
            buffer[iTo] = buffer[iFrom] >> bitsToShift;
            iTo++;
        }
        while (iTo < bufferSize)
        {
            buffer[iTo] = 0;
            iTo++;
        }
    }
}
}
于 2013-02-26T05:37:41.393 に答える