N-gram方式と形態素解析方式の2種類に大別されることがわかった。
全文検索の方法
第4回 形態素解析のしくみ：検索エンジンを作る｜gihyo.jp … 技術評論社
第5回 N-gramのしくみ：検索エンジンを作る｜gihyo.jp … 技術評論社
第6回 N-gramと形態素解析との比較：検索エンジンを作る｜gihyo.jp … 技術評論社
参考にした。わかりやすい。感謝。
どうやらN-gram方式と形態素解析方式の2種類に大別されるらしい。それぞれ長所と短所があってトレードオフ。
形態素解析方式
分かち書きで以下のようにスラッシュ/で区切られたとする。
今日/は/大雨/で/す/。
検索ワード雨でではヒットしない。今日はも同様。その文字列があるにも関わらず。これが形態素解析方式の欠点らしい。
私が思っていたのとだいぶ違う。単純に文字列から特定の文字の羅列に一致する部分が含まれているものを「全文検索」だと認識していた。形態素解析方式はどちらかというと、「本文から単語を抜き出して完全一致したものをヒットさせる」というイメージ。
しかも分割は辞書に依存する。辞書を変更したら分割も変わるため、データを作りなおす必要がある。また、日本語の文書にしか使えない。
ふつうは検索するとき、品詞は名詞を使う。文章はあまり使わない。困ることは少ないかもしれない。でも、特殊な言い回しだから覚えていて、それと一致する文書を見つけたいときに困りそう。
また、ソースコードから検索したい場合には到底使えない。自然言語のうちの日本語にしか使えない。
N-gram方式
形態素解析方式に存在した問題は、N-gram方式で解決できる。実装の仕方次第では。
第5回 N-gramのしくみ：検索エンジンを作る｜gihyo.jp … 技術評論社
N-gramのうち2-gramにしたとする。検索対象の文書を2文字ずつ分割した語にする。検索ワードが2文字以上の文字列である場合、連続しているかどうかの確認をする処理をすれば、2文字以上の完全一致をヒットさせることができる。
ただし、ノイズも拾いやすい。"京都"という言葉で検索を行うと"東京都"という文字列を含む文書も検索されてしまう。
気になること
形態素解析方式にしろ、N-gram方式にしろ、以下のどちらなのかが気になる。
- 検索するたびに分解処理をする
- あらかじめ分解した検索用データを保存しておく
どちらにするかで、データのファイルサイズや、実装するコードが変わる。
文書の量が多くなると、検索のたびに分解処理するのは現実的でないかもしれない。でも、わざわざ検索を高速化させるために二倍以上の無駄なデータを保持するくらいなら、遅くてもLIKE句でOKという判断もありうる。
転置インデックス
よくわかっていない。順位付けにも関係するかもしれない。
どちらを使うか
N-gram方式のほうが汎用性が高い。日本語以外に使えるし、分割用の辞書も不要。やるならN-gram方式を優先したい。
パターン網羅
| 検索方法 | 説明 |
|---|---|
| LIKE句 | 何も実装せずすぐに使える。実行速度が遅い。 |
| REGEXPユーザ定義関数 | 正規表現。処理を実装せねば使えない。 |
| FTS(標準Tokenizer) | 英語でしか実用性がない。 |
| FTS(標準Tokenizer)+N-gramデータ | 全言語対応。 |
| FTS(標準Tokenizer)+形態素解析データ | 日本語のみ対応。 |
| FTS(独自Tokenizer) N-gram方式 | 検索のたびN-gram分解する |
| FTS(独自Tokenizer) 形態素解析方式 | 検索のたび形態素解析分解する |
| FTS(独自Tokenizer) 原文部分一致 | 原文から部分一致する（検索用データ不要） |
| 検索方法 | 速度 | 実装 | 検索用DB | 英語 | 日本語 | プログラミング言語 |
|---|---|---|---|---|---|---|
| LIKE句 | 遅 | - | - | o | o | o |
| REGEXPユーザ定義関数 | ? | 要 | - | o | o | o |
| FTS(標準Tokenizer) | 速 | - | - | o | - | - |
| FTS(標準Tokenizer)+N-gramデータ | 速 | 要 | 要 | o | o | o |
| FTS(標準Tokenizer)+形態素解析データ | 速 | 要 | 要 | x | o | x |
| FTS(独自Tokenizer) 検索のたびN-gram分解 | 速? | 要 | - | o | o | o |
| FTS(独自Tokenizer) 検索のたび形態素解析方式分解 | 速? | 要 | - | x | o | x |
| FTS(独自Tokenizer) 原文部分一致 | 速? | 要 | - | o | o | o |
疑問
LIKE句のように原文から部分一致する手法はFTSでは使えないのか？「半角スペース区切り単語との一致確認」という縛りが元凶に思える。
また、正規表現で*検索単語*とすれば部分一致するドキュメントを探せないか？
SQLite3で正規表現(REGEXP)
SQLiteで正規表現を使いたい場合は関数を自分で作成する必要があるみたい - Guyon Diary
RailsのSQLiteで正規表現を使う - rochefort's blog
Big Sky :: DBD::SQLiteで正規表現SQLを使う
自前で正規表現を実行する関数を実装する必要があるらしい。なんという丸投げ。 トークナイザといい、そのうちSQLite3を魔改造しまくってオレオレSQLite3になってしまいそう。
性能もわからないし、実装方法もわからない。LIKE句で妥協すれば、これもやる必要のないことか。
正規表現すら標準装備していないのなら、FTSの日本語実装など永遠にされないかもしれない。
メタデータ
SQLite3の機能とはまったく関係ないが、記事とメタデータを関連付けたら、検索を向上できるかもしれない。
何も全文検索や正規表現などに囚われる必要はない。たとえばschema.orgなど汎用性があり、なおかつ実用性のある型を自分で定義する。それを元に記事の部分的な自動生成までできるとなおよし。それをふつうのSQLのSELECT文でやるという案。
所感
今後の作業方針がブレてきた。
あまりFTSにこだわらなくてもいいかもしれない。検索方法の工夫次第という感じがしてきた。FTSは未完成な機能だし、私が今手を出す必要性は薄い。ということにして逃げよう。すぐに日本語環境で使えるなら迷わず使ったのだが。当面はLIKE句でしのぐか。遅くて困るようになったらFTSの実装を検討しよう。
それに、もし進めるならメタデータ＆自動化のほうが効果が高そう。しかし、具体性がない。それよりも、GitHubの集計や可視化のほうが具体化しやすそう。そちらを優先したほうがアウトプットの効率がよさそう。
