トピック
ぺぃ shiba_petitcom

文字列をハフマン符号に変換

文字列→ハフマン符号 ハフマン符号→文字列 のプログラムの組み方が分かりません。 具体的に教えてほしいところ: ・ハフマンツリー ・固定型ナントカ…って言うやつ ・可変型ナントカ…って言うやつ 申し訳御座いませんが、どうか御回答お願い致します。
1そうだね
プレイ済み
返信[1]
親投稿
MIKI ifconfig
MK_HUF KEY=4RK444JD ハフマン符号化と復号のコードです。 バイト単位のデータがないのでいろいろ不便です。 エンコード var v%[0] v%=h_utf16_to_huf(文字列) デコード var u16$=utf8_to_utf16(h_decode(v%,len(v%)*4)
1そうだね
プレイ済み
返信[2]
親投稿
(MIKIさんのコードちゃんとみれてないので説明だけ) ハフマン符号化のアルゴリズムそのものはwikipediaにあるとおりで、 補足するなら「文章中に出てくる回数が多い文字(プチコンの1文字=16bit固定(UTF-16))を、可変ビット(文字の種類によって1bitから数bitに変化)に割り当てて、最初の文章より短くする」な感じです。 同じ文字が沢山繰り返されて1文字16bit使ってる文章があれば、その文字が1bitや2bitになればデータ量が少なくなるので圧縮できるという感じです。 可変bitに変換された結果は2進数のバイナリデータでしかなくて、 これを元の文章に戻すために、どの可変bitがどの文字に対応しているかの一覧をツリーにしたのがハフマンツリー 文字も画像データ1ドットも16bitや32bitのデータなので、同じように画像をハフマン符号化すると圧縮できるという仕組みです。
1そうだね
プレイ済み
返信[3]
親投稿
wikipediaの例だと 文字列 DAEBCBACBBBC は12文字でプチコンだと1文字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に4バイト(4x8bit)持つのが一般的)
1そうだね
プレイ済み
返信[4]
親投稿
ぺぃ shiba_petitcom
Wikipediaと合わせて参照して分かりやすくなりました! でもまだ聞くことがありそうなので開かせて頂きます。 このような子供のわがままを聞いてくださり有難う御座います。
0そうだね
プレイ済み
返信[5]
親投稿
ハフマンかどうか知らないけど多い文字に短い符号を当てる圧縮を前に作った。
0そうだね
プレイ済み
返信[6]
親投稿
MIKI ifconfig
ツララさん ハフマン符号実装したいってくらいの人だから、100の言葉より running code の方がいいかなと思って。 まあ解決したようでようございました。
0そうだね
プレイ済み
返信[7]
親投稿
ぺぃ shiba_petitcom
色々な情報有難う御座います。 私の理解できていないところがわかりました。 ハフマンツリーを割り当てるソースの作り方が私はどうも理解できません。 原理は一応分かったのですが、こまざわさんやMIKIさんのソースコードを見ても理解できそうにありません。 また私の我が儘を聞かせてしまい申し訳御座いません。
0そうだね
プレイ済み
返信[8]
親投稿
ハフマンツリーとか気にせずにとりあえず何か「多い文字に短い符号を当てる」っていうのを作っても良いんじゃないかな。
1そうだね
プレイ済み
返信[9]
親投稿
MIKI ifconfig
running code principle バッサリ切り捨てられてて笑った ツララさん 回答したい人が好きなように回答すればいいと思います。 デタラメを撒き散らすような回答に対してはやめろといいますけどね。
2そうだね
プレイ済み
返信[10]
親投稿
MIKI ifconfig
> ハフマンツリーを割り当てる ツリーの実装方法が分からないってことかな?? 0を左、1を右として二分木を作ればいい。 二分木は例えば、配列 car[] を左のリンク、cdr[] を右のリンクとして、葉は car に文字を入れる約束にしとく。 110=A 0=B としたいなら cdr[root]=1 cdr[1]=2 car[2]="A" car[root]="B" ここで root は根っこ。 ツララさんも書いてるけど、質問するたびに謝らなくていいですよ
1そうだね
プレイ済み
返信[11]
親投稿
ぺぃ shiba_petitcom
ツララさん» 1日前のコメントは読み返しても、Wikipediaを参照しても分からない、ということでした。 そして私も一度挑戦してみましたが、どうも上手くいかなくて…。
0そうだね
プレイ済み
返信[12]
親投稿
ぺぃ shiba_petitcom
MIKIさん» 親切で明解な回答を有難う御座います。 つまりそれは、読み取ったビットが0の場合、”B”を得ることができ、1の場合、更にそこへ2→&B10を追加して110、よって"A"を得ることが出来る、ということでしょうか。
0そうだね
プレイ済み
返信[13]
親投稿
ぺぃ shiba_petitcom
あまさとさん» 試してみます。
0そうだね
プレイ済み
返信[14]
親投稿
ぺぃ shiba_petitcom
とりあえずAとBだけの文字列をハフマン符号らしきものに圧縮は出来ました。 出現回数の多いものに小さいBit、出現回数の少ないものに大きいBitを割り当てたつもりがRSORTではなくSORTになっていました。 でもなんとなく理解は出来てきたので解凍の方にも少しずつ手を出していきたいなと思っています。(現在圧縮の方のみ)
0そうだね
プレイ済み
返信[15]
親投稿
ぺぃ shiba_petitcom
画像を貼るつもりが忘れていました。 余談ですが、 「はる」とうって予測変換したらパルケ・エスパーニャとか出てきました(笑)
0そうだね
プレイ済み
返信[16]
親投稿
MIKI ifconfig
そういうことです。 私は car[] cdr[] 使いましたが二分木の実装方法はこれに限らないので、ご自分の気に入った方法でどうぞ。 二分木を自在に操作できるようになったら、アキネーターっぽいのも作れるから試してみてね。
0そうだね
プレイ済み
返信[17]
親投稿
知らないことを知ろうとするときは、1つの情報(検索したページや本など)だけじゃなく、いろんな情報を参考にしてみるとそれぞれのページや本で違った見方からの情報があって、そこから自分なりに納得できる情報が導けるので、いろいろ調べてみるとですね。 ちなみにアルゴリズム系ならネットで調べるより図書館に行った方が詳しい情報がいろいろあるのでおすすめですよ(図書館で本のリクエストできるなら技術系がそろってる大きい書店で本を見つけてリクエストするのもありかも) アルゴリズムからプログラムを書く場合、必ずしもこのコードが正解ってのがあるわけではなくて、プログラムがアルゴリズム通りに動いていれば正解なので、自分なりに理解してコードを書いていろんなパターンのいじわるデータを入力をして動作してるかを試してみるのもです。
1そうだね
プレイ済み
返信[18]
親投稿
プログラムの作り方次第では使うかわからないけど、プチコンで可変ビット操作がめんどかったら、文字列に"0"と"1"を追加するのをビットだと思って操作するのがちょっと楽かもです。 保存時に数値変換など加工してしまえばいいので。 (相変わらずWiiU実機使えないのでMIKIさんのコードまだみれてないけど) 「car cdr lisp」で検索すると、なんでこの名前や目的なのかがちょっとわかったりも。 たんに「二分木」だと、枝が2本に分かれて、さらにまたそれぞれの枝が2本に分かれて、ってのを表すけど、 今回のハフマンについては、「2本分かれた先の片側(wikipediaのは右、MIKIさんのは左)は絶対に2本に分かれずに止まる」という性質があるのも、あんまり名言化されていなかったりするので、参考にするといいかもです(そうなるのとそうでないではまた作り方違うので)
1そうだね
プレイ済み
返信[19]
親投稿
MIKI ifconfig
文献は理系の大学図書館に行くとたくさんありますよ。 学生じゃなくても閲覧できたり貸し出しできるところもあるから調べてみてちょ。
1そうだね
プレイ済み
返信[20]
親投稿
MIKI ifconfig
私のコードは奥村先生の『C言語による最新アルゴリズム事典』のhuffman.c がベースです。 ここでソースコード一式配布してるので興味があれば確認してください。 https://oku.edu.mie-u.ac.jp/~okumura/algo/ ハフマン以外にも興味深いアルゴリズムが目白押しですよ。 この実装では葉の判定は car[i] cdr[i] で「i<256 なら葉」としています。 プチコンにそのまま応用するなら「i<65536 なら葉」とすればいいでしょう。
1そうだね
プレイ済み
返信[21]
親投稿
ツララ LongIceSword
>MIKIさん 教える側に取っても「いい質問」されるのは嬉しかったりしませんか? 調べても分からない人を相手に、取っ掛かりをくれた人が居るのに枝葉については別に教えてくれる人が現れるまで待てっていうのは違うんじゃないかと。 再質問されたことで説明漏れが無いか調べ直したりとかしませんでした? こういうやり取りが無駄で面倒くさいと思ってるなら別にいいですけど。
0そうだね
プレイ済み
返信[22]
親投稿
ぺぃ shiba_petitcom
沢山の情報、有難う御座いました。 皆様の御恩は忘れません。 これにてこのトピックを閉じさせて頂きます。 有難う御座いました!
0そうだね
プレイ済み