SQLite FTS : trigram tokenizerでunigram＆bigram検索までサポート-日本語全文検索
### 前段
2023年現在、全文検索システムをセルフホストしようとした場合に、
Elasticsearch、OpenSearch、Meilisearch（最近勢いありますね）
がまずメジャーどころで候補にあがるとおもいますが、これ以外にSQliteという選択肢もあります。
SQLiteには、デフォルトで有効の拡張機能として全文検索 FTS（Full-Text-Search）があります。
SQLite FTSはSQLite自体の特徴である優秀なポータビリティ、SQLで扱える習得運用コストの低さ、何より必要十分過ぎる検索速度があります。
ローカル／エッジといった環境向けなら個人的にはかなりオススメと感じています。
今回は SQLite FTS での日本語の全文検索をビルトインされているトークナイザtrigramを用いて環境を作成し、またtrigramに少しギミックを添えてunigram（1文字検索）、`bigram（2文字検索）`、までカバーする方法を紹介します。
### この記事の伝えたいこと
・ SQLite FTS での trigram トークナイザの導入
・ unigram（1文字検索）、bigram（2文字検索）への対応
### trigramトークナイザ
まず実装の前にFTS5のtokenizerについて少し説明します。
用意されているトークナイザは 「unicode61」（スペース文字と句読点文字で区切る。これがデフォルト。）、「ascii」「porter」「trigram」があります。
これまで日本語むけFTS実装ではスペース区切りされた文章を用意しての実装が多いかと思います。
trigramトークナイザは `ver 3.34.0 2020-12-01`に公開された比較的新しいトークナイザです。
trigramでは文字列を「3文字」を一つの塊トークンとして扱います。且つ文字列の先頭から1文字ずつ順番に最後まで3文字ずつに分割をします。
・素の文字列 :「検索システム」
・ trigramトークナイズ後のトークン : 「検索シ」 「索シス」 「システ」「ステム」
この合計4トークンが全文検索用の転置インデックスに格納されます。 また検索する際には、入力クエリの文字列に対して上記と同様に分割されます。
### SQLiteで実際に確認
$ sqlite3 hogehoge.db
--クエリ結果を見易くする準備
.mode column
.header on
-- FTS向けテーブル作成 trigram_fts、カラムは title, text
-- トークナイザをtrigramに指定
CREATE VIRTUAL TABLE trigram_fts USING fts5( title, text, tokenize='trigram');
--テストデータ挿入
INSERT INTO trigram_fts( title, text ) VALUES ('検索システム','実務者の為の開発改善ガイドブック');
INSERT INTO trigram_fts( title, text ) VALUES ('推薦システム実践入門','仕事で使える導入ガイド');
--全文検索 「ガイド」で検索
SELECT * FROM trigram_fts WHERE trigram_fts MATCH ('ガイド');
title text
---------- ----------------
検索システム 実務者の為の開発改善ガイドブック
推薦システム実践入門 仕事で使える導入ガイド
#### trigram でカバーできない範囲
この「trigram分割されたトークンを持つドキュメントを探す」という挙動の為、検索クエリ長が3文字未満の「1文字」や「2文字」の場合には検索ヒットしません。
具体例では、「検」「テ」、「検索」「シス」、で検索してもヒット0件となってしまいます。
--全文検索 「検索」で検索 -> 2文字はhitしない
SELECT * FROM trigram_fts WHERE trigram_fts MATCH ('検索');
（hit 0件）
--全文検索 「の」で検索 -> 1文字はhitしない
SELECT * FROM trigram_fts WHERE trigram_fts MATCH ('の');
（hit 0件）
試した通り、3文字の「ガイド」ではhit、2文字、1文字、ではhitしません。
#### unigram（1文字検索）、bigram（2文字検索）の対応について
では、この状態から 1文字&2文字検索を実現へ幾つか方法を挙げます。
（方法案1）. unigram（1文字検索）、bigram（2文字検索） のトークナイザを独自で実装する
custom tokenizer という機能があり独自に実装にて対応する方法。
これはもちろんunigram,bigramに限らずの話で、日本語独自むけとしてはSQLite3 fts5用mecabトークナイザというものも公開されています。
（ほかにSudachi対応やICUのBreakIteratorに対応したトークナイザがあれば誰か教えてください）
（方法案2）. デフォルトの「unicode61」トークナイザを用いて新たにunigram、bigramインデックス構築する
unigram、bigramにトークナイズした文章を別途用意をして、それぞれのテーブルを追加構築をします。
今回は行いませんが、unigramむけのサンプルは以下の様になります。
-- FTS向けテーブル作成 unigram_fts_tbl、カラムは title, text
-- トークナイザは今回FTS標準 デフォルト指定なし つまり"unicode61"
CREATE VIRTUAL TABLE unigram_fts_tbl USING fts5( title, text );
-- テストデータ挿入
-- 自前でスペース区切りテキストを用意してINSERT
INSERT INTO unigram_fts_tbl ( title, text ) VALUES ('検 索 シ ス テ ム','実 務 者 の 為 の 開 発 改 善 ガ イ ド ブ ッ ク');
-- 上記は生テキストを直書きですが、
-- 実際はcreation_function()機能にて別言語プログラム上のunigram関数を登録しSQLiteからトークナイズ関数を呼び結果INSERTするか、
-- プログラム側からSQliteを操作してINSERTするかになると思います。
（方法案3）. 1文字or2文字のクエリに部分一致するtrigramのトークンを検索クエリとして全文検索
FTS仮想テーブルを作成すると、内部的には幾つかのシャドーテーブルが生成されます。
その中にはトークンとドキュメントの関係情報をもつ情報があり、このトークン情報からunigram,bigramに部分一致するトークンを探して全文検索クエリにします。
（方法案1）.の独自トークナイザ構築はハードルが高いです。
（方法案2）.の別FTSインデックス構築では今回2つ増えるので全体データサイズ肥大化と管理対象が増えることが負担になります。
今回は（方法案3）.の部分一致するtrigramを使う方法で進めます。
#### 1文字or2文字のクエリに部分一致するtrigramのトークンを探す
手順としては、以下の順になります。
（手順1） `fts5vocab`モジュールでtrigramトークンの入った仮想テーブルを作成
-- これまでの準備で、trigram_fts は作成済み、データも投入済み、の状態
-- 作成済みのFTS仮想テーブル`trigram_fts`をもとに、`fts5vocab`モジュールで仮想テーブルを作成 名前はtrigram_fts_vocab
-- 構文は CREATE VIRTUAL TABLE {vocab_table_name} USING fts5vocab( {fts_table_name} , row );
CREATE VIRTUAL TABLE trigram_fts_vocab USING fts5vocab( trigram_fts , row );
--中身を確認
SELECT * FROM trigram_fts_vocab;
term doc cnt
---- --- ---
える導 1 1
で使え 1 1
の為の 1 1
の開発 1 1
る導入 1 1
イドブ 1 1
ガイド 2 2
システ 2 2
ステム 2 2
テム実 1 1
ドブッ 1 1
ブック 1 1
ム実践 1 1
事で使 1 1
仕事で 1 1
使える 1 1
入ガイ 1 1
務者の 1 1
善ガイ 1 1
実務者 1 1
実践入 1 1
導入ガ 1 1
推薦シ 1 1
改善ガ 1 1
検索シ 1 1
為の開 1 1
発改善 1 1
索シス 1 1
者の為 1 1
薦シス 1 1
践入門 1 1
開発改 1 1
-- トークナイズされたトークンが保存されています。対応するFTSテーブルにレコードが追加されるとこちらにも自動で追加されます。
パラメータを”row” タイプで構築したfts5vocabのテーブルには、関連するFTS5テーブル内の個別のトークンごとの情報が含まれます。
・ term : FTSテーブルに保存されている各3文字トークン
・ doc : トークンを持つドキュメントの総数
・ cnt : FTSテーブル全体内の出現回数
termカラムにトークナイズされたトークンが保存されているので、これらを利用します。
なおfts5vocabのパラメータ値には”row” の他に “col”、”instance”があり、そちらで作成したテーブルにアクセスすればよりドキュメント毎に対するトークン情報が拾えます。今回は割愛。
（手順2）1文字・2文字検索のクエリに`前方一致`するtrigramのトークンらを取得
ここで重要なのは、LIKE`前方一致`検索だけを使うという点です。
これと比較すると`後方一致`、`部分一致`は壊滅的に遅くなります。
全文検索をしたいケースでは対象ドキュメント数が数万～数百万はざらにあるのでインデックスサイズ増加に伴って`後方一致`、`部分一致`の速度はより悲惨になります。
せっかく高速なFTSなのにここが顕著に足を引っ張るので、速度に目をつむれるケース以外では推奨できません。`前方一致`をオススメします。
-- LIKE 検索で「検索」に`前方一致`のトークンを抽出 SELECT term FROM trigram_fts_vocab WHERE term LIKE '検索%' ; term ---- 検索シ SELECT term FROM trigram_fts_vocab WHERE term LIKE 'の%' ; term ---- の為の の開発
まずは1文字2文字を含んでいるtrigramトークンが見つかりましたので、これを全文検索に使えばOKです。
#### 1文字or2文字のクエリに部分一致するtrigramのトークンを探す その2
後方一致、部分一致検索はしていないので、このままだとまだ以下のケースで文字が拾えません。
・ 文章末の２文字と1文字
例:「検索システム」での「テム」「ム」
・ そもそも文章それ自体が1文字、2文字と短い
例:「JP」「0」
この対策として2案あります。
（案1）. すべてのドキュメントの文末に「2文字追加」してtrigram FTSを構築をする
例えば「`🐤`」や、軽量なASCII文字の「`!`」、ゼロ幅スペース（Zero Width Space, ZWSP）の「`\u200B`」、など他への影響がない範囲なら適当になんでも良いので、2文字をお尻に追加です。
素のドキュメントが「検索システム」の場合は2文字追加で「検索システム🐤🐤」となります。
本来の文章末尾の2文字「テム」「ム」も2文字追加後にtrigramトークナイズされると「テム🐤」「ム🐤🐤」として格納され、前述の LIKE`前方一致`検索では「テム%」「ム%」でtrigramトークンがhitします。
-- 新たに2文字追加バージョンのFTSテーブル trigram_fts_add2char を作成して仕切り直し
CREATE VIRTUAL TABLE trigram_fts_add2char USING fts5( title, text, tokenize='trigram');
--テストデータ挿入 🐤*2を末尾に追加
INSERT INTO trigram_fts_add2char( title, text ) VALUES ('検索システム🐤🐤','実務者の為の開発改善ガイドブック🐤🐤');
INSERT INTO trigram_fts_add2char( title, text ) VALUES ('推薦システム実践入門🐤🐤','仕事で使える導入ガイド🐤🐤');
--全文検索 「ガイド」で検索
SELECT * FROM trigram_fts_add2char WHERE trigram_fts_add2char MATCH ('ガイド');
title text
---------- ----------------
検索システム🐤🐤 実務者の為の開発改善ガイドブック🐤🐤
推薦システム実践入門🐤🐤 仕事で使える導入ガイド🐤🐤
-- fts5vocabモジュールでトークンのテーブル作成
CREATE VIRTUAL TABLE trigram_fts_add2char_vocab USING fts5vocab( trigram_fts_add2char , row );
--中身を確認
SELECT * from trigram_fts_add2char_vocab ;
term doc cnt
---- --- ---
える導 1 1
で使え 1 1
の為の 1 1
の開発 1 1
る導入 1 1
イドブ 1 1
イド🐤 1 1
ガイド 2 2
ク🐤🐤 1 1
システ 2 2
ステム 2 2
ック🐤 1 1
テム実 1 1
テム🐤 1 1
ドブッ 1 1
ド🐤🐤 1 1
ブック 1 1
ム実践 1 1
ム🐤🐤 1 1
事で使 1 1
仕事で 1 1
使える 1 1
入ガイ 1 1
入門🐤 1 1
務者の 1 1
善ガイ 1 1
実務者 1 1
実践入 1 1
導入ガ 1 1
推薦シ 1 1
改善ガ 1 1
検索シ 1 1
為の開 1 1
発改善 1 1
索シス 1 1
者の為 1 1
薦シス 1 1
践入門 1 1
門🐤🐤 1 1
開発改 1 1
-- LIKE 検索で「入門」に`前方一致`のトークンを抽出
SELECT term FROM trigram_fts_add2char_vocab WHERE term LIKE '入門%' ;
term
----
入門🐤
-- LIKE 検索で「ム」に`前方一致`のトークンを抽出
SELECT term FROM trigram_fts_add2char_vocab WHERE term LIKE 'ム%' ;
term
----
ム実践
ム🐤🐤
無事1文字クエリ、2文字クエリに対応できるtrigramのトークンが見つかりました。
この場合は副作用として
・ 対象ドキュメントすべてに2文字分追加するのでデータサイズが若干増加
・ 追加2文字も当然SELECT結果として取得されるので、後続処理で除去対応が必要
・ 文章中のhit位置部分のみを抽出ができる `snippet`関数での結果が2文字分も対象になる
・ 文章中のhit位置を指定タグ（bタグ等）で挟んで強調できる `hightlight`関数の結果が2文字分も対象になる
・ 文章長が2文字変わるので、`RANK`関数での`BM25 score`が若干変わる
目立つのは上からふたつ「データサイズが若干増加」と「後続処理で除去対応が必要」で、これらがOKならば2文字追加のこの方法がシンプルに1文字検索・2文字検索に対応ができます。
（案2）. trigram の全トークンを前後反転させ、別途テーブルに格納してLIKE’前方一致’検索する
新たに「trigramトークンを前後に反転させたトークンをもつ別のFTSテーブル」 を作成し、そちらに対してLIKE`前方一致`検索をします。
今回は行いませんが、コードサンプルとしては以下の様になります。
import sqlite3
# SQLiteデータベースに接続
conn = sqlite3.connect('hogehoge.db')
cursor = conn.cursor()
# テーブル作成（reverseテーブル）
cursor.execute('''CREATE TABLE IF NOT EXISTS reverse (
reverse_term TEXT
)''')
# trigram_fts_vocabテーブルからtermカラムのデータを選択
cursor.execute('''SELECT term FROM trigram_fts_vocab''')
results = cursor.fetchall()
# 選択したデータを逆順でreverseテーブルに挿入
for result in results:
term = result[0]
reverse_term = term[::-1] # 文字列を逆順にする
cursor.execute('''INSERT INTO reverse (reverse_term) VALUES (?)''', (reverse_term,))
conn.commit()
conn.close()
-- ２文字クエリ「入門」で確認 なお値は反転させて「門入」になる -- 反転テーブルのrowidと、元のtrigramトークンテーブルのrowidとが同一であるとして参照する SELECT term FROM trigram_fts_vocab WHERE rowid IN (SELECT rowid FROM reverse WHERE reverse_term LIKE "門入%" ); term ---- 践入門 -- 1文字クエリ「ム」で確認 SELECT term FROM trigram_fts_vocab WHERE rowid IN (SELECT rowid FROM reverse where reverse_term like "ム%" ); term ---- ステム
これで反転した部分一致の3文字トークンが取得できました。これを使い全文検索を行います。
こちらの方法では、このあたりが副作用
・ trigram反転トークンのための別テーブル構築
・ 上記の追加テーブルの分のデータ増加
（ユニークトークン数がデータ増分の上限になるので、英語圏など文字種類が多くないドキュメントならtrigram構成パターン数増加（データ増加）は正比例でなく何処かで緩やかになるはず。日本語などは構成パターン数が爆発、、）
・ 検索時の参照先テーブルが増える
（案1）と（案2）、比べると好みの範疇かと思います。個人的には（案2）は対象テーブルが増えSQLで管理の複雑さが出る点は好みでないのでパスします。
FTSテーブルのカラムの数が多い場合には（案1）での「2文字分追加」となる対象が増えるためそのデータ増加が負担になるようならtrigramトークン前後反転の（案2）にするかも、な見通しです。
### 1文字、2文字、3文字検索それぞれ実際のSQLにして検索する
1文字or2文字のクエリに対してLIKE前方一致をし、対象文字が含まれているtrigramトークンを取得できるようになりました。
この結果から全文検索をするわけですが、FTS5では `AND/OR/NOT`句が使えるのでこれ用いてSQLを書いていきしょう。
（例）クエリ： 「システム」
3文字以上あるので ストレートな全文検索でOK
SELECT * from trigram_fts_add2char WHERE trigram_fts_add2char MATCH ('システム');
（例）クエリ：「検索」
2文字クエリが含まれているので LIKE検索で拾えた文字列を ` OR` でつなぐ
SELECT * from trigram_fts_add2char WHERE trigram_fts_add2char MATCH ('検索シ OR 検索サ');
（例）クエリ：「サービス 速度 質」
3文字以上以外に1文字と2文字クエリが含まれているのでLIKE検索で拾えた文字列らを`ANDとOR と( )括弧 ` でつなぐ
SELECT * from trigram_fts_add2char WHERE trigram_fts_add2char MATCH
(' サービス AND ( 速度測 OR 速度が) AND ( 質管理 OR 質調査 OR 質試験 ) ');
または、
SELECT * from trigram_fts_add2char
WHERE
trigram_fts_add2char MATCH 'サービス'
AND
trigram_fts_add2char MATCH (' 速度測 OR 速度が ')
AND
trigram_fts_add2char MATCH (' 質管理 OR 質調査 OR 質試験 ')
;
### さらに実際のケースに即したSQL
クエリ長が1文字だけの検索ならSQLは以下の様になります。
候補のtrigramトークンを探し、GROUP_CONCAT`句のオプションのdelimiterで、複数検索の結果を`OR`で結合します。
SELECT * from trigram_fts_add2char WHERE trigram_fts_add2char MATCH (SELECT GROUP_CONCAT(term, " OR ") FROM trigram_fts_add2char_vocab WHERE term LIKE 'の%') ;
クエリが1文字、2文字、3文字以上と複数種類が混在しているケースなら、全文検索を複数つなげていく以下のようなSQLがわかりやすく良いです。
検索クエリが「サービス」「の」「開発」でAND条件とした場合以下の様になります。
SELECT * from trigram_fts_add2char WHERE trigram_fts_add2char MATCH 'サービス' AND trigram_fts_add2char MATCH (SELECT GROUP_CONCAT(term, ' OR ') FROM trigram_fts_add2char_vocab WHERE term LIKE 'の%') AND trigram_fts_add2char MATCH (SELECT GROUP_CONCAT(term, ' OR ') FROM trigram_fts_add2char_vocab WHERE term LIKE '開発%') ;
なお上記書き方以外の全クエリトークンをすべてAND/OR（）でまとめ1回のFTSにするSQL構文もEXPLAIN QUERY PLAN に通してみると上記と等価に見られました。
①プログラム側で構文を構成しやすい②「titleカラムはこの文字列で検索」といった形で対象を絞ることが可能、などの理由から今回はFTS構文を並べる上記を採用しました。
まとめ
・SQliteFTS5にてtrigram tokenizer を用いて日本語全文検索
・trigramトークンを使い、1文字検索・2文字検索を行う
を紹介しました。
記事が長くなったので、次回にSQlite FTSの検索速度ベンチマーク、インデックスサイズについて紹介しようと思います。
Tweet