Ａ０９班非明示的表現に対するアルゴリズムの開発計算の対象が明示的に与えられるのではなく，それを生成する文法や論理式，数式などを用いて非明示的に表現されて与えられたときに，それを効率よく処理するアルゴリズムの開発と計算量の解析を行う．篠原歩，石野明東北大学情報科学研究科竹田正幸九州大学システム情報科学研究院下薗真一，坂本比呂志九州工業大学情報工学部  フィボナッチ文字列abaababaabaababaabaababaのさまざまな表現 f0 = b f1 = a fn = fn-1・ fn-2 7 6 （n≥2) 漸化式，文法 f2=ab f3=aba f4=abaab f5=abaababa f6=abaababaabaab f7=abaababaabaababaababa 5 4 1 5 y x 2 2 1 a b 3 OBDD風方程式 compress gzip bzip2 : 圧縮 abaababaabaababaabaababa aabaababaabaababaabaabab aabaababaabaababaabaabab aabaababaabaababaabaabab aababaabaababaabaababaab aababaabaababaabaababaab aababaabaababaabaababaab abaabaababaabaababaabaab abaabaababaabaababaabaab abaabaababaabaababaabaab abaababaabaababaabaababa abaababaabaababaabaababa abaababaabaababaabaababa ababaabaababaabaababaaba ababaabaababaabaababaaba ababaabaababaabaababaaba baabaababaabaababaabaaba baabaababaabaababaabaaba baabaababaabaababaabaaba baababaabaababaabaababaa baababaabaababaabaababaa baababaabaababaabaababaa babaabaababaabaababaabaa babaabaababaabaababaabaa babaabaababaabaababaabaa BW変換すると b9a15 になる bzip2で圧縮しやすいフィボナッチ文字列はbzip2でよく縮む f2=ab BW変換 f3=aba f4=abaab BW逆変換 f5=abaababa f6=abaababaabaab f7=abaababaabaababaababa b1a1 b1a2 b2a3 b3a5 b5a8 b8a13 OBDDで表現された文字列に対する圧縮パターン照合 [DLT2004] テキストの圧縮表現節点数n パターンの圧縮表現 O(n2m)時間節点数m 圧縮パターン照合アルゴリズム a b a b 出現位置は{6} 愚直に適用すると O(2m + 2n)時間かかる仮想の世界 abaababaabaababa 長さN O(M+N)時間 1 2 3 4 5 6 7 8… パターン照合アルゴリズム abaabaab 長さM abaababaabaababa abaabaab OBDD ⋍ MPMG  SLP MPMG T = abaababa x3 x２ X8 x２ X6 x1 x1 x1 a OBDD b X3 X7 X4 X5 X5 X1 X2 X1 X1 X2 X1 X2 X1 a b a a b a b a X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X3 X4 X7 = X5 X5 X8 = X6 X7 Good Compression for Repetitive Text T = (aaab)n X7 X7 X6 X6 X5 X3 X5 X4 X1 X1 X1 X2 X1 X1 X1 X2 X1 X1 X1 X2 X1 X2 a a b a b X3 a a X4 a b X3 X5 X3 a X4 X5 a a X4 a b Example of MPM Grammar MPMG X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X2 X2 X7 = X3 X4 X8 = X5 X5 X9 = X6 X3 X10 = X7 X8 X11 = X9 X2 X12 = X10 X11 T = abaabababbaba X12 X10 X11 X7 X3 X8 X4 X5 X9 X5 X6 X3 X1 X2 X1 X1 X2 X1 X2 X1 X2 X2 X1 X2 X2 a b a a b a b a b b a b a OBDDで表現された文字列に対する圧縮パターン照合 [DLT2004] テキストの圧縮表現節点数n パターンの圧縮表現 O(n2m)時間節点数m 圧縮パターン照合アルゴリズム a b a b 出現位置は{6} 愚直に適用すると O(2m + 2n)時間かかる仮想の世界 abaababaabaababa 長さN O(M+N)時間 1 2 3 4 5 6 7 8… パターン照合アルゴリズム abaabaab 長さM abaababaabaababa abaabaab 回文の検出第７回日本ことば遊び・回文コンテスト最優秀作品出涸らしに求める駄菓子噛む夫婦昔語る目共に白髪で英語の回文 A Santa lived as a devil at NASA 著者名-作品名芥川竜之介-戯作三昧平林初之輔-文学方法論宮本百合子-一連の非プロレタリア的作品長さ6以上の文字数回文 23815 20896 19180 一般の文章から回文はほとんど見つからない 1 1 0 近似回文レーベンシュタイン回文の例（誤り2） SL ニハタライテイツタハンニ反転 SR イラタハニ rev(SL) に働いて行った犯人（青空文庫より） rev(SL)とSRのレーベンシュタイン距離が2 誤りkのすべてのレーベンシュタイン回文を検出するO(k2n)時間アルゴリズム [Porto et.al.2002] 誤りkのすべてのハミング回文を検出するO(kn)時間アルゴリズム 11 Webテキストからの近似回文検出 HTMLテキスト <h1>「竹やぶ」焼けた。</h1> HTMLタグの除去漢字かなテキスト「竹やぶ」焼けた。 MeCabにより変換かなテキスト「タケヤブ」ヤケタ。濁音等を清音に置換清音かなテキスト「タケヤフ」ヤケタ。カナと長音以外の記号を除去記号除去かなテキストタケヤフヤケタレーベンシュタイン回文検出アルゴリズムの適用 Webアプリケーションの実装検索語を入力，誤りと長さを指定回文検出位置を強調表示 13 レベンシュタイン回文の検出結果著者-作品名文字数芥川竜之介-戯作三昧 23815 20896 19180 平林初之輔-文学方法論宮本百合子-一連の非プロレタリア的作品誤0長6 誤1長7 1 1 0 9 11 8 誤2長8 26 39 28 検出した誤り2の回文回文に対応する原文イセントトウヨウニトンテイ以前と同様に富んでいるヨクノカツシンシツノヒヨ窮極のかつ真実の標準シヨトクノチヨチクトシシ所得の貯蓄と支出ンノシヨシヨシヨウエン自分の処女上演より多くの回文を検出することができたただし，ハミング回文の方が対応を見つけやすい 14 圧縮文字列を展開せずに回文検出 w wR, wcwR • 入力： SLP • 出力：すべての極大な回文の位置を簡潔に表した構造 SLP X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X3 X4 X7 = X5 X5 X8 = X6 X7 a b a a b a b a O(n4)時間O(n2)領域アルゴリズム n : SLPの行数圧縮文字列を展開せずにスクエア検出 ww • 入力： SLP • 出力：すべてのスクエアの位置を簡潔に表した構造 SLP X1 = a X2 = b X3 = X1 X2 X4 = X1 X1 X5 = X2 X1 X6 = X3 X4 X7 = X5 X5 X8 = X6 X7 a b a a b a b a 入力が通常のテキストならば O(n)時間で見つかることが知られているフィボナッチ文字列の中の繰り返し構造 4回以上は繰り返さない部分文字列どこにある？は部分文字列どれだけ繰り返す？は n-ボナッチ文字列の繰り返し構造中の繰り返し回数回 [F.Mignosi ら, 1992] 回= 2+φ 黄金比中のの繰り返し回数 -ボナッチi定数フィボナッチ文字列の一般化フィボナッチトリボナッチ n-ボナッチひらめき☆ときめきサイエンス～ようこそ大学の研究室へ～ KAKENHI （研究成果の社会還元・普及事業，日本学術振興会）「アルゴリズムを体感しよう ----- ロボットプログラミングを通じて –-----」平成１９年８月７日（火）予定東北大学青葉山キャンパス受講生高校生１０名を募集予定