構造的類似性を持つ半構造化文書における頻度分析山田泰寛* 池田大輔** 廣川佐千男** *九州大学大学院システム情報科学府 **九州大学情報基盤センター発表内容 • 背景 – 共通パタン特定 • 頻度分布 – 自然言語文 – 共通テンプレートを持つ半構造化文書群 • まとめ • 今後の課題背景 • 共通パタンの特定 – 文字列処理 • 最長共通部分文字列 • 最長共通部分列問題 – パタン言語の学習 • 与えられた例に共通するパタンの探索 – ゲノム • モチーフ発見 • 最大反復 – テキストの圧縮 • 頻出するパタンの予測計算量が高い情報抽出(Web マイニング) • ラッパー – コンテンツ抽出プログラム – 共通テンプレートを持つ文書群を対象 – 共通テンプレートの特定し、コンテンツを抽出するルールを生成目的 • 共通パタン特定の予備実験として頻度分析 – 自然言語文 – 構造的類似性（共通テンプレート）を持つ半構造化文書群 • 共通テンプレートを持つ半構造化文書群 – テンプレート部分とコンテンツ部分で構成 – コンテンツ部分は自然な文字列 • 頻度分布の差を用いた共通テンプレートの特定 – 部分文字列の出現頻度だけを使う – 計算量が小さい発表内容 • 背景 – 共通パタン特定 • 頻度分布 – 自然言語文 – 共通テンプレートを持つ半構造化文書群 • まとめと今後の課題テンプレートを持たないテキスト • 夏目漱石「こころ」 – 487KByte V(f) n : 部分文字列の長さ f : 出現頻度 V(f) :出現頻度 f を持つ部分文字列の種類数 n f テンプレートを持たないテキストべき分布に従う種類数 V(f) 頻度 f テンプレートを持たないテキストジップの第２法則テキスト中の単語の頻度分布、特に低頻度部分において、頻度がfである単語の種類数V(f)は頻度fとの間に以下の関係が成り立つ log V(f) = - a (log f) + b 種類数 V(f) 頻度 f 共通テンプレートを持つテキスト • 産経新聞 – 50ファイル – 328KByte V(f) n f テンプレートを持たないテキスト • 夏目漱石「こころ」 – 487KByte V(f) n : 部分文字列の長さ f : 出現頻度 V(f) :出現頻度 f を持つ部分文字列の種類数 n f 共通テンプレートを持つテキスト • 産経新聞 – 50ファイル – 328KByte V(f) n f 頻度分布の差 (a) テンプレート部分 (b) コンテンツ部分共通テンプレートを持つテキスト f vs. V(f) 種類数 V(f) 頻度 f テンプレートを持たないテキスト f vs. V(f) 種類数 V(f) 頻度 f 共通テンプレートを持つテキスト f vs. V(f) べき分布からの乖離する点の出現種類数 V(f) 頻度 f 頻度分析 • グラフ1 – 部分文字列の長さ n – 出現頻度 f – 出現頻度 f を持つ部分文字列の種類数 V(f) • グラフ2 – 出現頻度 f – 出現頻度 f を持つ部分文字列の種類数 V(f) • グラフ3 – 出現頻度 f – 出現頻度 f を持つ部分文字列の全体の頻度 f * V(f) テンプレートを持たないテキスト夏目漱石「こころ」 f vs. f * V(f) 頻度 f*V(f) 頻度 f 共通テンプレートを持つテキストピークが出現 • 産経新聞 – 50ファイル５０ファイル数頻度 f*V(f) １００ファイル数の２倍頻度 f まとめ共通テンプなしレート頻度分布あり f vs. V(f) べき分布べき分布からの乖離 f vs. f*V(f) ピークなしピークあり今後の課題 • 共通パタンの発見 – べき分布からの外れの数値化 • 他データへの応用 – ゲノム参考論文 • 文字列の頻度分布による共通パタン発見, 池田大輔, 山田泰寛, 廣川佐千男, 第72回情報学基礎研究会, 2003年9月29,30日 – テンプレート発見問題の定義 – f vs. f * V(f) yahooの検索結果 f vs. f * V(f) ４６全ファイルに共通頻度 f*V(f) カテゴリ名９１９１３検索結果頻度 f ノイズを含む入力九州大学６２トップページから深さ３まで 598ファイル頻度 f 頻度62の部分文字列を持つページ複数のテンプレート f vs. F(f) １４０１０４４９，５０産経：５０朝日：１０４読売：１４０部分文字列の長さによる頻度の差 (a) 長さ 2 (b) 長さ 5