8

Huffman Copression で最後のバイトを処理する最善の方法は何か疑問に思っています。テキストファイルを非常にうまく圧縮できるC++の素敵なコードがありますが、現在、最後のバイトを処理する方法がわからないため、コード化された文字の数もコード化されたファイルに書き込む必要があります（入力ファイルのサイズに等しい）。より良い。

たとえば、圧縮する最後の文字は 'a' で、このコードは 011 で、新しいバイトの書き込みを開始したところなので、最後のバイトは次のようになります: 011 + ゴミの 5 ビット、たとえば終わり。そして、このコード化されたファイルをエンコードしているときに、コード 00000 (またはゼロが少ない) が一部の char のコードである可能性があるため、エンコードされたファイルの最後にゴミの char が含まれます。

最初の段落で書いたように、入力ファイルの文字数をコード化されたファイルに保存することでこれを回避しています。エンコード中に、コード化されたファイルを読み取ってその数に到達します（EndOfFileではなく、それらの例に到達しないようにします5 つのゼロ)。コード化されたファイルのサイズが長いほど大きくなり、あまり効率的ではありません。

どうすればこれをより良い方法で処理できますか?

4

2 に答える 2

8

あなたのアプローチ（エンコードされたバイト数をファイルに書き込む）は、完全に合理的なアプローチです。別の方法を試したい場合は、入力の終わりを示す新しい「疑似 EOF」文字を発明することを検討できます (これを□で示します)。文字列sを圧縮したいときはいつでも、代わりに文字列s □ を圧縮します。これは、エンコーディング ツリーを構築するときに、□ の一意のエンコーディングを持つように、□ 文字のコピーを 1 つ含めることを意味します。次に、文字列をファイルに書き出すときは、通常どおり文字列のビット文字を書き出してから、□のビット パターンを書き出します。残りのビットがある場合は、任意に設定したままにすることができます。

このアプローチの利点は、ファイルをデコードするときに□文字が見つかった場合、ファイルの最後に到達したことがわかっているため、ビットのデコードをすぐに停止できることです。これは、書き出されたバイト数をどこかに保存する必要はありません。エンコーディングは暗黙的に独自のエンドポイントをマークします。

このセットアップの欠点は、他のすべての文字に加えて□にビット パターンを割り当てる必要があるため、特定の文字で使用されるビット パターンの長さが長くなる可能性があることです。

私はプログラミングの入門コースを教えており、課題の 1 つとしてハフマン符号化を使用しています。ファイルの内容の前にビット数またはバイト数を書き出すよりも少し簡単なので、学生に上記のアプローチを使用してもらいます。詳細については、この配布資料またはコースの講義スライドをご覧ください。

お役に立てれば！

于 2013-02-02T23:39:41.493 に答える
3

これは古い質問であることは知っていますが、それでも代替案があるので、誰かの助けになるかもしれません.

圧縮ファイルを出力に書き込んでいる場合、おそらく現在のバイトのどこにいるかを追跡する整数があります (ビットシフト用)。

char c, p;
p = '\0';
int curr = 7;
while (infile.get(c))
{
    std::string trav = GetTraversal(c);
    for (int i = 0; i < trav.size(); i++)
    {
        if (trav[i] == '1')
            p += (1 << curr);
        if (--curr < 0)
        {
            outfile.put(p);
            p = '\0';
            curr = 7;
        }
    }
}
if (curr < 7)
    outfile.put(p);

このブロック(curr+1)%8の最後で、最後のデータ バイトのトラッシュ ビットの数に等しくなります。その後、それを 1 バイトの追加バイトとして最後に保存し、解凍するときに覚えておいてください。

于 2014-12-16T20:38:17.470 に答える