データの圧縮(3)～RSA暗号(1) - 小西研究室@電脳工房ＭＳＣ

第12回 データの圧縮(3)～RSA暗号(1)

---

前回の続きです。

---

課題3 （1月8日(水)　17:00　提出期限（厳守））　【全員対象問題】

以下の2つの問題を解き、解答だけではなく、途中の経過と共に、課題提出先([email protected])までメールで送信しなさい。
メール送信するとき、件名に自分の学籍番号を付けること。

---

【1】．活字データを圧縮するのに次のような方法を用いる。
　１文字を８ドット×８ドットのドットパターンで表し、ドットのないときW、あるときBを与える。そして、重複するとき、その文字の後に重複する個数を書く方法でデータを圧縮する。１文字の場合は、「W１」と書かずに単に「W」と書くことにする。

　たとえば、「Ａ」は、
　　　　WWWBBWWW　　　 →　W３B２W３
　　　　WWBBBBWW　　　 →　W２B４W２
　　　　WBBWWBBW　　　 →　WB２W２B２W
　　　　WBBWWBBW　　　 →　WB２W２B２W
　　　　WBBBBBBW　　　 →　WB６W
　　　　WBBWWBBW　　　 →　WB２W２B２W
　　　　WBBWWBBW　　　 →　WB２W２B２W
　　　　WWWWWWWW　　 →　W８　
として、改行を無視して連ねて、
W３B２W３W２B４W２WB２W２B２WWB２W２B２WWB６WWB２W２B２WWB２W２B２WW８
と表すことにする。
　このとき、次の圧縮データを解読し、何の文字であるかを答えよ。また、圧縮率（％にして、小数第２位を四捨五入しなさい）を求めよ。

(1). B２W３B２WBWBWBWBWBW２BW２BWBW５BWBW５BWBW５BWBW５BWW８

　　　　　　　　文字：　　　　　　　　　　　　　圧縮率：　　　　　　　％　

(2). WB２W３BWBW２BWBW２WB２WBW３W３BW４W２BWB２W２WBWBW２BWBW３B２W２W８

　　　　　　　　文字：　　　　　　　　　　　　　圧縮率：　　　　　　　％　

【2】．各文字が次の割合で出現しているものとする。

文字	出現確率
A	0.48
E	0.23
L	0.12
M	0.08
P	0.05
S	0.04
合計	1.00

上の表を用いて、ハフマン法を用いて、割合の大きい方に1ビットの「0」、少ない方に1ビットの「1」を付けてコード化をする。以下の問いに答えよ。

(1)． このとき、「SAMPLE」はどのような符号に変換されるか答えよ。

(2). ハフマン法で表現した時の平均ビット長を求めよ。
　　　　（ヒント：各文字のビットの長さに確率を掛けて加えたものが「平均ビット長」である。）

　　　　　　　　　　　　　　　　　　　　　　　　　　　(以上 2問)

---

今日の話題に感想を述べてください。（名前欄に学生番号を記入すること）　質問も結構です。必要に応じて、回答します。

• 暗号鍵と復号鍵の仕組みがよく分かりました。 -- 12130774 (2013-12-19 12:15:38)
• 授業の最後にやった「ユークリッドの互除法」が良く分かりませんでした。 -- 12131140 (2013-12-23 12:30:20)
• 課題できるだけ今日中にはお願いします。 -- 12131136 (2013-12-23 13:13:52)
• 課題はいつ出されるのでしょうか？早めにお願いします -- 12131154 (2013-12-24 12:56:18)
• 課題は何時出ますか？ -- 12100547 (2013-12-25 02:54:56)
• 課題はいつ出ますか？ -- 12131140 (2013-12-26 18:13:41)
• やっと課題が出ました。まあ、いままでの問題の復習です。ちんぷんかんぷんな人は、友人に聞くとかして、早めに解決して下さい。期末試験でも同じようなのが出ます。 -- 小西敏雄 (2013-12-26 18:24:50)
• 課題出たということで頑張りたいです -- 12134160 (2013-12-26 20:59:37)
• 今までの事を思い出しながら課題頑張ります -- 12121561 (2013-12-26 22:05:23)
• 先生ありがとうございます(*^^*)♪ -- 12120452 (2013-12-26 22:26:21)
• 課題をしっかりやっていきたいです。 -- 12120333 (2013-12-27 04:25:32)
• 課題頑張ります。 -- 12130536 (2013-12-27 09:54:41)
• 課題一生懸命取り組みます。 -- 12132841 (2013-12-27 18:59:31)
• ほぼ課題できたのですが、〔1〕の（1）の文字がいまいち分かりません。 -- 12131136 (2013-12-27 19:49:45)
• 分からなかった問題もできました！ -- 12131136 (2013-12-27 20:06:20)
• 課題提出しました！ -- １２１３４１６０ (2013-12-30 15:49:08)
• 課題、がんばります!!　 -- 12131154 (2013-12-30 20:35:27)
• 課題頑張ろうと思います -- 12122161 (2014-01-06 11:41:04)
• 課題をがんばりたいです -- 14131073 (2014-01-07 09:29:52)
• 課題をがんばります‼‼‼ -- 12130417 (2014-01-07 21:23:33)
• テストに向けて３つの圧縮方法をできるようにしたいです。 -- 12131017 (2014-01-07 21:57:43)
• 3つ目の圧縮方法は辞書を提示することが困難なので2つ目までで充分だと思います。 -- 小西敏雄 (2014-01-07 23:00:40)
• 今の時点で課題提出者は約80人です。明日の午後5時が期限です。まあ、頑張りに期待しますが… -- 小西敏雄 (2014-01-07 23:02:16)
• ようやく課題ができました　 -- 12124068 (2014-01-08 00:18:57)
• 課題の件名に間違えて学籍番号のみではなく名前も書いてしまったのですが問題ありませんか？ -- 12124068 (2014-01-08 00:21:08)
• 課題提出しました。かくにんお願いします。 -- 12122799 (2014-01-08 13:52:58)
• 小西敏雄先生!単位ください。 -- 12114067 (2014-01-08 17:16:22)
• 課題は無事提出しました。 -- 12131306 (2014-01-08 18:03:02)
• 課題は約束通り5時が期限ですよ。 -- 小西敏雄 (2014-01-08 18:56:52)

---