篠原 歩，石野 明 東北大学情報科学研究科 竹田 正幸 九州大学システム情報科学研究院 下薗 真一，坂本 比呂志 九州工業大学情報工学部

Presentation on theme: "篠原 歩，石野 明 東北大学情報科学研究科 竹田 正幸 九州大学システム情報科学研究院 下薗 真一，坂本 比呂志 九州工業大学情報工学部"— Presentation transcript:

1 篠原 歩，石野 明 東北大学情報科学研究科 竹田 正幸 九州大学システム情報科学研究院 下薗 真一，坂本 比呂志 九州工業大学情報工学部
非明示的表現に対する アルゴリズムの開発 Ａ０９班 計算の対象が明示的に与えられるのではなく， それを生成する文法や論理式，数式などを用いて 非明示的に表現されて与えられたときに，それを効率よく処理するアルゴリズムの開発と計算量の解析を行う． 篠原　歩，石野　明 　　　　東北大学情報科学研究科 竹田　正幸 　　　九州大学システム情報科学研究院 下薗　真一，坂本　比呂志　　九州工業大学情報工学部

2 フィボナッチ文字列abaababaabaababaabaababaの さまざまな表現
f0 = b f1 = a fn = fn-1・ fn-2　（n≥2)  6 4 1 b a 2 7 3 5 漸化式，文法 f2=ab f3=aba f4=abaab f5=abaababa f6=abaababaabaab f7=abaababaabaababaababa OBDD風 方程式 compress gzip bzip2 : 圧縮 アルゴリズムの効率のよさや問題の計算量は通常，入力長に対する関数として評価される．したがって，問題の対象をどのように表現するか大きく依存する．例えば，単純な文字列照合問題を例にとってみても，入力となる文字列が圧縮された形式で与えられたとすると，そのためのアルゴリズムの開発や計算量の評価は全く違ったものとなる．本研究では，このような着想を一般化し，計算の対象が明示的に与えられるのではなく，それを生成する文法や論理式，数式などを用いて非明示的に表現されて与えられたときに，それを効率よく処理するアルゴリズムの開発と計算量の解析を行うことを目的とする．同時に，効率のよいアルゴリズムの開発に適した非明示的な表現法そのものについて，文字列やグラフなどの離散構造に力点をおいて研究を展開する．

3 BW変換すると b9a15 になる bzip2で 圧縮しやすい abaababaabaababaabaababa
aabaababaabaababaabaabab aababaabaababaabaababaab abaabaababaabaababaabaab abaababaabaababaabaababa ababaabaababaabaababaaba baabaababaabaababaabaaba baababaabaababaabaababaa babaabaababaabaababaabaa BW変換すると b9a15　になる bzip2で 圧縮しやすい

4 フィボナッチ文字列はbzip2でよく縮む b1a1 b1a2 b2a3 b3a5 b5a8 b8a13 f2=ab f3=aba
BW変換 f2=ab f3=aba f4=abaab f5=abaababa f6=abaababaabaab f7=abaababaabaababaababa b1a1　 b1a2　 b2a3　 b3a5 b5a8　 b8a13　　 BW逆変換

5 OBDDで表現された文字列に対する 圧縮パターン照合 [DLT2004]
テキストの圧縮表現 パターンの圧縮表現 b a O(n2m)時間 節点数n b a 節点数m 圧縮パターン照合 アルゴリズム 出現位置は{6} 愚直に適用すると O(2m + 2n)時間かかる 仮想の世界 O(M+N)時間 abaababaabaababa パターン照合 アルゴリズム … 長さN abaababaabaababa abaabaab abaabaab 長さM

6 OBDD ⋍ MPMG  SLP OBDD X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1
T = abaababa x3 x２ x1 b a X2 X3 X1 a b X4 X5 X6 X7 X8 OBDD

7 T = (aaab)n Good Compression for Repetitive Text a X1 b X2 X6 X7 X3 X4

8 Example of MPM Grammar T = abaabababbaba X1 = a X2 = b X3 = X1 X2

9 OBDDで表現された文字列に対する 圧縮パターン照合 [DLT2004]
テキストの圧縮表現 パターンの圧縮表現 b a O(n2m)時間 節点数n b a 節点数m 圧縮パターン照合 アルゴリズム 出現位置は{6} 愚直に適用すると O(2m + 2n)時間かかる 仮想の世界 O(M+N)時間 abaababaabaababa パターン照合 アルゴリズム … 長さN abaababaabaababa abaabaab abaabaab 長さM

10 一般の文章から回文はほとんど見つからない
回文の検出 第７回日本ことば遊び・回文コンテスト最優秀作品 出涸らしに　求める駄菓子　噛む夫婦 昔語る目　共に白髪で 英語の回文 　　A Santa lived as a devil at NASA 著者名-作品名 文字数 長さ6以上の回文 芥川 竜之介-戯作三昧 23815 1 平林 初之輔-文学方法論 20896 宮本 百合子-一連の非プロレタリア的作品 19180 最低限の回文の長さを入れる． 回文の作者を明記する． ５７５７７の非常に面白い回文であると紹介する． 一般の文章から回文はほとんど見つからない 10

11 rev(SL)とSRのレーベンシュタイン距離が2
近似回文 レーベンシュタイン回文の例　（誤り2） SL ニ ハ タ ラ イ テ イ ツ タ ハ ン ニ SR 反転 イ ラ タ ハ ニ rev(SL) に働いて行った犯人（青空文庫より） rev(SL)とSRのレーベンシュタイン距離が2 誤りkのすべてのレーベンシュタイン回文を検出するO(k2n)時間アルゴリズム 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　[Porto et.al.2002] 誤りkのすべてのハミング回文を検出するO(kn)時間アルゴリズム 11 11

12 Webテキストからの近似回文検出 レーベンシュタイン回文検出アルゴリズムの適用 HTMLテキスト
<h1>「竹やぶ」焼けた。</h1> HTMLタグの除去 漢字かなテキスト 「竹やぶ」焼けた。 MeCabにより変換 かなテキスト 「タケヤブ」ヤケタ。 濁音等を清音に置換 清音かなテキスト 「タケヤフ」ヤケタ。 HTMLから記号除去テキストまでのプロセスは省略して表示． 前処理が必要であることを説明すればよい． カナと長音以外の記号を除去 記号除去かなテキスト タケヤフヤケタ レーベンシュタイン回文検出アルゴリズムの適用 12

13 Webアプリケーションの実装 検索語を入力，誤りと長さを指定 回文検出位置を強調表示 13 入力：検索語
出力：検索語を含むページから検出した回文（検索語を含むとは限らない） ハイライト表示を実際に検索して出てきたページにする． 13 13

14 ただし，ハミング回文の方が対応を見つけやすい
レベンシュタイン回文の検出結果 著者-作品名 文字数 誤0長6 誤1長7 誤2長8 芥川 竜之介-戯作三昧 23815 1 9 26 平林 初之輔-文学方法論 20896 11 39 宮本 百合子-一連の非プロレタリア的作品 19180 8 28 検出した誤り2の回文 回文に対応する原文 イセントトウヨウニトンテイ ヨクノカツシンシツノヒヨ シヨトクノチヨチクトシシ ンノシヨシヨシヨウエン 以前と同様に富んでいる 窮極のかつ真実の標準 所得の貯蓄と支出 自分の処女上演 誤りとか正しい文字の長さの部分がつながって見づらい． 実際，ここでは何文字の回文を検出したのかを明示する． 「リリカルなもの」の回文は繰り返し文字がカットされているのでよろしくない． より多くの回文を検出することができた ただし，ハミング回文の方が対応を見つけやすい 14 14

15 圧縮文字列を展開せずに回文検出 a b a a b a b a w wR, wcwR 入力： SLP
出力：すべての極大な回文の位置を 　　　　簡潔に表した構造 　　 X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X3 X4 X7 = X5 X5 X8 = X6 X7 SLP a　b　a　a　b　a　b　a O(n4)時間O(n2)領域アルゴリズム n : SLPの行数

16 a b a a b a b a 未解決 圧縮文字列を展開せずにスクエア検出 w w 入力： SLP
出力：すべてのスクエアの位置を 　　　　簡潔に表した構造 　　 X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X3 X4 X7 = X5 X5 X8 = X6 X7 SLP a　b　a　a　b　a　b　a 入力が通常のテキストならば O(n)時間で見つかることが知られている

17 フィボナッチ文字列の中の繰り返し構造 4回以上は繰り返さない 部分文字列　　　　　　　　　　は どれだけ繰り返す？ 部分文字列　　　　　　　　　　　は どこにある？

18 n-ボナッチ文字列の繰り返し構造 -ボナッチi定数 中の 繰り返し回数 [F.Mignosi ら, 1992] 回 回 = 2 + φ
　　　　中の　 の繰り返し回数　 回 回 = 2 + φ 黄金比 ビリヤードワードの図は書き直しだな… -ボナッチi定数

19 フィボナッチ文字列の一般化 フィボナッチ トリボナッチ n-ボナッチ

20 ひらめき☆ときめきサイエンス ～ようこそ大学の研究室へ～ KAKENHI （研究成果の社会還元・普及事業，日本学術振興会）
アナウンス ひらめき☆ときめきサイエンス ～ようこそ大学の研究室へ～　KAKENHI （研究成果の社会還元・普及事業，日本学術振興会） 「アルゴリズムを体感しよう 　----- ロボットプログラミングを通じて –-----」 平成１９年８月７日（火）　予定 東北大学　青葉山キャンパス 受講生　高校生１０名を募集予定