【Solr入門】Full-text Search・Inverted Index・TF-IDF・BM25を解説
はじめに
Apache Solrを学び始めると、次のような用語をよく見かけます。
- Full-text Search
- Inverted Index
- Tokenization
- Stemming
- Stop Words
- TF-IDF
- BM25
本記事では、実際の例を交えながら解説します。
Full-text Searchとは
Full-text Search（全文検索）は、文章の内容を対象に検索する仕組みです。
例えば以下のデータがあるとします。
| ID | Content |
|---|---|
| 1 | I love playing football |
| 2 | Football is the most popular sport |
| 3 | I enjoy watching movies |
ユーザーが
football
と検索した場合、
Doc1
Doc2
がヒットします。
SQLのLIKE検索との違い
通常のSQLでは、
SELECT *
FROM articles
WHERE content LIKE '%football%';
のように検索できます。
しかし、
- データ量が増えると遅い
- 関連度による並び替えができない
- 単語の活用形を考慮できない
- 自然言語検索に弱い
という問題があります。
Solrでは検索用のインデックスを作成し、高速かつ高精度な検索を実現します。
Inverted Indexとは
全文検索エンジンの心臓部となる仕組みです。
通常の保存方法
例えば以下の文書があるとします。
Doc1 -> football basketball
Doc2 -> football tennis
Doc3 -> tennis golf
通常は
Document → Words
という形で保存されます。
Inverted Index
検索エンジンでは逆に保存します。
football -> Doc1, Doc2
basketball -> Doc1
tennis -> Doc2, Doc3
golf -> Doc3
つまり、
Word → Documents
の形式です。
これを Inverted Index（転置インデックス）と呼びます。
なぜ高速なのか
ユーザーが
football
と検索すると、
football -> [Doc1, Doc2]
を見るだけで済みます。
全データを走査する必要がありません。
Tokenizationとは
Tokenization（トークン化）は文章を単語単位に分割する処理です。
例えば、
Apple iPhone 15 Pro Max
を分割すると、
apple
iphone
15
pro
max
になります。
Solrでの流れ
Original Text
↓
Tokenization
↓
Tokens
検索エンジンは文章そのものではなく、トークンを保存して検索します。
Stemmingとは
単語を語幹（Stem）に変換する処理です。
例えば、
play
playing
played
plays
を
play
に統一します。
なぜ必要なのか
文書:
I am playing football
検索:
play
Stemmingが無い場合、
play ≠ playing
となりヒットしない可能性があります。
Stemmingを適用すると、
playing → play
となり検索可能になります。
Stop Wordsとは
出現頻度が高く検索にあまり意味を持たない単語です。
英語では、
a
an
the
is
are
of
to
for
などがあります。
例
文章:
The football match is exciting
Stop Words除去後:
football
match
exciting
不要な単語を除外することで、
- インデックスサイズ削減
- 検索性能向上
が期待できます。
TF-IDFとは
検索結果の関連度を計算するための代表的なアルゴリズムです。
TF（Term Frequency）
単語が文書内に何回出現するかを表します。
例:
football football football tennis
の場合、
football = 3
tennis = 1
となります。
IDF（Inverse Document Frequency）
単語の希少性を表します。
例えば1000件の文書中、
football → 800件
worldcup → 5件
なら、
worldcup
の方が価値の高い単語と判断されます。
基本イメージ
TF-IDF = TF × IDF
頻出かつ希少な単語ほど高得点になります。
TF-IDFの課題
例えば、
football football football football football
のように単語を大量に繰り返した文書は過剰に高評価されることがあります。
また、
長い文書ほど有利になる傾向があります。
BM25とは
現在のSolrで標準的に使用されているランキングアルゴリズムです。
BM25はTF-IDFを改良したものです。
TF Saturation
例えば、
DocA: football が5回
DocB: football が500回
TF-IDFではDocBが圧倒的に有利になります。
しかし実際には、
5回と500回
で関連度に100倍もの差はありません。
BM25では増加量を抑制し、より自然な評価を行います。
Length Normalization
文書長も考慮します。
例えば、
DocA: 50語
DocB: 5000語
TF-IDFでは長い文書が有利になりやすいですが、
BM25では文書長を補正するため公平な評価が可能です。
Solrにおける検索の流れ
全文検索では一般的に次の流れで処理されます。
Raw Text
↓
Tokenization
↓
Stop Words Removal
↓
Stemming
↓
Inverted Index
↓
Query Search
↓
BM25 Scoring
↓
Ranking
まとめ
本記事では全文検索の基本概念を紹介しました。
| 用語 | 概要 |
|---|---|
| Full-text Search | 全文検索 |
| Inverted Index | 単語→文書の対応表 |
| Tokenization | 単語分割 |
| Stemming | 語幹化 |
| Stop Words | 不要語の除去 |
| TF-IDF | 従来の関連度計算 |
| BM25 | 現在主流の関連度計算 |