k - 東京大学

k単語近接検索について
定兼邦彦今井浩
東京大学理学系研究科
情報科学専攻
1
内容
• k 単語の近接検索(proximity search)の
O(n log n) 時間アルゴリズム
– 平面走査による方法
– 分割統治による方法
• 平面走査アルゴリズムの検索速度の実験
– htmlファイル 185MB
2
背景
• 電子化された文書の普及
– WWW, メール
– 新聞, 辞書, 書籍
– ゲノムデータベース
• 大量の文書からの検索
– 文書のランキングが必要
3
文書のランキング
• 検索結果が多い場合に重みをつける
– キーワードの重要度
• tf*idf法
– 参照回数
– 近接検索 (proximity search)
4
Proximity Search
• キーワードが近くに現れている場所を探す
• 狭い範囲に全てのキーワードが含まれているなら
そこは有益な情報を含むと考える
5
問題の定義(Proximity Search)
問題1 (naive proximity search)
• 入力: k 種類の単語のテキスト T[1..N] で
の出現位置(合計 n 個)
• 出力: 全ての単語の出現位置を含む
テキスト中の区間 [l,r]
• （区間は、幅 r-l の小さい順にならべる）
• 区間内の単語の出現順は任意
6
既存研究
• Manber, Baeza-Yates 91
○ 距離 d 以内の2単語の数を O (log
× O (dn) メモリ
n) 時間で求める
• Gonnet, Baeza-Yates, Snider 92
– 距離 d 以内の2単語を O((n1  n2 ) log n1 )) 時間
• Aref, Barbara, Johnson, Mehrotra 95
– 距離 d 以内の k 単語の列挙を O ( n 2 ) 時間
7
既存の方法の問題点
• ３単語以上の場合に良いアルゴリズムがない
• ２単語用のアルゴリズムを繰り返す
– 単語間の距離 d を決めておく必要がある
2
– 距離 d 以内の単語の組は O(d ) 個
– 答えの数が多くなる
本研究
３単語以上で効率のよいアルゴリズムを提案
「極小」なもののみ求める
8
本研究の方法
•
•
•
•
k 単語を含む極小な区間の列挙を O(n log n) 時間
区間の最大値 d の制限はない
O (n) メモリ
２つのアルゴリズム
– 平面走査アルゴリズムの拡張
– 分割統治法
9
極小性
定義1
k 単語を含む区間が極小
A B C
別の区間を含まない
極小
A B A C 極小ではない
A B B C 極小
10
naive proximity searchの問題点
• 検索結果に冗長なものが入る
– 極小ではない区間を含む
– 極小: 他の区間を含まない区間
– 区間の数が n(n  1) / 2 個ある
問題2 (proximity search)
naive proximity searchにおいて、極小な区間
のみを幅の狭い順に求める
極小な区間は n 個未満
11
アルゴリズム(平面走査)
1 各単語の出現位置のリストをソート
2 各リストの先頭のものを取り出しソートし
区間 [l,r] を求める
3 区間 [l,r] が極小ならヒープに入れる
4 区間の左端の単語を取り除き、同じ単語をリストか
ら取り出す。空なら 6 へ。
5 区間と単語の順序を更新し、3へ。
6 ヒープの中の区間をソートして出力
12
例
次のAは現在の区間に含まれる
A B C
A B A C
B A C
左端の単語を捨て、同じ単語を入れる
現在の区間は極小ではない
13
計算量
• 定理1: k 種類、合計 n 個の単語の出現位置
が与えられたとき、問題2 (proximity search)
は O(n log n) 時間でできる。
• 証明:
– 出現位置のソート:
O(n log n)
– 出現位置のリストのマージ: O(n log k )
– 極小な区間のソート:
O(n log n)
14
分割統治による方法
• 単語の位置をソートする必要がない
– ある単語の頻度が小さいときに有効
定理2: 最も少ない単語の頻度が l のとき、m 個の
極小な区間は O(n log l  lk log k  m log m) 時間。
15
アルゴリズム(分割統治)
1 n 個の単語の位置の中間値 v を求める。
2 単語の位置を v より小さいもの(L)と大きいもの (R)
に分ける。k 個の単語に対し L 中で最右のものと
R 中で最左のものを求める。
3 L, R 両方にまたがる区間を平面走査で求める。
4 L (R) が k 個の単語を全て含んでいればその中の
区間を再帰的に求める。
16
例
中間値
A B
L
A B A C
B A C
L
C
B A C
B A
B A C
R
R
17
実際的な高速化
• 出現位置は整数 radix sortを使う
• 区間の幅の最大値 d を設定する
• 区間の数の上限を設定する
– ヒープの根に幅が最大のものを入れ、
それより大きいものはヒープに入れない
• 区間の数の上限がない場合
– 区間を配列に入れておき最後にradix sort
18
検索速度の実験
• データ
– htmlファイル51,783個
テキストサイズ: 185Mバイト (１つは平均3.5KB)
suffix arrayサイズ: 639Mバイト
– (91-95年の毎日新聞全記事 485Mバイト)
• マシン
– Sun Ultra60
– UltraSPARC-II 360MHz, メモリ2GB, ディスク18GB
19
実装方法
•
•
•
•
平面走査アルゴリズム
16
位置のソートは基数 2 のradixソート
区間の幅の最大値は1000
区間の数は無制限
20
1キーワードの検索時間
キーワード
http
www
jp
h
t
p
e
n
個数検索時間(秒)
283719
0.698
214524
0.505
319914
0.778
3747125
2.333
7304053
4.721
2610014
1.820
6939739
4.410
4371063
2.752
個数に比例した時間 (radix sort)
21
極小な区間の検索時間
キーワード
http www jp
htp
ethn
キーワード数
818157
13661192
22361980
区間数検索時間(秒) ソート以外
377405
2.414
0.443
3180532
16.351
7.487
4400220
26.811
12.595
検索時間の約半分は極小な区間を求める時間
時間はキーワードの総数にほぼ比例
22
まとめ
• k 単語近接検索を O(n log n) 時間で行う
アルゴリズムの提案
• 実際にはほぼ O (n) 時間
• htmlファイルでの検索速度の実験
– 通常の検索では速度は問題ない
23
課題
• 分割統治アルゴリズムの実装、平面走査との比較
• 高次元への拡張(分割統治アルゴリズム)
– セブンイレブン、ローソン、ファミリーマートが近くにある
ところを見つける
• 計算量の下限を求める
24

Download Report