検索システム

ユーザーの情報欲求の四段階

1. ユーザーが探すものを理解できていない状態
2. ユーザーが探すものを言語化できない状態
3. ユーザーが探すものを言語化できる状態
4. ユーザーが探すものの条件を検索システムのクエリやフィルタとして入力できる状態

1, 2, のユーザーは検索クエリを入力することができないため、彼らに対してはランキングやオススメ通知など受動的に情報を受け取れる方法を検討する。 3, 4, のユーザーは全文検索システムによるナビゲーションを検討する。

特に上級ユーザーには検索対象の項目ごとに検索ワードを指定できる詳細検索を提供してもよいが、システムとして複雑になってしまうことに注意する。

全文検索の分類

逐次検索

逐次検索 (grep) では、複数のデータを順次検索していくことで検索対象となる文字列を探し出す。

ある文字列の中から別の文字列を高速に検索するアルゴリズムには以下のようなものがある。

• BM (Boyer-Moore) 法
• KMP (Knuth-Morris-Pratt) 法

事前のインデックスを必要としないが、検索時に全ての検索対象を順次走査していくため検索対象の増加に伴って検索速度が低下する。 そのため、大抵の検索サービスでは後述のインデックス型検索が使われる。

インデックス型検索

インデックス型検索では、あらかじめ検索対象を走査しておき、高速な検索ができるようなインデックス (転置インデックス, 後述) を作成しておくことで検索時のパフォーマンスを向上させる。

以降、検索対象のことを文書 (document) と表記する。

転置インデックス

インデックス型検索のインデックスには転置インデックスが使われる。 転置インデックスは、単語に対してそれを含む文書集合を保持するデータ構造である。

並行処理

検索処理を高速に行うには、転置インデックスを複数のノードに分散配置し、並列で検索を行う。

転置インデックスの分割 (パーティショニング) 方法には以下の2通りがある。

文書分割方式 (document partitioning)

文書単位で分割する

文書単位で検索する → DAAT (Document At A Time)

単語分割方式 (term partitioning)

単語単位で分割する

単語単位で検索する → TAAT (Term At A Time)

転置インデックスを参照するキー (単語) のことをターム (term) という。

トークナイズ

文書に対して転置インデックスを作成するには、文書中に含まれる単語 (以下、トークン, token) を抜き出す必要がある。 文書に含まれる文をトークン単位で分解することをトークナイズ (tokenization, segmentation) という。

トークナイズを行う方法は以下の2つがある。

N-gram

• 一定の長さ ($N$) の文字列単位で分解する
• 特に $N=1$ のN-gramをuni-gram (ユニグラム), $N=2$ のN-gramをbi-gram (バイグラム), $N=3$ のN-gramをtri-gram (トライグラム) と呼ぶ
• $N$ 文字未満の文字列を検索できない
• 再現性に優れるが、適合率に劣る (ex. 京都 → 東京都)

形態素解析

• 意味をもつ最小単位 (形態素) の列に分解する
• 日本語の場合は、単語を空白で区切る (分かち書き) の習慣がないため、解析用の辞書が必須となる
• N-gramと比べてトークンの種類が少ない (転置インデックスが小さい分、検索が速い)
• 適合率に優れるが、再現率に劣る (例: チョコ → チョコレート にヒットしない)
• 日本語の代表的な形態素解析エンジンにMeCab, Kuromoji, Sudachi などがある

正規化

シノニム

予め辞書登録したシノニム (同義語, synonym) に基づいて単語を変換する (ex. 地下ドル → 地下アイドル)

ストップワード

ストップワード (stop word) は、検索の対象外となる単語のことであり、大半の文書に含まれている単語から構成される。 (ex. です, ます)

ステミング

ステミング (stemming, lemmatisation) は、形態素解析で抽出した単語の語形を辞書系にする処理のことである。 (ex. 会った → 会う, met → meet)

日本語の形態素解析や検索シノニム, ステミングで用いられる代表的な辞書に NEologd がある。 週2回で更新され、新語や固有名詞に強いという特徴がある。

検索結果の評価

検索システムを継続的に改善するために、検索結果にユーザーが求めるものがどれだけ含まれるかをフィードバックし、検索結果を定量的に評価する必要がある。

検索を「ある文書を検索結果に含めるかどうか」を決定する過程と考えると、検索は分類問題に帰着でき、検索結果は分類問題と同じように評価できる。

参考: 混同行列 - Wikipedia

以下、ユーザーが求める文書を正解文書と表記する。

適合率

適合率 (precision) は、検索結果が含む正解文書の割合であり、検索の正確性の指標である。

$$\text{precision}=\frac{\text{検索結果に含まれる正解文書}}{\text{検索結果}}=\frac{\text{TP}}{\text{TP}+\text{FP}}$$

再現率

再現率 (recall) は、正解文書が検索結果に含まれる割合であり、検索の網羅性の指標である。

$$\text{recall}=\frac{\text{検索結果に含まれる正解文書}}{\text{正解文書}}=\frac{\text{TP}}{\text{TP}+\text{FN}}$$

Fβ値

適合率と再現率はトレードオフの関係にあるため、検索結果の総合的な評価にはそれらの調和平均である Fβ値 (Fβ-measure) が主に用いられる。

$$\begin{aligned} F_\beta&=\dfrac{(1+\beta^2)\cdot\text{precision}\cdot\text{recall}}{(\beta^2\cdot\text{precision})+\text{recall}}\\ &=\dfrac{(1+\beta^2)\cdot\text{TP}}{(1+\beta^2)\cdot\text{TP}+\beta^2\cdot\text{FN}+\text{FP}} \end{aligned}$$

参考: F-score - Wikipedia

検索クエリのAND/OR

検索クエリに複数のタームが与えられたとき、それらを全て含む文書のみを検索結果に含める (AND検索) か、いずれかのワードを含む文書を検索結果に含める (OR検索) かの2通りがある。

文書のスコアリング

文書をスコアリングし、スコアに基づいてソートした検索結果を返すことで、特にユーザーが求めている (と考えられる) 文書を検索結果の上位に表示する。

TF-IDF

TF-IDFは文書に現れるタームの重要度を評価する文書のスコアリング手法の1つであり、文書 $D$ のスコアは次のように算出される。

$$\text{TF-IDF}=\frac{D\,\text{中のタームの出現回数}}{D\,\text{中のワードの総数}}\cdot\log\frac{\text{文書数}}{\text{タームを含む文書の数}}$$

クエリの提案

1. 検索を行う前に提案 (頻繁に検索されるキーワードのサジェスト)
2. 検索クエリの入力中に提案 (オートコンプリート)
3. 検索結果画面に表示に提案 (Google検索のもしかして機能など)

有名な全文検索システム

Apache Lucene

Java製のOSS検索ライブラリ。

Elasticsearch

LuceneベースのOSS全文検索システム。Elastic社が中心となり開発している。

Apache Solr

LuceneベースのOSS全文検索システム。

Algolia

BaaSの全文検索システム。API経由で利用できる。

TODO

• 検索システムの全体像
• Okapi BM25
• nDCG

参考文献

• Wikipedia, 全文検索
• Wikipedia, 文字列検索
• Wikipedia, tf-idf
• Wikipedia, Okapi BM25
• 山田 浩之, 検索エンジン自作入門～手を動かしながら見渡す検索の舞台裏, 2014
• 打田 智子他, ［改訂第3版］Apache Solr入門 ―オープンソース全文検索エンジン, 2017
• rilmayer, 図書館情報学オタクと学ぶ 検索エンジニア入門, 2020
• 守谷 純之介, 検索結果の品質向上Elasticsearch入門, 2019
• 高岡 一馬, Javaでつくる本格形態素解析器, 2017