やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

SQLite3の全文検索(FTS)について調べてみた

SQLite3での全文検索にはFTS(Full Text Search)という機能があるらしい。

背景

SQLite3にブログデータをバックアップした。

もしその中から全文検索できるようになれば、第二の脳になる。物忘れ問題を軽減できる。

全文検索

複数の文書(ファイル)から特定の文字列を検索すること。

今回は1つのSQLite3ファイルだが、複数のブログ記事をまたいで検索することをいう。

SQLite3で全文検索する方法

SQLite3 (PDO) を使った全文検索 (FTS) 入門 – セルティスラボ
Sqlite で全文検索 - Qiita
SQLiteを使ってAndroid端末内でお手軽に日本語全文検索する - Qiita
SQLiteの全文検索を使ってみる : mwSoft blog
iOSアプリでSQLiteを使い日本語の全文検索をする。 - shobylogy
SQLiteで高速全文検索〜日本語編〜 - SSSSLIDE

予想

難しすぎてよくわからない。以下は予想。

SQLite3のFTSは半角スペースで区切られた文字列と前方一致、完全一致したものを抽出するらしい。

しかし日本語は英語と違い、スペースで区切ったりしない。そこで、形態素解析(分かち書き)の処理をかけて文節や単語などを堺にしてスペース区切りのデータに加工する必要が生じる、のだと思う。

形態素解析

形態素解析とは、文章を最小単位に分割すること。

分かち書き

分かち書きとは、文章を分割してスペースなどを差し込むこと。

N-Gram

N-gramモデルを利用したテキスト分析 ―インデックスページ―

N-gramモデルとは、「ある文字列の中で、N個の文字列または単語の組み合わせが、どの程度出現するか」を調査する言語モデルを意味します。

SQLite3のFTS

半角スペースで区切られた語に対して、検索ワードと完全一致または前方一致するものだけが検索できるらしい。

Sqlite で全文検索 - Qiita

その機能のことを各参考先では「SQLite FTS 標準トークナイザ」のように表現されているように読めた。

FTS標準トークナイザは先述のような方法で検索するため、英語にしか利用できない。

たとえば以下のように英文なら半角スペースで区切られる。

This is a pen.

完全一致

SELECT * FROM some_FTS_table WHERE en_sentence MATCH 'pen'

前方一致

SELECT * FROM some_FTS_table WHERE en_sentence MATCH 'pen*'
完全一致 前方一致
This
is
a
pen.

上記のような検索をする。のだと思う。

日本語の場合

しかし、日本語は半角スペースで区切ったりしない。

そして、FTS標準トークナイザは半角スペース区切りの語に対して、検索ワードとの完全一致または前方一致しか検索できない。

これは筆です。

よって、上記の文に対して以下のような検索しかかけられない。しかしそれでは一致しない。

完全一致

SELECT * FROM some_FTS_table WHERE ja_sentence MATCH '筆'

前方一致

SELECT * FROM some_FTS_table WHERE ja_sentence MATCH '筆*'

以下のような文にすれば前方一致できる。

筆ですこれは。

しかし、半角スペース区切りになるまですべてひとつなぎの文字列として扱われてしまう。そしてその文字列の前方一致しかできない。ほとんどが検索ワードにならない。

実際は1記事を1テーブル1レコード1列に挿入する。1記事には複数の文章がある。もちろん半角スペースでは区切らない。たとえば以下のような文章になる。

筆ですこれは。硯、墨、半紙、文鎮で書道セットのできあがり。
ああ書道。ビバ書道。楽しいかな書道。

検索キーワードになりそうなものが複数あるが、先頭一致だと使えるキーワードは"筆"くらいしかない。つまりその記事の検索ワードはその記事の先頭部分の単語のみとなってしまう。

完全一致なら文章まるごと完全一致しないとならないため、まったく使い物にならない。

どちらも実用できないレベル。という話だと思う。

どうやって日本語を検索するか

では、どうやって日本語検索するのか?

おそらく大別して以下の2パターンがある。

A. 日本語形態素解析トークナイザを実装する
B. 分かち書きしたテキストを別途DBテーブルに保存して、標準トークナイザで完全一致、前方一致検索する

参考先はBの方法を使っていることが多いように読めた。Aだと検索するたびに形態素解析することになるためCPUやメモリの負担が大きいのだろう。データ量と計算量のトレードオフ

テキストの変更よりも検索のほうが頻繁にするなら、Bのほうが負荷が少ない。しかしデータ量は単純計算で2倍以上になる。元テキスト+分かち書きスペースになる。

他の方法は以下が思いつく。

C. 元テキストにLIKE句で検索する
D. 日本語を捨てて英語を使う

CはFTS機能を使わなくても実現できる。元テキストだけで足りる。しかし実行速度が遅い。DBが大きくなるにつれて顕著になると思われる。

Dはもはや日本語でない。祖国にして日出ずる国である倭国を捨てた売国奴に未来なし。冗談はさておき、現代ではむしろ逆かもしれない。が、Google翻訳が手放せない私には難しいというのが本音。そもそも、物忘れ対策のために今回のことをやっているのに、新しい言語を覚えることができたら苦労しない。

翻訳した文章をDBに入れて検索するとしても、その文章自体を読めない。ふたたび翻訳をかけたとしても原文と違うおかしな日本語になってしまうだろう。あたりまえだが英文挿入は自分で英語の読み書きができないと使えない手法。

SQLite3でどうやって実現するか

  1. FTSを有効にしてSQLite3をコンパイルする
  2. トークナイザーを実装する(N-gramなど)
  3. 全文検索用のテーブルを作成する
    • CREATE VIRTUAL TABLE hoge_fts USING fts4( words TEXT )
  4. 全文検索用テキストデータを作成し、上記テーブルに挿入する
  5. 検索SQLを作成して検索する
    • SELECT * FROM some_FTS_table WHERE ja_sentence MATCH '筆'

トークナイザ

検索方法

標準では半角スペース区切りで完全一致、前方一致しかできない。後方一致、部分一致ができないのは辛い。

正規表現や、Google検索のようにnotキーワード指定などもできたらなおよい。さらに、半角スペースを含んだ検索もできたほうがソースコードの検索などに便利そう。

そもそも、元テキスト全体から部分一致させるだけなら簡単にできそうな気がするのだが。標準トークナイザとやらを改造してコンパイルすれば対応できるかもしれない。おそらく最も難易度の高い方法になる。こちらがヒントになるかもしれないが未調査。

また、トークナイザ内で元テキストをメモリ上で分かち書きにして検索するという実装ができるなら、分かち書きデータを保存する必要がなくなる。全データに処理をかけるため計算負荷が大きいと思うが。

いずれにせよ、検索アルゴリズムはおそらくトークナイザで実装すると思われる。たぶん。

全文検索用テキストデータを作成する

  1. Markdownなど検索対象のテキストに分かち書き処理をする
  2. 1をCREATE VIRTUAL TABLEに挿入する

まずは分かち書き処理について調べる必要がある。

所感

とてつもなく難易度が高い気がする。トレードオフの判断もむずかしい。遅くても今すぐ簡単に実現できるLIKE句でいいような気がしないでもない。でも、一度はFTSを使ってみたい。やれるところまでやってみる。