shikato's blog

Software Engineerをやっている人間のブログです。きんいろモザイクが好きでした。

SQLiteを使ってAndroid端末内でお手軽に日本語全文検索する

タイトルの通り、SQLiteを使ってAndroid端末内でお手軽に日本語全文検索する方法です。

FTS

SQLiteにはFTSという全文検索用モジュールがサポートされているのでそれを使う。
最新版はFTS4で、Android APIレベル11以上なら標準で使えるようなのでFTS4を使う。

公式ドキュメント
SQLite FTS3 and FTS4 Extensions


N-gram

FTS標準のトークン作成処理はスペース区切りにしか対応していないので、日本語の場合、自分でトークンを作成する必要がある。トークン作成には、お手軽にトークンを作成できるN-gram方式を採用する。

以下が指定した値(N)でN-gram変換するだけのNgramクラス。

/**
 * N-gramクラス
 * @author shikato
 *
 */ 
public class Ngram { 

    private Ngram() {
    }

    /**
     * N-gram変換したテキストを返す
     * @param aText N-gram変換するテキスト
     * @param aN N
     * @return N-gram変換されたテキスト
     */
    public static String getNgramText( final String aText, final int aN ) {

        final StringBuilder ngramText = new StringBuilder();
        final int length = aText.length();

        if ( length < 1 ) {

            return "";
        }

        if ( length > aN ) {

            int roop = length - aN;

            for ( int i = 0; i < roop; i++ ) {

                ngramText.append( aText.substring( i, i + aN ) );
                ngramText.append( " " );

                if ( i == ( roop - 1 ) ) {

                   i++; 
                   ngramText.append( aText.substring( i, i + aN ) );

                   if ( i % aN >= aN ) {

                       i++; 
                       ngramText.append( " " );
                       ngramText.append( aText.substring( i, i + aN ) );
                   }
                }
            }

        } else {

            ngramText.append( aText );
        }

        return ngramText.toString();
    } 
}

指定した値でN-gram変換するだけのNgramクラス


FTSテーブル作成

FTSテーブルでは値がすべて文字列扱いになってしまうので、実際に使用するときはメインのテーブルと全文検索用のFTSテーブルにわけて使うことが多くなると思う。

以下が上述したように、メインのテーブルと全文検索用のFTSテーブルにわけて作成する例。

CREATE TABLE hoge ( id INTEGER PRIMARY KEY AUTOINCREMENT, text TEXT )

CREATE VIRTUAL TABLE hoge_fts USING fts4( words TEXT )


検索対象テキストをメインテーブルのtextに格納し、検索対象テキストをN-gram変換したものを、FTSテーブルのwordsに格納する。
FTSテーブルを作成すると、docidというAUTO INCREMENTなカラムが自動的に用意されるので、メインテーブルと結合するときに使う。ちなみにdocidはrowidの別名なのでテーブル定義にはない。
あと、FTSでテーブルを作ると、~_contentのような名前のテーブル(Shadow Tables)が5つくらい勝手に作られるけど、普通に使う分にはあまり意識する必要はなさそう。
その辺りの詳細は公式ドキュメントに書いてある。
http://www.sqlite.org/fts3.html#section_9


保存

今回の例ではメインのテーブルとFTSテーブルにわけているので、両方のテーブルに保存する(メインのほうには通常のテキスト、FTSテーブルのほうにはN-gram変換したテキスト)。
※保存するテキストは、ユーザーの入力値になることがほとんどだと思うので、実際の開発時にはプリペアードステートメント等でSQLインジェクション対策する。

INSERT INTO hoge ( text ) VALUES( "hoge" ) 

INSERT INTO hoge_fts ( words ) VALUES( "ho og ge" )


同様に削除や更新の際も、両方のテーブルに対して実行する。


検索

MATCHを使用する。

SQLは以下のような感じになる。検索キーワードにN-gram変換したテキストを使用する。
※検索キーワードはユーザーの入力値になることがほとんどだと思うので、実際の開発時にはプリペアードステートメント等でSQLインジェクション対策する。

SELECT * FROM hoge h INNER JOIN hoge_fts hf ON h.id = hf.docid WHERE words MATCH "ho og ge"


前方一致だとこんな感じになる。

SELECT * FROM hoge h INNER JOIN hoge_fts hf ON h.id = hf.docid WHERE words MATCH "ho og ge*"


他にも色々な検索方法がある。
http://www.sqlite.org/fts3.html#section_3


パフォーマンス

SQLiteの.timerオプションを使用して測定。 投入したデータは5万件ほど。

普通にLIKE

SELECT count(*) from hoge WHERE text LIKE "%hoge%"

CPU Time: user 0.104006 sys 0.240015


FTS メインテーブルとの結合なし

SELECT count(*) from hoge_fts WHERE words MATCH "ho og ge"
 
CPU Time: user 0.000000 sys 0.000000


FTS メインテーブルとの結合あり

SELECT count(*) FROM hoge h INNER JOIN hoge_fts hf ON h.id = hf.docid WHERE words MATCH "ho og ge"

CPU Time: user 0.004000 sys 0.000000


FTS 前方一致でメインテーブルとの結合あり

SELECT count(*) FROM hoge h INNER JOIN hoge_fts hf ON h.id = hf.docid WHERE words MATCH "ho og ge*"

CPU Time: user 0.004001 sys 0.000000


やっぱりLIKEより速い。


まとめ

LIKEで検索するより速いし、別途ライブラリ等もいらないので、お手軽に端末内で日本語全文検索するときは使うと良いと思う。