文字列→ハフマン符号 ハフマン符号→文字列 のプログラムの組み方が分かりません。 具体的に教えてほしいところ: ・ハフマンツリー ・固定型ナントカ…って言うやつ ・可変型ナントカ…って言うやつ 申し訳御座いませんが、どうか御回答お願い致します。

MK_HUF KEY=4RK444JD ハフマン符号化と復号のコードです。 バイト単位のデータがないのでいろいろ不便です。 エンコード var v%[0] v%=h_utf16_to_huf(文字列) デコード var u16$=utf8_to_utf16(h_decode(v%,len(v%)*4)

（MIKIさんのコードちゃんとみれてないので説明だけ） ハフマン符号化のアルゴリズムそのものはwikipediaにあるとおりで、 補足するなら「文章中に出てくる回数が多い文字(プチコンの1文字＝16bit固定(UTF-16))を、可変ビット(文字の種類によって1bitから数bitに変化)に割り当てて、最初の文章より短くする」な感じです。 同じ文字が沢山繰り返されて１文字16bit使ってる文章があれば、その文字が1bitや2bitになればデータ量が少なくなるので圧縮できるという感じです。 可変bitに変換された結果は２進数のバイナリデータでしかなくて、 これを元の文章に戻すために、どの可変bitがどの文字に対応しているかの一覧をツリーにしたのがハフマンツリー 文字も画像データ１ドットも16bitや32bitのデータなので、同じように画像をハフマン符号化すると圧縮できるという仕組みです。

wikipediaの例だと 文字列 DAEBCBACBBBC は１２文字でプチコンだと１文字16bitなので192bit これをハフマン符号化すると それぞれの文字の数から A=110, B=0, C=10, D=1110, E=1111 とハフマンツリーを作って、これを元の文字列にあてはめて 1110 110 1111 0 10 0 110 10 0 0 0 10 となって 25bit ハフマンツリーも一緒にデータとして持っておかないと元の文字列に変換できないので、符号化した25bitのデータと一緒に保存しておく必要があります（どのように保存するかはプログラムやデータ形式次第） おもいっきりバイト単位(8bit)のビット操作なので、プチコンだとビット操作はできてもバイト単位が扱いづらいので、ちょっといろいろ大変なのです。(整数型32bitに４バイト(4x8bit)持つのが一般的)

Wikipediaと合わせて参照して分かりやすくなりました！ でもまだ聞くことがありそうなので開かせて頂きます。 このような子供のわがままを聞いてくださり有難う御座います。

ハフマンかどうか知らないけど多い文字に短い符号を当てる圧縮を前に作った。

ツララさん ハフマン符号実装したいってくらいの人だから、100の言葉より running code の方がいいかなと思って。 まあ解決したようでようございました。

色々な情報有難う御座います。 私の理解できていないところがわかりました。 ハフマンツリーを割り当てるソースの作り方が私はどうも理解できません。 原理は一応分かったのですが、こまざわさんやMIKIさんのソースコードを見ても理解できそうにありません。 また私の我が儘を聞かせてしまい申し訳御座いません。

ハフマンツリーとか気にせずにとりあえず何か「多い文字に短い符号を当てる」っていうのを作っても良いんじゃないかな。

running code principle バッサリ切り捨てられてて笑った ツララさん 回答したい人が好きなように回答すればいいと思います。 デタラメを撒き散らすような回答に対してはやめろといいますけどね。

> ハフマンツリーを割り当てる ツリーの実装方法が分からないってことかな?? 0を左、1を右として二分木を作ればいい。 二分木は例えば、配列 car[] を左のリンク、cdr[] を右のリンクとして、葉は car に文字を入れる約束にしとく。 110=A 0=B としたいなら cdr[root]=1 cdr[1]=2 car[2]="A" car[root]="B" ここで root は根っこ。 ツララさんも書いてるけど、質問するたびに謝らなくていいですよ

ツララさん» 1日前のコメントは読み返しても、Wikipediaを参照しても分からない、ということでした。 そして私も一度挑戦してみましたが、どうも上手くいかなくて…。

MIKIさん» 親切で明解な回答を有難う御座います。 つまりそれは、読み取ったビットが0の場合、”B”を得ることができ、1の場合、更にそこへ2→&B10を追加して110、よって"A"を得ることが出来る、ということでしょうか。

あまさとさん» 試してみます。

とりあえずAとBだけの文字列をハフマン符号らしきものに圧縮は出来ました。 出現回数の多いものに小さいBit、出現回数の少ないものに大きいBitを割り当てたつもりがRSORTではなくSORTになっていました。 でもなんとなく理解は出来てきたので解凍の方にも少しずつ手を出していきたいなと思っています。(現在圧縮の方のみ)

画像を貼るつもりが忘れていました。 余談ですが、 「はる」とうって予測変換したらパルケ・エスパーニャとか出てきました(笑)

そういうことです。 私は car[] cdr[] 使いましたが二分木の実装方法はこれに限らないので、ご自分の気に入った方法でどうぞ。 二分木を自在に操作できるようになったら、アキネーターっぽいのも作れるから試してみてね。

知らないことを知ろうとするときは、１つの情報(検索したページや本など)だけじゃなく、いろんな情報を参考にしてみるとそれぞれのページや本で違った見方からの情報があって、そこから自分なりに納得できる情報が導けるので、いろいろ調べてみるとですね。 ちなみにアルゴリズム系ならネットで調べるより図書館に行った方が詳しい情報がいろいろあるのでおすすめですよ（図書館で本のリクエストできるなら技術系がそろってる大きい書店で本を見つけてリクエストするのもありかも） アルゴリズムからプログラムを書く場合、必ずしもこのコードが正解ってのがあるわけではなくて、プログラムがアルゴリズム通りに動いていれば正解なので、自分なりに理解してコードを書いていろんなパターンのいじわるデータを入力をして動作してるかを試してみるのもです。

プログラムの作り方次第では使うかわからないけど、プチコンで可変ビット操作がめんどかったら、文字列に"0"と"1"を追加するのをビットだと思って操作するのがちょっと楽かもです。 保存時に数値変換など加工してしまえばいいので。 （相変わらずWiiU実機使えないのでMIKIさんのコードまだみれてないけど） 「car cdr lisp」で検索すると、なんでこの名前や目的なのかがちょっとわかったりも。 たんに「二分木」だと、枝が２本に分かれて、さらにまたそれぞれの枝が２本に分かれて、ってのを表すけど、 今回のハフマンについては、「２本分かれた先の片側（wikipediaのは右、MIKIさんのは左）は絶対に２本に分かれずに止まる」という性質があるのも、あんまり名言化されていなかったりするので、参考にするといいかもです（そうなるのとそうでないではまた作り方違うので）

文献は理系の大学図書館に行くとたくさんありますよ。 学生じゃなくても閲覧できたり貸し出しできるところもあるから調べてみてちょ。

私のコードは奥村先生の『C言語による最新アルゴリズム事典』のhuffman.c がベースです。 ここでソースコード一式配布してるので興味があれば確認してください。 https://oku.edu.mie-u.ac.jp/~okumura/algo/ ハフマン以外にも興味深いアルゴリズムが目白押しですよ。 この実装では葉の判定は car[i] cdr[i] で「i<256 なら葉」としています。 プチコンにそのまま応用するなら「i<65536 なら葉」とすればいいでしょう。

＞MIKIさん 教える側に取っても「いい質問」されるのは嬉しかったりしませんか？ 調べても分からない人を相手に、取っ掛かりをくれた人が居るのに枝葉については別に教えてくれる人が現れるまで待てっていうのは違うんじゃないかと。 再質問されたことで説明漏れが無いか調べ直したりとかしませんでした？ こういうやり取りが無駄で面倒くさいと思ってるなら別にいいですけど。

沢山の情報、有難う御座いました。 皆様の御恩は忘れません。 これにてこのトピックを閉じさせて頂きます。 有難う御座いました！