CodeIQ/リンゴ問題

アルゴリズム

リンゴ問題†

• codeIQで結城浩先生が出題されていた、リンゴ問題に挑戦し、無事解けたので、自分なりの解説を書いてみる
• なお、問題の詳細はこちら
• 結城先生のCodeIQのページはこちら&note{codeiq-hyuki:CodeIQの問題に挑戦しよう！, 2013-04-02更新, 2013-05-28閲覧};

自分なりの解説†

• この問題はつまるところ「ハフマン符号化」を実装することにある
• 特徴として以下のような時にハフマン符号化が使える
  • 文字列が予めわかっている
  • その頻度もわかっており、頻度に偏りがある
• 今回の問題の他の例としては、吉野家の注文方法がある
  • 注文を受けた店員は厨房に居るスタッフに注文を伝える
  • 例えば、豚丼大盛りなら「豚大」と伝えるが、牛丼大盛りの場合は「大」だけになる
  • 牛丼屋なので、当然牛丼が注文されることが多い
  • なので、多く使われる注文用語には「大」や「並」と行った短い呼び方を割り当てる
  • 一方で、注文が滅多にされないものは、長い呼び名を割り当てる
• 今回のリンゴ問題で言えば、アルファベットの頻度に偏りがある
  • TやEなんかは良く使われるが、X、ZやQなんかは滅多に使われない

肝心の「３値」ハフマン符号化†

• ハフマン符号化の手順はググレば出てくる
  • 簡単にまとめれば
  1. 頻度の少ない「２つ」の状態をまとめて1桁の符号を割り当てる
  2. 「２つ」の状態をまとめて１つの新しい状態とする
  3. 頻出順に並べ替える
  4. 1.に戻る
  • である
• ハフマン符号化は一般的には「２値」のものを圧縮する符号化なので、「３値」（３色のリンゴ）を使って圧縮する場合はちょっと注意が必要。
• というのも、前述のとおり、ハフマン符号化では、状態（ノード）２つをまとめて新しい一つの状態（ノード）にする
• 符号が１桁長くなるたびに状態が２個ずつ減り、新しく１つ増える（＝差し引き１つ減る）
• しかし、3値の場合は、符号が１桁長くなるたびに状態数が差し引き２つ減る。
• 結果として、最後に3個残る必要があり、3個から2個ずつ増えていく=奇数である必要がある。
• しかし、アルファベットは26文字=偶数のため、1文字ずらす（増やす）工夫が必要になる。
• やってみると分かるが、偶数のまま処理をして最後に２つの符号が残ると、結果として、平均符号長が長くなってしまう
  • 考えてみれば、最後に残る２つの符号は1桁で表せる符号なので、それが３つから２つに減ってしまうと、それは平均長に大きな影響を及ぼしてしまう。
• なので、最初のステップだけ、２つの状態をまとめて１つの新しい状態にする必要がある。

• 参考サイト：結城浩さん (id:hyuki) 出題のリンゴ問題に挑戦した - vim 初心者のメモと開発中の pukiwiki.vim について&note{hyuki-synga:結城浩さん (id:hyuki) 出題のリンゴ問題に挑戦した - vim 初心者のメモと開発中の pukiwiki.vim について, 2013-04-28発表, 2013-05-09閲覧};
• 参考サイト：挑戦者求む！【アルゴリズム】リンゴ列をもっと短く！ by The Essence of Programming 結城 浩│CodeIQ&note{huffman-apple-yuki-hiroshi-codeiq:挑戦者求む！【アルゴリズム】リンゴ列をもっと短く！ by The Essence of Programming 結城 浩│CodeIQ, 2013-04-01出題, 2013-04-22締切, 2013-04-22閲覧};

最新の20件