ハフマン符号化プログラミング

Question

学校の課題でVisualStudioで実現できるハフマン符号化プログラム（３次拡大）を作成せよ。という課題が出題されました。
　しかし私は今まで入門程度のプログラミングしかやったことがなく、。指定されたファイルの文字数を調べる程度の事しかできない程度のプログラミングの知識なのでさっぱりです。

指定されたｔｘｔファイルを読み込んで、文字数を数えて、文字の種類を調べて、各文字の発生確率を調べて、各文字を３次拡大行列にし、ツリー構造のアルゴリズムを作成し、各値を２進数に変換して、２進数に変換したものをtxtファイルにして保存するということは何となくわかるのですが、それを実現する知識がありません。

プログラミングの知識をお持ちの方のご協力をお願いいたします。

dscripty · Accepted Answer

「ハフマン符号化プログラム（３次拡大）を作成せよ。」

これだと、問題に不備があるとおもう。
入力情報源の符号はビット？バイト？その他？

一文字だとすると、文字コードによっては長さが変動するから、固定長の文字コードじゃないと無理だと思う。

例えば、
扱う文字が限定されているとか、
ファイルで使う文字コードが決まってるとか
なにか他に限定する条件が必要。

この課題を素直に解釈すると、
ファイルの bit ストリームを、3bit ずつ区切るか、
ファイルの byte ストリームを、3byte ずつ区切るか
して「一つの符号」とする。

1) 出現回数をカウントして
2) 二分木を構築する。
3) 構築した二分木から bit 列 → 「一つの符号」の対応テーブルをファイルに出力。
4) 作成した二分木をつかって、入力の「一つの符号」を順番に bit 列に変換しながら、ファイルに出力して、入力の「一つの符号」がなくなるまで繰り返す。

おしまい。

あと、必要な知識は、

二分木
http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8

連結リストは、二分木の前提知識
http://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88

ハフマン符号化の為の、
- 「一つの符号」
- 出現回数
- 左右の子の接点の合計
をノードの属性として含めて、構造体かクラスにする。
クラスにするなら、二分木の操作をクラス関数に含める。

構造体
http://ja.wikipedia.org/wiki/%E6%A7%8B%E9%80%A0%E4%BD%93

クラス
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%A9%E3%82%B9_%28%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%29

ノードのソート
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

ハフマン符号化プログラミング

「ハフマン符号化プログラム（３次拡大）を作成せよ。

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング