3

NEED などのハフマン コードを使用して単語をエンコードする方法

4

4 に答える 4

5

ハフマン エンコーディングでは、基本的に可変長のビット文字列を使用してトークン (通常はいくつかの例外を除いて文字) を表します。トークンが一般的であるほど、ビット長は短くなり、これは (通常) ストリームが処理されるときに動的になります。

通常、ESCAPE と END-STREAM という 2 つの特別なトークンがあります。

エンコーディングは、基本的にトークンを取得するためのビット シーケンスのルックアップである辞書を維持します。最初は、2 つの特別なトークンのみが含まれています。

ESCAPE と END_STREAM の最初のビット シーケンスは 0 と 1 の可能性があります (これは最初は問題になりません)。エンコーダーが辞書にない文字を受け取ると、ESCAPE と完全な長さのトークンを出力し、それを追加して、すべてのトークンの頻度に基づいて新しいビット シーケンスを割り当てます。

したがって、「N」は出力ストリームになる場合があります。

0 xxxxxxxx
| +- token code for N
+--- ESCAPE

そして新しい辞書：

ESCAPE:00
END-STREAM:01
N:1

次に、「E」は出力ストリームになる場合があります。

0 xxxxxxxx 0 yyyyyyyy
             +- token code for E

そして新しい辞書：

ESCAPE:00
END-STREAM:01
N:10
E:11

次の E は、既に辞書にあるため、ESCAPE 出力にはなりません。コード (11) を出力するだけです。E のカウントが増えたため、辞書が変更されます。すべての文字が 2 進数であるため、この状況では問題になりませんが、より複雑な例では、'E' トークンのビット長が短くなります。

D が到着すると、出力ストリームは次のようになります。

0 xxxxxxxx 0 yyyyyyyy 11 0 zzzzzzzz
                      |    +- token code for D
                      +------ second E

そして新しい辞書：

ESCAPE:00
END-STREAM:011
N:010
E:11
D:10

したがって、より多くの文字が入ると、一般的なもののビット長が減少し、一般的でないもののビット長が増加し、圧縮が行われることがわかります. この場合、N (または D) は 3 桁のコードを取得しますが、E はもっと多くのコードがあるため 2 桁のコードを使用します。

ESCAPE セクションは圧縮解除のために辞書を動的に構築するため、辞書をファイルと一緒に保存する必要がないという利点があります。

また、最後まで END-STREAM トークンが存在しないため、ビット長がどんどん大きくなっていきます。ESCAPE も同様で、まだ新しいキャラクターがたくさん入ってきますが、そのビット長は短いままですが、新しいキャラクターが到着しないときは、END-STREAM と同じ運命をたどります。

(8 ビット ASCII) 入力ストリームの最良のケースは、何百万もの同じ文字だけを含むファイルです。これには、最初の文字に 9 ビット、追加の文字ごとに 1 ビット、ストリームの最後に 2 ビットのコストがかかります。その速さは、8 分の 1 の圧縮率 (97.5%) に近づきます。

最悪のケースは、文字ごとに 9 ビットとストリームの終わりを消費する各文字の 1 つだけです。これにより、実際にはストリームが 12.5% 拡張されます。

于 2008-12-07T07:06:09.923 に答える
1

ハフマンコーディングのことだと思います。データを損失なく圧縮するためのアルゴリズムです。簡単に言えば、データの最も長く、最も繰り返しの多い連続ビットを可能な限り最小の表現に置き換えます (これがほとんどの圧縮のしくみです)。たとえば、HTML ページは、すべての 32 ビットをわずか 2 ビットに減らして、非常に一般的な<DIV2 進数に割り当てる場合があります。01<DIV

それが基本的な考え方です。もう 1 つのトリックは、固定サイズやセパレーターを使用する必要がないように数字を選択する方法です。これは、ハフマン ツリーを使用して行われます。詳細については、ウィキペディアの記事を参照してください。

于 2008-12-07T06:33:58.443 に答える
1

Huffman Coding with F#を参照してください。これは、F# で記述されたハフマン コーダー/デコーダーを紹介するブログ投稿です。短くてわかりやすい。

于 2008-12-07T06:56:34.200 に答える
0

私の C# プロジェクトの Huffman を見てください: https://github.com/kad0xf/HuffmanSharp

于 2015-07-22T19:38:07.143 に答える