CodeIQ/リンゴ問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[アルゴリズム]]
*リンゴ問題 [#g5089bd2]
-codeIQで結城浩先生が出題されていた、リンゴ問題に挑戦し、...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*自分なりの解説 [#p88dd0e3]
-この問題はつまるところ「ハフマン符号化」を実装することに...
-特徴として以下のような時にハフマン符号化が使える
--文字列が予めわかっている
--その頻度もわかっており、頻度に偏りがある
-今回の問題の他の例としては、吉野家の注文方法がある
--注文を受けた店員は厨房に居るスタッフに注文を伝える
--例えば、豚丼大盛りなら「豚大」と伝えるが、牛丼大盛りの...
--牛丼屋なので、当然牛丼が注文されることが多い
--なので、多く使われる注文用語には「大」や「並」と行った...
--一方で、注文が滅多にされないものは、長い呼び名を割り当...
-今回のリンゴ問題で言えば、アルファベットの頻度に偏りがある
--TやEなんかは良く使われるが、X、ZやQなんかは滅多に使われ...
*肝心の「3値」ハフマン符号化 [#hecc204b]
-ハフマン符号化の手順はググレば出てくる
--簡単にまとめれば
++頻度の少ない「2つ」の状態をまとめて1桁の符号を割り当てる
++「2つ」の状態をまとめて1つの新しい状態とする
++頻出順に並べ替える
++1.に戻る
--である
-ハフマン符号化は一般的には「2値」のものを圧縮する符号化...
-というのも、前述のとおり、ハフマン符号化では、状態(ノー...
-符号が1桁長くなるたびに状態が2個ずつ減り、新しく1つ増...
-しかし、3値の場合は、符号が1桁長くなるたびに状態数が差...
-結果として、最後に3個残る必要があり、3個から2個ずつ増え...
-しかし、アルファベットは26文字=偶数のため、1文字ずらす(...
-やってみると分かるが、偶数のまま処理をして最後に2つの符...
--考えてみれば、最後に残る2つの符号は1桁で表せる符号なの...
-なので、最初のステップだけ、2つの状態をまとめて1つの新...
-参考サイト:[[結城浩さん (id:hyuki) 出題のリンゴ問題に挑...
-参考サイト:[[挑戦者求む!【アルゴリズム】リンゴ列をもっ...
終了行:
[[アルゴリズム]]
*リンゴ問題 [#g5089bd2]
-codeIQで結城浩先生が出題されていた、リンゴ問題に挑戦し、...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*自分なりの解説 [#p88dd0e3]
-この問題はつまるところ「ハフマン符号化」を実装することに...
-特徴として以下のような時にハフマン符号化が使える
--文字列が予めわかっている
--その頻度もわかっており、頻度に偏りがある
-今回の問題の他の例としては、吉野家の注文方法がある
--注文を受けた店員は厨房に居るスタッフに注文を伝える
--例えば、豚丼大盛りなら「豚大」と伝えるが、牛丼大盛りの...
--牛丼屋なので、当然牛丼が注文されることが多い
--なので、多く使われる注文用語には「大」や「並」と行った...
--一方で、注文が滅多にされないものは、長い呼び名を割り当...
-今回のリンゴ問題で言えば、アルファベットの頻度に偏りがある
--TやEなんかは良く使われるが、X、ZやQなんかは滅多に使われ...
*肝心の「3値」ハフマン符号化 [#hecc204b]
-ハフマン符号化の手順はググレば出てくる
--簡単にまとめれば
++頻度の少ない「2つ」の状態をまとめて1桁の符号を割り当てる
++「2つ」の状態をまとめて1つの新しい状態とする
++頻出順に並べ替える
++1.に戻る
--である
-ハフマン符号化は一般的には「2値」のものを圧縮する符号化...
-というのも、前述のとおり、ハフマン符号化では、状態(ノー...
-符号が1桁長くなるたびに状態が2個ずつ減り、新しく1つ増...
-しかし、3値の場合は、符号が1桁長くなるたびに状態数が差...
-結果として、最後に3個残る必要があり、3個から2個ずつ増え...
-しかし、アルファベットは26文字=偶数のため、1文字ずらす(...
-やってみると分かるが、偶数のまま処理をして最後に2つの符...
--考えてみれば、最後に残る2つの符号は1桁で表せる符号なの...
-なので、最初のステップだけ、2つの状態をまとめて1つの新...
-参考サイト:[[結城浩さん (id:hyuki) 出題のリンゴ問題に挑...
-参考サイト:[[挑戦者求む!【アルゴリズム】リンゴ列をもっ...
ページ名: