定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻 k単語近接検索について 定兼邦彦　今井浩 東京大学理学系研究科 情報科学専攻

内容 k 単語の近接検索(proximity search)の 時間アルゴリズム 平面走査アルゴリズムの検索速度の実験 平面走査による方法 分割統治による方法 平面走査アルゴリズムの検索速度の実験 htmlファイル 185MB

背景 電子化された文書の普及 WWW, メール 新聞, 辞書, 書籍 ゲノムデータベース 大量の文書からの検索 文書のランキングが必要

文書のランキング 検索結果が多い場合に重みをつける キーワードの重要度 参照回数 近接検索 (proximity search) tf*idf法 参照回数 近接検索 (proximity search)

Proximity Search キーワードが近くに現れている場所を探す 狭い範囲に全てのキーワードが含まれているならそこは有益な情報を含むと考える

問題の定義(Proximity Search) 問題1 (naive proximity search) 入力: k 種類の単語のテキスト T[1..N] での出現位置(合計 n 個) 出力: 全ての単語の出現位置を含む　　　テキスト中の区間 [l,r] （区間は、幅 r-l の小さい順にならべる） 区間内の単語の出現順は任意

既存研究 Manber, Baeza-Yates 91 Gonnet, Baeza-Yates, Snider 92 メモリ Gonnet, Baeza-Yates, Snider 92 距離 d 以内の2単語を 時間 Aref, Barbara, Johnson, Mehrotra 95 距離 d 以内の k 単語の列挙を 時間

既存の方法の問題点 ３単語以上の場合に良いアルゴリズムがない ２単語用のアルゴリズムを繰り返す 本研究 単語間の距離 d を決めておく必要がある 距離 d 以内の単語の組は　　　　　 個 答えの数が多くなる 本研究 ３単語以上で効率のよいアルゴリズムを提案 「極小」なもののみ求める

本研究の方法 k 単語を含む極小な区間の列挙を 時間 区間の最大値 d の制限はない メモリ ２つのアルゴリズム 平面走査アルゴリズムの拡張 分割統治法

極小性 定義1 k 単語を含む区間が極小　　　　別の区間を含まない A B C 極小 A B C 極小ではない A B C 極小

naive proximity searchの問題点 検索結果に冗長なものが入る 極小ではない区間を含む 極小: 他の区間を含まない区間 区間の数が 個ある 問題2 (proximity search) naive proximity searchにおいて、極小な区間 のみを幅の狭い順に求める 極小な区間は n 個未満

アルゴリズム(平面走査) 各単語の出現位置のリストをソート 各リストの先頭のものを取り出しソートし 区間 [l,r] を求める 区間の左端の単語を取り除き、同じ単語をリストから取り出す。空なら 6 へ。 区間と単語の順序を更新し、3へ。 ヒープの中の区間をソートして出力

例 A B C A B A C B A C 現在の区間は極小ではない 次のAは現在の区間に含まれる 次のAは現在の区間に含まれる 左端の単語を捨て、同じ単語を入れる

計算量 定理1: k 種類、合計 n 個の単語の出現位置が与えられたとき、問題2 (proximity search)は 時間でできる。 証明: 出現位置のソート: 出現位置のリストのマージ: 極小な区間のソート:

分割統治による方法 単語の位置をソートする必要がない 定理2: 最も少ない単語の頻度が l のとき、m 個の 極小な区間は 時間。 ある単語の頻度が小さいときに有効 定理2: 最も少ない単語の頻度が l のとき、m 個の 極小な区間は 時間。

アルゴリズム(分割統治) n 個の単語の位置の中間値 v を求める。 単語の位置を v より小さいもの(L)と大きいもの (R)に分ける。k 個の単語に対し L 中で最右のものと R 中で最左のものを求める。 L, R 両方にまたがる区間を平面走査で求める。 L (R) が k 個の単語を全て含んでいればその中の区間を再帰的に求める。

例 中間値 A B C A B C L R R L A B C

実際的な高速化 出現位置は整数 radix sortを使う 区間の幅の最大値 d を設定する 区間の数の上限を設定する ヒープの根に幅が最大のものを入れ、 それより大きいものはヒープに入れない 区間の数の上限がない場合 区間を配列に入れておき最後にradix sort

検索速度の実験 データ マシン htmlファイル51,783個 テキストサイズ: 185Mバイト (１つは平均3.5KB) suffix arrayサイズ: 639Mバイト (91-95年の毎日新聞全記事 485Mバイト) マシン Sun Ultra60 UltraSPARC-II 360MHz, メモリ2GB, ディスク18GB

実装方法 平面走査アルゴリズム 位置のソートは基数 のradixソート 区間の幅の最大値は1000 区間の数は無制限

1キーワードの検索時間 個数に比例した時間 (radix sort) キーワード http www jp h t p e n 個数 283719 214524 319914 3747125 7304053 2610014 6939739 4371063 検索時間(秒) 0.698 0.505 0.778 2.333 4.721 1.820 4.410 2.752 個数に比例した時間 (radix sort)

極小な区間の検索時間 検索時間の約半分は極小な区間を求める時間 時間はキーワードの総数にほぼ比例 キーワード http www jp h t p e t h n キーワード数 818157 13661192 22361980 区間数 377405 3180532 4400220 検索時間(秒) 2.414 16.351 26.811 ソート以外 0.443 7.487 12.595 検索時間の約半分は極小な区間を求める時間 時間はキーワードの総数にほぼ比例

まとめ k 単語近接検索を 時間で行うアルゴリズムの提案 実際にはほぼ 時間 htmlファイルでの検索速度の実験 実際にはほぼ 時間 htmlファイルでの検索速度の実験 通常の検索では速度は問題ない

課題 分割統治アルゴリズムの実装、平面走査との比較 高次元への拡張(分割統治アルゴリズム) 計算量の下限を求める セブンイレブン、ローソン、ファミリーマートが近くにあるところを見つける 計算量の下限を求める