オートマトンと言語

Size: px

Start display at page:

Download "オートマトンと言語"

きょういちこいまる
5 years ago
Views:

1 アルゴリズムとデータ構造 III 3 回目 : 月 3 日 ( 木 ) 暗号, 符号化, テキスト圧縮授業資料 3 授業の予定 ( 中間試験まで ) 0/07 スタック ( 後置記法で書かれた式の計算 ) 0/4 チューリング機械, 文脈自由文法 0/ 構文解析 Y 法 4 /04 構文解析 Y 法 5 / 構文解析 ( チャート法 ) 6 /8 構文解析 ( チャート法 ), グラフ ( ダイクストラ法, Pマッチング ) 7 /9 グラフ (* アルゴリズム,Pマッチング) 4 時限 -4 8 /5 グラフ ( Pマッチング ), 前半のまとめ 9 /0 中間試験授業の予定 ( 中間試験以降 ) /09 全文検索アルゴリズム (simple search, MP) /6 全文検索アルゴリズム (M, ho-orasick) 0/06 0/3 全文検索アルゴリズム (ho-orasick), データ圧縮暗号 ( 黄金虫, 踊る人形 ) 符号化 ( モールス信号, Zipf の法則, ハフマン符号 ) テキスト圧縮レポート出題 0/0 テキスト圧縮 (zip), 音声圧縮 (PM,MP3,LP), 画像圧縮 (PG) 0/03 期末試験レポート全文検索アルゴリズム (M) oyer-moore 法のプログラムを作成言語は何でも良いプログラムの説明データ text: 種類 : : ZYXWVUTSG ey: 種類 : : 結果表示 (4 種類の実験に対して ) キーワード出現位置 ( あれば複数 ) 照合回数締め切り : 月 0 日 ( 木 ) 7:00 提出場所 : 鈴木の居室 (3-54) 前のレポート入れ本日のメニュー世の中は不公平 Zipf の法則不公平を生かす暗号符号化モールス信号ハフマン符号テキスト圧縮世の中は不平等... だからおもしろい分布の偏り例 : 株取引, 麻雀, ブラックジャック自分だけが知っている ( つもりの ) の偏りを利用して得をする株価チャートを解読麻雀で山読みして勝つブラックジャックでカードカウンティングする試験で山を掛ける ( 張る ) 確率を無理やり変える偽情報を流して株価操作スティング ( 映画 ) のポーカー試験範囲を満遍なく勉強する ( 効果絶大 ) 授業中, 指名されないように下を向く ( 逆効果 )

2 ジップの法則 (Zipf s law) あるタイプの現象が生起する確率はその現象の生起する順位に反比例する : 経験則定数生起確率 = 順位 Zipfの法則が当てはまる事象毎の出現コンピュータにおけるコマンドの使用 Webページのアクセス都市の人口文献の参照回数会社でのランク ( 役職 ) と給料などケータイのシェア (docomo, au, softbank, e-mobile) 携帯電話 : 各グループ毎の加入者数累計 (009 年月ケータイ Watch より ) 順位 3 4 事業者 NTTドコモ I ソフトバンクイーモバイル累計 55,97,00 3,39,400,50,900,048,00 割合 ( 確率 ) 50.% 8.4% 9.5%.8% Zipf s law = % 5.5% 7.0%.8% 定数生起確率 = 順位順位自然言語の統計的性質の使用 ( 英語 ) _ はスペース前回はここまで % % 3 % 4 % _ 7.4 e_ 3.0 _th.6 _the. e 9.7 _t.4 the.3 the_.0 t 7.0 th.0 he_.3 _of_ 0.6 a 6. he.9 _of 0.6 and_ 0.4 o 5.9 _a.7 of_ 0.6 _and 0.4 i 5.5 s_.7 ed_ 0.5 _to_ 0.4 n 5.5 d_.5 _an 0.5 ing_ 0.3 の使用 (caesar より ) シーザー暗号 ( 解読 / 作成 ) プログラム T hal? O N 順位出現確率 R I S H T L 4 O N M 6 U R 80 G 7 I 30 P Y 8 S 0 W 9 V 0 H X L Z 順位出現確率 4 M U 0 6 G P Y W V X Z 順位単語 the of 3 and 単語の使用 to a in that % of the in the to the on the and the for the to be % one of the 0.5 as well as 0.3 the United States 0. out of the 0. some of the 0. the end of 0. the fact that % 単語の出現分布ジップの法則 (Zipf s law): 単語の出現順位 (r) と出現 (f) は反比例の関係にある r 順位出現確率 5/ 順位 f f the 5 n番目の単語の出現確率 P Pn n は定数低の語には当てはまらない r n of 3 and 4 to 5 a 6 in 7 that

データの分布の偏りを利用した技術暗号 ( 換字式 ) の解読小説 ( ポー, ドイルなど ) シーザー暗号データ圧縮 ( ロスレス ) キー入力時の打鍵回数の削減モールス符号ハフマン符号 ( 情報理論年前期宮本先生 ) 小説中での暗号解読の解説黄金虫 (The gold bug) 著者 : エドガーアランポー作品 : 翻訳版 http://www.aozora.gr.

3 データの分布の偏りを利用した技術暗号 ( 換字式 ) の解読小説 ( ポー, ドイルなど ) シーザー暗号データ圧縮 ( ロスレス ) キー入力時の打鍵回数の削減モールス符号ハフマン符号 ( 情報理論年前期宮本先生 ) 小説中での暗号解読の解説黄金虫 (The gold bug) 著者 : エドガーアランポー作品 : 翻訳版作品 : 原文踊る人形 (The dventure of the ancing Men) 著者 : アーサーコナンドイル作品 : 翻訳版題 : 暗号舞踏人の謎作品 : 原文黄金虫 ( エドガーアランポー ) に出てくる暗号 ( 換字式 ) 小説内で暗号解読暗号は多分英語英語はによって出現確率が違う出現確率の高い方から並べると e a o i d h n r s t u y c f g l m w b k p q x z (e は頻出 ) ee も頻出 the も頻出対応がとれたは置き換え, 前後のを推理する踊る人形アーサーコナンドイル (The dventure of the ancing Men) 人形の形暗号の元の言語旗頻出する形 M HR SLNY アルファベット英語単語の区切り What one man can invent another can discover. 携帯電話のアルファベットキー abc def ghi jkl mno pqrs tuv wxyz _ ehp tdy alw ofb ncv rmk iuxq sgjz _ 一般的なアルファベットキーアルファベット順に6 を8つのキーに割り振っている pqrsとwxyzは4 をつのキーに割り振られているキー配置による打鍵数の違い i h a v e a p e n 上下出現を考慮したアルファベットキー ( 鈴木考案 ) 出現が低いを入力するには複数回打鍵キーの場所を覚え直す必要おまけ Scrabble ( 英単語作成ボードゲーム ) の得点 Scrabble 対戦型英単語作成ゲームボード上に手持ちのをならべ英単語を作成作成した単語のに書かれている得点をし, 高得点を競う英単語を作りにくいには高得点が割り振られている. 点 :,, I, O, R, N, T, L, S, U... 0 点 :, Z 3

4 シフト暗号シーザー暗号 ROT3, ROT47 00 年宇宙の旅のHL IM ( 俗説?) 蛇足 aesar ( シーザー暗号法の解読 ) Unix のアプリケーション kki ではオンラインマニュアルはあるがプログラム自身はインストールされていない entos や Ubuntu では ( インストールすれば ) 使用可能 ( のはず ) 使用例 >caesar ibwf b qfo >I have a pen I have a pen をずらして入力各の出現を利用し, 何ずらしたかを推測し答えを出力する蛇足 ode talker ( 暗号通信兵 ) Windtalkers ( アメリカ映画 00 年 ) アメリカインディアンのナバホ族が暗号通信兵ナバホ族の言葉を使って暗号通信サイパン島での日本軍との戦いナバホ族の言葉文法も発音も独特 (native にしか理解できない ) 日本軍は知らないアメリカには native のナバホ族がいる ( 訓練しなくても理解できる ) 蛇足分布の偏りを推定勝つ! ブラックジャックのカードカウンティング映画 : レインマン (RIN MN) 映画 : ラスベガスをぶっつぶせ () 麻雀の山読み蛇足分布の偏りのデータ圧縮への利用モールス信号ハフマン符号モールス信号の符号 ( 短点 ) とー ( 長点 ) を用いてアルファベットを表現する情報を早く送るための工夫よく使われる ( 例えば e,t) は短い e: ( 短点 ) t: - ( 長点 ) あまり使われない ( 例えば q は 4 ) は長い q:

5 モールス信号の符号 ( 短点 ) とー ( 長点 : 短点 3 つ分の長さ ) を用いてアルファベットを表現する区切りの切れ目 : 短点 3 つ分の間隔単語の切れ目 : 短点 7 つ分の間隔 L: ー (Life カードの M に使われていた ) SOS: ーーーモールス信号の符号情報を早く送るための工夫よく使われる ( 例えば e,t) は短い e: ( 短点 ) t: - ( 長点 ) あまり使われない ( 例えば q は 4 ) は長い q: -- - ハフマン符号分木を使っての出現順に並べる葉 = 浅い : 符号長が短い, 深い : 符号長が長い平均符号長が最小になることが保証されているハフマン符号の作り方 / の低いを () を選び, の低い方を左の葉, の高い方を右の葉に置き, 分木をつくる. ルートノードにはつの葉のの和を書き込む () 0.5 ハフマン符号の作り方 /5 () 統合後, の低いと () 連合を選ぶ. と () 連合のを比較し, の高いを右ノードに, 低い () 連合を左ノードに配置する. ルートノードにはの和を書き込む (()) ハフマン符号の作り方 3/5 (()) 統合後, の低いと (()) 連合を選ぶ. と (()) 連合のを比較し, の高い (()) 連合を右 0.35 ノードに, 低いを左ノードに配置する. ルートノードにはの和を書き込む 5

6 ハフマン符号の作り方 4/5 ((())) 0.60 ((())) 統合後, の低いと ((())) 連合を選ぶ. と ((())) 連合のを比較し, の高い ((())) 連合を右ノードに, 低いを左ノードに配置する. ルートノードにはの和を書き込むハフマン符号の作り方 5/5 左のノードに 0, 右のノードにを付与する符号ハフマン符号の変換符号 Z SII コード (8bit) からハフマン符号へ符号 SII: (0x4) 8bit Huffman: 0 : bit SII: (0x45) 8bit Huffman: 0 : bit 練習問題下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. 練習問題解答例 0/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. 6

7 練習問題解答例 /7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. 練習問題解答例 /7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. ( ) 0.0 練習問題解答例 3/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. 練習問題解答例 4/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. ( ) 0.9 (( )) 0.8 (( )) 0.8 練習問題解答例 5/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. 練習問題解答例 6/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. ((( ))) ( ) (( ) ) ((( )))

8 練習問題解答例 7/7 下の表のようなの出現のとき, ハフマン符号をつくりなさい. 但しハフマン符号作成のための二分木も書くこと. コードハフマン符号の特徴各がリーフノード ( 葉 ) に対応しているハフマン符号列を左からトレースすることで, の区切りが分かる区切りを入れる必要がない平均符号長エントロピーの良い近似レポート全文検索アルゴリズム (M) oyer-moore 法のプログラムを作成言語は何でも良いプログラムの説明データ text: 種類 : : ZYXWVUTSG ey: 種類 : : 結果表示 (4 種類の実験に対して ) キーワード出現位置 ( あれば複数 ) 照合回数締め切り : 月 0 日 ( 木 ) 7:00 提出場所 : 鈴木の居室 (3-54) 前のレポート入れ 8

Microsoft PowerPoint - アルデIII 13回目01月12日 [互換モード]

Microsoft PowerPoint - アルデIII 13回目01月12日 [互換モード] アルゴリズムとデータ構造 III 13 回目 :1 月 12 日 ( 木 ) 暗号, 符号化, テキスト圧縮授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/algorithm3/ 授業の予定 ( 中間試験まで ) 1 10/06 スタック ( 後置記法で書かれた式の計算 ) 2 10/13 チューリング機械, 文脈自由文法 3 10/20 構文解析