[[アルゴリズム]]
*リンゴ問題 [#g5089bd2]
-codeIQで結城浩先生が出題されていた、リンゴ問題に挑戦し、無事解けたので、自分なりの解説を書いてみる
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hiroshi/q279]]
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/codeiq/]]¬e{codeiq-hyuki:[[CodeIQの問題に挑戦しよう！>http://www.hyuki.com/codeiq/]], 2013-04-02更新, 2013-05-28閲覧};
*自分なりの解説 [#p88dd0e3]
-この問題はつまるところ「ハフマン符号化」を実装することにある
-特徴として以下のような時にハフマン符号化が使える
--文字列が予めわかっている
--その頻度もわかっており、頻度に偏りがある
-今回の問題の他の例としては、吉野家の注文方法がある
--注文を受けた店員は厨房に居るスタッフに注文を伝える
--例えば、豚丼大盛りなら「豚大」と伝えるが、牛丼大盛りの場合は「大」だけになる
--牛丼屋なので、当然牛丼が注文されることが多い
--なので、多く使われる注文用語には「大」や「並」と行った短い呼び方を割り当てる
--一方で、注文が滅多にされないものは、長い呼び名を割り当てる
-今回のリンゴ問題で言えば、アルファベットの頻度に偏りがある
--TやEなんかは良く使われるが、X、ZやQなんかは滅多に使われない
*肝心の「３値」ハフマン符号化 [#hecc204b]
-ハフマン符号化の手順はググレば出てくる
--簡単にまとめれば
++頻度の少ない「２つ」の状態をまとめて1桁の符号を割り当てる
++「２つ」の状態をまとめて１つの新しい状態とする
++頻出順に並べ替える
++1.に戻る
--である
-ハフマン符号化は一般的には「２値」のものを圧縮する符号化なので、「３値」（３色のリンゴ）を使って圧縮する場合はちょっと注意が必要。
-というのも、前述のとおり、ハフマン符号化では、状態（ノード）２つをまとめて新しい一つの状態（ノード）にする
-符号が１桁長くなるたびに状態が２個ずつ減り、新しく１つ増える（＝差し引き１つ減る）
-しかし、3値の場合は、符号が１桁長くなるたびに状態数が差し引き２つ減る。
-結果として、最後に3個残る必要があり、3個から2個ずつ増えていく=奇数である必要がある。
-しかし、アルファベットは26文字=偶数のため、1文字ずらす（増やす）工夫が必要になる。
-やってみると分かるが、偶数のまま処理をして最後に２つの符号が残ると、結果として、平均符号長が長くなってしまう
--考えてみれば、最後に残る２つの符号は1桁で表せる符号なので、それが３つから２つに減ってしまうと、それは平均長に大きな影響を及ぼしてしまう。
-なので、最初のステップだけ、２つの状態をまとめて１つの新しい状態にする必要がある。
-参考サイト：[[結城浩さん (id:hyuki) 出題のリンゴ問題に挑戦した - vim 初心者のメモと開発中の pukiwiki.vim について>http://d.hatena.ne.jp/syngan/20130428/1367077800]]¬e{hyuki-synga:[[結城浩さん (id:hyuki) 出題のリンゴ問題に挑戦した - vim 初心者のメモと開発中の pukiwiki.vim について>http://d.hatena.ne.jp/syngan/20130428/1367077800]], 2013-04-28発表, 2013-05-09閲覧};
-参考サイト：[[挑戦者求む！【アルゴリズム】リンゴ列をもっと短く！ by The Essence of Programming 結城 浩│CodeIQ>https://codeiq.jp/ace/yuki_hiroshi/q279]]¬e{huffman-apple-yuki-hiroshi-codeiq:[[挑戦者求む！【アルゴリズム】リンゴ列をもっと短く！ by The Essence of Programming 結城 浩│CodeIQ>https://codeiq.jp/ace/yuki_hiroshi/q279]], 2013-04-01出題, 2013-04-22締切, 2013-04-22閲覧};
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
