第 7 章 リンク解析 111
9.3 検索
9.3 検索 135
!"#$%&'&
()*
+),
-./012&%&'&
./13&4%&'&
5678%&'&
9):
;)<
=
1. 負荷分散サーバーにクエリQが与えられる
2. もっとも負荷の低いマスターサーバーにクエリQが送信される
3. クエリQを解析し，検索条件C，単語インデックスQword，係り受けインデックスQdpnd を抽出する 4. C,Qword,QdpndをN台の検索サーバーに送信する
5. 各検索サーバーでC,Qword,Qdpndに適合する文書を検索し，クエリとの適合度を表すスコアを計算する 6. 検索により得られたスコア付き文書の集合をマスターサーバーへ返信する
7. 各検索サーバーからの返信された検索結果をマージし，スコアに従いソートする
8. 上位M件について，タイトル，URLなどをデータベースより獲得し，またファイルサーバーから標準フォーマットを読み 込み，スニペッツを生成する
9. 検索結果を負荷分散サーバーへ送る 10. 検索結果をユーザへ提示する
図9.7 検索の流れ
9.3.2.2 タームの重要度判定
検索クエリに対する言語解析結果およびWeb16億文を利用して求めた共起情報を利用して，クエリか ら抽出されたタームの重要度を決定する．TSUBAKIでは，語句の重要度として以下の3段階を設け，検 索での利用方法を区別する．
必須: 文書に含まれていなくてならない．さらに，必須の全表現がW 語以内という近接条件を課すこと も考えられる
任意: 文書に含まれていた方が良い
不要: 文書に含まれていても，いなくてもどちらでも良い
前節で述べたように，クエリ中の単語，同義語・句，係り受け関係がタームとして抽出されるが，各ター ムの重要度は，基本的には単語，同義語・句は必須，係り受けは任意として扱われる．しかしながら，固 有名詞（または「情報科学」のようなつながりの強い複合名詞）内の係り受け関係や，「シェイクスピアの 書いた本」における「書く」のような冗長的な動詞などが存在するため，このようなタームの重要度を変 更する．重要度の変更処理については論文[3]を参照されたい．簡単に述べると，文書の収集に必須表現 のみを，文書のスコアリングに必須表現，任意表現を利用し，不要表現は一切利用しない．
9.3 検索 137
表9.2 TSUBAKIで指定可能な検索制約
制約名 タグ名 説明 例
AND制約 ˜AND 必須タームが全て含まれていなければならない 京都大学˜AND
OR制約 ˜OR いずれかの必須タームが含まれている 京都大学˜OR
フレーズ制約 タグなし．‘¨’で囲む 既存の検索エンジンで使われているフレーズ検索に相当する ”京都大学” 係り受け制約 ˜FD クエリ中の全係り受けタームが含まれていなくてはならない 京都大学˜FD 近接制約（方向性無） ˜Nw 必須タームが，N語以内に現れている 京都大学˜20w 近接制約（方向性有） ˜NW 必須タームが，クエリ中の出現順で，N語以内に現れている 京都大学˜20W
9.3.2.3 検索制約
TSUBAKIでは，入力として与えられた複数個の検索クエリ間に，AND/ORの論理条件を適用して検
索することが可能であるが（一般に言われているAND検索・OR 検索に相当する），検索条件に加え，
検索クエリごとに制約を指定することも可能である．制約は，検索クエリの末尾に「˜制約を表す文字列」
を指定して表現する．表9.2にTSUBAKIで指定可能な検索制約を示す．
制約が指定された検索クエリを組み合わせて検索することも可能である．例えば，「”市バス” 京都大 学へのアクセス˜20W」とすることで，「市バス」というフレーズを含みかつ，「京都」，「大学」，「アクセ ス」が20単語以内現れている文書を検索することが可能である．
9.3.2.4 検索クエリの内部表現
検索クエリの内部表現としてS式を用いている．図9.8にクエリ「京都大学へのアクセス」の内部表現を 示す．S式は図9.9に示すフォーマットに従っている．図中のSTRICTは「必須」，OPTIONALは「任意」
を表す．FUNCは検索制約を表しておりPROX，ORDERED PROX，PHRASEは，近接制約（方向無），
近接制約（方向有），フレーズ制約をそれぞれ表す．またPROX，ORDERED PROXのみ，近接幅を OPTION としてとる．タームは (LABEL,T IMP,DF,BASIC NODE FLAG,T TYPEFEATURE) の6つ組で表現される．LABELは見出し，T IMPは重要度，BASIC NODE FLAGはタームが基本 ノードかどうか，T TYPEはタームのタイプ（単語（本文），係り受け（本文），単語（アンカー），係り受 け（アンカー）の4種類），FEATUREは検索対象とする素性を表す．素性の値は検索に考慮するブロッ クタイプをもとに求める．具体的には，利用するブロックタイプの値の和を用いており，例えば，メイン
テキスト(128)，タイトル(1)，ヘッダー(4)領域を検索に考慮する場合，素性の値は133となる．特に
指定がない場合，タイトル，キーワード，ヘッダー，フッター，メインテキスト，未判定領域が検索時に 考慮される．
9.3.3 文書のスコアリング
クエリと文書の関連度の計算にはOkapi BM25 [2]を利用する．多くの場合，Okapi BM25はクエリ中 の単語と文書の関連度を計算するために用いられるが，ここでは係り受け関係を考慮して関連度を計算で きるよう拡張する．Tqw をクエリqから抽出された単語ターム，同義表現タームの集合，Tqd を係り受け タームの集合としたとき，文書dとクエリqの関連度Rel(q, d)を以下の式で求める．
(PROX 100 (OR
((s9868:京都大学 1 405623 0 0 399)) (PROX 100
((京都->大学 1 229052 1 1 399)) ((京都 1 7642403 1 0 399)) ((大学 1 9380681 1 0 399)) )
) (OR
((アクセス 1 17474939 1 0 399)) ((s6583:接近 1 17474939 0 0 399)) )
)
((大学->アクセス 3 8860 1 1 399)) (OR
((s9868:京都大学 3 405623 0 2 1)) )
((京都->大学 3 229052 1 3 1)) ((京都 3 7642403 1 2 1)) ((大学 3 9380681 1 2 1)) (OR
((アクセス 3 17474939 1 2 1)) ((s6583:接近 3 17474939 0 2 1)) )
)) 図9.8 クエリのS式
Rel(q, d) = (1−α) %
t∈Tqw
BM(t, d) +α %
t∈Tqd
BM(t, d)
ここでαはスコアリングに係り受けタームをどの程度重視するかを調整するパラメータである．BM(t, d) は以下の式で定義される．
BM(t, d) = (k1+ 1)Fdt
K+Fdt × (k3+ 1)Fqt
k3+Fqt
w= logN−n+ 0.5
n+ 0.5 , K =k1((1−b) +b ld
lave
)
Fdt は文書d中でのtの出現頻度，Fqt はq中でのtの出現頻度，N は検索対象となっている文書数，n はq の文書頻度，ldはdの文書長（単語数），lave は平均文書長である．また，k1,k3,bはOkapiのパラ メータであり，k1= 1,k3= 0,b= 0.6としている．
9.3.4 スニペットの生成
検索クエリ中の単語，同義表現タームが最も近接して出現している領域に基づきスニペットを生成す る．具体的には，文書取得の際，インデックス引きすることで単語，同義表現タームが最も近接して出現
9.3 検索 139
ROOT→STRICT OPTIONAL STRICT→OPERATION EXP OPTIONAL→EXP∗
OPERATION→FUNC OPTION?
EXP→(OPERATION EXP)|TERM
FUNC→(AND| OR|PHRASE|PROX|ORDERED PROX) OPTION→Integer
TERM→LABEL T IMP DF BASIC NODE FLAG T TYPE FEATURE LABEL→String
T IMP→Integer DF→Integer
BASIC NODE FLAG→Integer T TYPE→Integer
FEATURE→Integer
図9.9 S式のフォーマット
している領域の左端（SL）と右端（SR）がわかるため，これらを利用する．検索結果に表示するスニペッ トのサイズ（単語数）Ssizeは設定ファイルで定義されており，SR−SLがSsizeより大きい場合はSL単 語目からSR単語目を，小さい場合はSL−(Ssize−(SR−SL))/2単語目からSR+ (Ssize−(SR−SL))/2 単語目をスニペットとする．
パラメータ 値 説明
query string 検索クエリ(utf8)をURLエンコードした文字列．検索結果を得る場合は必須．
start integer 取得したい検索結果の先頭位置．
results integer 取得したい検索結果の数．デフォルトは10． logical operator ANDOR 検索時の論理条件．デフォルトはAND．
only hitcount 0/1 ヒット件数だけを得たい場合は1，検索結果を得たい場合は0．デフォルトは0．
force dpnd 0/1 クエリ中の係り受け関係を全て含む文書を得たい場合は1，そうでない場合は0．デフォル
トは0．
snippets 0/1 スニペッツが必要な場合は1，スニペッツが不要な場合は0．デフォルトは0．
near integer クエリ中の単語と単語がn語以内に出現するという条件のもと検索を実行する(近接検索)． クエリ中の単語の出現順序は考慮される．
id string 個別の文書を取得する際の文書ID．オリジナルのWeb文書，または標準フォーマット形
式の文書を得る際は必須．
format htmlxml オリジナルのWeb文書，または標準フォーマット形式のWeb文書のどちらを取得するか
を指定．idを指定した際は必須．