概要
全文検索ソフトウェアであるSolrについて、自分用にまとめようと思いました。
Solr（ApachSolr）はオープンソースの全文検索ソフトウェアで、核となる部分はLucene（ルシーン）が使われており、Solr本体はJava言語で作られています。
全文検索とは
複数のドキュメントから、特定の文字列を検索すること。
大きく分けて逐次型と索引型の２つの手法があり、それぞれ以下のようになっています。
- 逐次型
文頭から特定の文字列を探す方法。先頭から一文字ずつ見て検索をします。
検索対象の文字が変化しても問題が起きにくく、事前の設定が不要であるメリットがあります。
ただし、ドキュメントの数が増えると、検索にかかる時間がどんどん増えてしまい、効率が悪くなります。 - 索引型
インデックス（転置インデックスともいう）から、特定の文字列を探します。
ドキュメントの数が多くても少なくても高速で検索することができます。
事前にドキュメントのインデックスが必要になります。
デメリットとして、検索対象の文字が変化すると、インデックスを書き直さなければ対応をすることができません。
一つのPC内のドキュメントや、ファイル内のテキストは規模が小さいとされ、逐次型で問題がないとされています。
また、組織内のすべてのドキュメントや、ニュースなどの特定のサービス、インターネット上のドキュメントなどは規模が大きいとされ、索引型が適しているとされています。
Solrは、索引型の検索を実行することができます。
転置インデックスの作られ方
インデックスの作成は、以下のように作られ方をします。
| ドキュメントID | ドキュメント |
|---|---|
| D1 | 明日の天気は雨のち曇りです |
| D2 | 今日の天気は晴れのち曇りです |
ドキュメントから単語を抽出して、以下の表のようになります。
| 明日 | 天気 | 雨 | 曇り | 今日 | 晴れ | |
|---|---|---|---|---|---|---|
| D1 | 1 | 1 | 1 | 1 | 0 | 0 |
| D2 | 0 | 1 | 0 | 1 | 1 | 1 |
単語で並び替えて転置します。
| D1 | D2 | |
|---|---|---|
| 明日 | 1 | 0 |
| 雨 | 1 | 0 |
| 今日 | 0 | 1 |
| 曇り | 1 | 1 |
| 天気 | 1 | 1 |
| 晴れ | 0 | 1 |
最後に、空間の最適化を行います。
| 単語 | ドキュメントID |
|---|---|
| 明日 | D2 |
| 雨 | D2 |
| 今日 | D1 |
| 曇り | D1, D2 |
| 天気 | D1, D2 |
| 晴れ | D1 |
これにより、「天気」というキーワードは両方のドキュメントにあり、「雨」というキーワードはD2にあるとすぐに分かるようになります。
日本語の文書の分割（トークナイザの動き）
検索エンジンの構成としてアナライザーがあり、アナライザーは文字フィルタ、トークナイザ、トークンフィルタで構成されています、
- 文字フィルタ
一文字ずつ正規化をする。 - トークナイザ
文書を単語に分割する。 - トークンフィルタ
不要な文字を除去したり、単語を正規化する。
例えば英語であれば、単語と単語の間にはスペースが挟まり、それぞれが単語だと識別することが容易になりますが、日本語の場合は単語間にスペースがない場合が殆どです。
このうち、単語として分割するトークナイザは、日本語を分割する場合は大きく２つの方法があります。
形態素解析
日本語辞書を使って、文書を単語に分割します。
インデックスのサイズが小さくなるため、実行時の処理が速く、検索結果のノイズが少ない特徴があります。
ただし、インデックスの作成に時間がかかり、分割するために使用する辞書が必要になります。また、検索漏れが発生する可能性があります。
現在は、この形態素解析を利用して分割をすることが一般的になっています。
- 形態素解析をする文書
私はﾒｶﾞﾈを1本だけ買った - 文字フィルタにより、半角文字を全角文字に変換
私はメガネを１本だけ買った - トークナイザにより、形態素解析を行う
私はメガネを１本だけ買った - トークンフィルタにより、不要な単語を除去し、類語を展開する
私メガネ眼鏡１本買う
形態素解析による検索漏れとして、例えば「革のショルダーバッグ」を「革 ショルダーバッグ」と分割した場合、「バッグ」で検索をしても検索にかかりません。「鞄」「カバン」でも勿論かかりません。
N-gram
機械的に、n文字単位で分割をする。
インデックスの作成が速く、辞書も不要で、基本的に検索漏れはありません。
ただし、インデックスのサイズが大きく、実行時の処理が遅くなり、検索結果にノイズが多いことも特徴です。
主に形態素解析と併用して使うことで、検索漏れを防ぐ目的で使用されます。
- 形態素解析をする文書
私はﾒｶﾞﾈを1本だけ買った - 文字フィルタにより、半角文字を全角文字に変換
私はメガネを１本だけ買った - トークナイザにより、2-gram(Bi-gram)で分割
私ははメメガガネネをを１１本本だだけけ買買っった
※N-gramにはトークンフィルタはありません。
N-gramの検索結果に入るノイズとしては、例えば「東京都港区赤坂」を「東京 京都 都港 港区 区赤 赤坂」と分割した場合、「京都」でも検索にかかってしまいます。
形態素
形態素解析で分解された単語で、これ以上分解したら言葉としての意味がなくなるというところまで文書を分解したものです。
分解に使う日本語の辞書として形態素辞書というものがあり、単語の品詞が何なにかや、その単語がどれだけ出現するか、品詞と品詞がどれだけ繋がりやすいかなどが設定されています。
その単語自身のコストと接続のコストを足して、元の文書を作り、文書の総コストが最も低い組み合わせを選択して分解をします。
「カードローンの」を形態素分解
| 単語 | 生起コスト（出現コスト） | 品詞 |
|---|---|---|
| カード | 4 | 名詞 |
| ローン | 6 | 名詞 |
| カー | 4 | 名詞 |
| ドローン | 24 | 名詞 |
| の | 2 | 助詞 |
| 品詞の組み合わせ | 生起コスト |
|---|---|
| 名詞＋名詞 | 1 |
| 名詞＋助詞 | 4 |
-
カードローンので分解をした場合
３つの単語を組み合わせたとき、「名詞＋名詞＋助詞」は「1 + 4 = 5」という連接コストになります。
また、それぞれの単語のコストが「6 + 6 + 2 = 14」となります。
これらを足したコストの19が総コストになります。 -
カードローンので分解をした場合
３つの単語を組み合わせたとき、「名詞＋名詞＋助詞」は「1 + 4 = 5」という連接コストになります。
また、それぞれの単語のコストが「6 + 24 + 2 = 32」となります。
これらを足したコストの37が総コストになります。
ドローンという単語はコスト24（出現しにくい）となっているため、上記の場合は１の組み合わせの方がコストの合計が低くなり、利用の対象となります。
このとき使用される日本語辞書に、追加でユーザー辞書を作成することで、検索の制度を上げることができます（「トート」という単語を登録して、「トートバッグ」を分解させるなど）。
ただし、すべての単語を登録することは難しく、意図しない分割がされる可能性も考慮しなければなりません。
検索結果の並びに関するアルゴリズム
検索結果に含まれるドキュメントを、計算式を用いてランキングにして、関連度の高い順に並び替えることをランキングと呼びます。
これはソート（50音順、日付順など）とは全く別物になります。
計算式には、いくつか有名なものがあります。
TF-IDF
ドキュメントにおける単語の重みを表現し、その単語がどれだけ出現するか、どれだけ希少性が高いかを算出します。
計算は、単語出現頻度と逆文書頻度で算出されます。
単語出現頻度(TF:TermFrequency)
tf(単語, ドキュメント) = 単語がドキュメントに出現した回数 / ドキュメント内のすべての単語数の和
例）「吾輩は猫である」の文書１の中に単語が106個あり、検索単語が「吾輩」で文書１中に2回出現をした場合
tf(吾輩, D1) = 2 / 106 = 0.018867924528301886...
逆文書出現頻度(IDF:InverseDocumentFrequency)
idf(単語) = log * 全ページ数 / 単語が出現したページ数
例）7ページある「吾輩は猫である」に、「吾輩」という単語が3回出現していた場合
idf(吾輩) = log * 7 / 3 =0.8472978603872037...
TF-IDF
tf-idf(単語, D1) = tf(単語, D1) * idf(単語)
例）「吾輩は猫である」の１ページ目における「吾輩」のTF-IDF
tfidf(吾輩. D1) = tf(吾輩, D1) * idf(吾輩) = (2 / 106) * (log * 7 / 3) = 0.01598675208277427...
ベクトル空間モデル(Vector space model)
検索文字列とドキュメントを空間座標に置いて、検索文字列と各ドキュメントのベクトル方向がどれだけ似ているかでランキングを算出します。
検索に用いられた単語と、検索された文書がどれだけ類似しているかを示す手法です。
つまり、どれだけ単語がヒットしても、関係のないドキュメントがランキングのトップに来たら困るという考えになります。
計算式で求められますが、上記よりも複雑な計算（sim(Di, Dj) = di * dj / || di || * || dj || など）になるため割愛します。
LinkPopularity(PageLink)
ウェブページのリンク・被リンクの関係を用いて算出します。
重要なドキュメントは、より多くの重要なドキュメントからリンクされているとして、それで文書の重要度を算出します。
ただし、むやみにリンク・被リンクされていても重要度が上がるわけではありません。
ランキング
TF-IDF、ベクトル空間モデル、LinkPopularityなどの複数のRankingFeature（素性）を組み合わせて、最良の検索結果を算出します。
Solrの核となっているLuceneでは、スコアリングという数値をRankingFeatureから算出して使用しています。
Sole5系以前はTF-IDFがデフォルトで使用されていましたが、Solr6系以降はBM25という計算式がデフォルトになっています。
BM25はTF-IDFを元に、単語の使用回数が多いだけで値が高くなることを抑制したものになります。
ランキングチューニング
ランキングを決めるアルゴリズムを調整して、質の高いドキュメントを上位に表示させる作業になります。
フィールドの重みを変更する方法や、Similarity（類似度）を変更する方法などがあります。
インデックスを常に更新・追加したり、日本語辞書に新しく単語を登録したりする事もチューニングの一環になります。
日本語辞書で、略語・同義語・外来語・表示ゆれ・送り仮名は、シノニム辞書というもので管理されていて、クエリを解釈するときやインデックスを作成する際に使用されます。
ただし、これらはメンテナンスコストが大きく、どのようにトークナイザされるかを正確に設定をしないと、せっかく登録したキーワードがただのノイズになってしまいます。
感想
概要としてはここまでとなります。
次回は実際にSolrを動かし、インデックスの扱いやリクエスト・レスポンス等についてまとめられれば良いなと思います。