構造的類似性を持つ半構造化文書
における頻度分析
山田泰寛* 池田大輔** 廣川佐千男**
*九州大学大学院システム情報科学府
**九州大学情報基盤センター
発表内容
• 背景
– 共通パタン特定
• 頻度分布
– 自然言語文
– 共通テンプレートを持つ半構造化文書群
• まとめ
• 今後の課題
背景
• 共通パタンの特定
– 文字列処理
• 最長共通部分文字列
• 最長共通部分列問題
– パタン言語の学習
• 与えられた例に共通するパタンの探索
– ゲノム
• モチーフ発見
• 最大反復
– テキストの圧縮
• 頻出するパタンの予測
計算量が高い
情報抽出(Web マイニング)
• ラッパー
– コンテンツ抽出プログラム
– 共通テンプレートを持つ文書群を対象
– 共通テンプレートの特定し、コンテンツを抽出する
ルールを生成
目的
• 共通パタン特定の予備実験として頻度分析
– 自然言語文
– 構造的類似性(共通テンプレート)を持つ半構造化文
書群
• 共通テンプレートを持つ半構造化文書群
– テンプレート部分とコンテンツ部分で構成
– コンテンツ部分は自然な文字列
• 頻度分布の差を用いた共通テンプレートの特定
– 部分文字列の出現頻度だけを使う
– 計算量が小さい
発表内容
• 背景
– 共通パタン特定
• 頻度分布
– 自然言語文
– 共通テンプレートを持つ半構造化文書群
• まとめと今後の課題
テンプレートを持たないテキスト
• 夏目漱石「こころ」
– 487KByte
V(f)
n : 部分文字列の長さ
f : 出現頻度
V(f) :出現頻度 f を持つ部分文字列の種類数
n
f
テンプレートを持たないテキスト
べき分布に従う
種類数 V(f)
頻度 f
テンプレートを持たないテキスト
ジップの第2法則
テキスト中の単語の頻度分布、
特に低頻度部分において、頻度が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ファイル
50
ファイル数
頻度 f*V(f)
100 ファイル数の2倍
頻度 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)
46
全ファイルに共通
頻度 f*V(f)
カテゴリ名
91
913
検索結果
頻度 f
ノイズを含む入力
九州大学
62
トップページから深さ3まで
598ファイル
頻度 f
頻度62の部分文字列を持つページ
複数のテンプレート
f vs. F(f)
140
104
49,50
産経:50
朝日:104
読売:140
部分文字列の長さによる頻度の差
(a) 長さ 2
(b) 長さ 5
ダウンロード

発表資料 - 九州大学