[WP]no.009 ハフマン符号作成

1時間半くらいで作成

エントロピー符号の一種だそう
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7

実行結果(hotsoupprocessor):

c 01100011 0000000000000000000000000010010
e 01100101 0000000000000000000000000010011
h 01101000 0000000000000000000000000010101
o 01101111 0000000000000000000000000000110
p 01110000 0000000000000000000000000001011
r 01110010 0000000000000000000000000001110
s 01110011 0000000000000000000000000001111
t 01110100 0000000000000000000000000001000
u 01110101 0000000000000000000000000010100

多分このコードで大丈夫。
例えば、1→0→1→0→1(h)→0→1→1(o)→0→0→0→1(t)という解釈。


#const MAXLN 50

msg="hotsoupprocessor"
;msg="asdfghjklqwertyu"

dim data,200,3 // 生成用の木
dim lopen,MAXLN// 選択中の要素
dim char,100 // 割り当て文字
cn=0 // 文字の種類数
n=0 // 木要素数
ln=0 // 選択中の要素数

dim tmp,256

repeat strlen(msg) // 文字の出現回数を数える
tmp.peek(msg,cnt)++
loop
i=0
repeat 256
if (tmp.cnt==0):continue // 1度も出現しなかったら無視
char.i=cnt
data.i.0=tmp.cnt // 出現数=出現確率
i++
loop

cn=i
ln=i // 値が確定する
n=i

// 選択要素初期化
repeat cn
lopen.cnt=cnt
loop

dim min,2
repeat
//await 10
if (ln<=1):break // 要素が1つになったら終了

// 出現確率最小の要素2つ
min.0=data.(lopen.0).0>data.(lopen.1).0 : min.1=(min.0)^1
repeat ln-2,2
if (data.(lopen.cnt).0<data.(lopen.(min.1)).0){
if (data.(lopen.cnt).0<data.(lopen.(min.0)).0){
min.1=min.0
min.0=cnt
}else{
min.1=cnt
}
}
loop

// 統合
data.n.0 = data.(lopen.(min.0)).0 + data.(lopen.(min.1)).0
data.n.1 = lopen.(min.0)
data.n.2 = lopen.(min.1)
//選択中の要素からmin.0,min.1を消去してnを追加
//かなりややこしく書いてる
if ((min.0)!=(ln-1)){
lopen.(min.0)=n
lopen.(min.1)=lopen.(ln-1)
}else{
lopen.(min.1)=n
}
n++:ln-- // 木の要素は1つ増え、選択中要素は1つ減る
loop

if ln<=0:dialog"ln<=0":stop //一応念のため

data.(lopen.0)=1 // 符号を1文字セット

repeat ;n
if (ln<=0):break // 全て走査したら終了
i=lopen.0 // 選択
// 選択したものを削除
ln--
lopen.0=lopen.ln

j=data.i.1// 子
k=data.i.2// もう片方の子
data.j.0=((data.i.0)<<1)|0 // 片方の子には文字0を
data.k.0=((data.i.0)<<1)|1// もう片方の子には文字1を加える
if (j>=cn):lopen.ln=j:ln++ // 末端でなければ選択中リストに加える
if (k>=cn):lopen.ln=k:ln++ // おなじく
loop

// 表示
repeat cn
i=cnt
t=strf("%c ",char.i)
u=""
repeat 8
u=""+(((char.i)&(1<<cnt))>>cnt)+u
loop
t=t+u
u=""
repeat 31
u=""+(((data.i.0)&(1<<cnt))>>cnt)+u
loop
t=t+" "+u
mes t
loop

stop

後日解説・コメントもう少し増やします
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : HSP3 アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1467位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>