ハフマンでエンコードされたビットストリームからメッセージをデコードする方法は? ハフマンアルゴリズムの考え方がよくわかりません。
私が理解している限り、「私の名前はXYZです」というテキストメッセージが表示されたとします。
次に、エンコード プロセスは次のようになります。 1. 文字の頻度を数えます。2. 度数を値で並べ替えます。3. ツリーを構築します。4. 左端を 0、右端を 1 と見なしてツリーをトラバースし、目的のメッセージ文字に到達します。5. コードを連結してビット ストリームを見つけます。
問題は、エンコードされたビット ストリームから元のメッセージを見つけるにはどうすればよいかということです。
ハフマン木をもう一度構築する必要があると思います。
しかし、ビット ストリームからハフマン ツリーを構築するにはどうすればよいでしょうか。
元のツリーがないとメッセージをデコードできません。したがって、送信側はそれをメッセージに含める必要があります (オーバーヘッドのある長いメッセージの場合は小さくなります)。または、メッセージを送信する前に両方の当事者がツリーについて同意する必要があります。次に、プロセスは逆です。ストリームからビットごとに読み取り、ツリーをトラバースします。リーフをヒットしたら、キャラクターを放出します。
これにはいくつかの選択肢があります。1 つは、固定ハフマン ツリーを使用することです。たとえば、通常の英語のテキストをエンコードしている場合、文字の相対頻度は通常一定に近いため、送信者と受信者が事前に合意するだけでかなり合理的に行うことができます。 3つのうち、両方が使用します。
あなたが説明する2パスハフマンアルゴリズムの場合、データとともにツリーを（何らかの形で）送信することにかなりこだわっています。
また、動的ハフマン ツリーを使用することもできます。この場合、(たとえば) 上記の最初のオプションで概説したツリーから開始しますが、データを処理する際に、送信機と受信機の両方がツリーを調整して、観測された周波数に適合させます。これに対する唯一の秘訣は、調整前にツリーを使用して各文字をエンコードし、調整を行ってから次の文字を処理する必要があることです。このようにして、受信側は送信側と同期を保つことができます。