FTS（全文検索）について調べたので、KotlinでNgram法の文字列分割を実装してみた

AndroidのSearchViewを使った検索機能について調べていると、出くわす「FTS(全文検索）」という単語。
この単語についてあまり理解していなかったので、調べてみました。

先人の方々が詳しくまとめてくれていました。特に参考になったのは、以下の記事です。
・Wikipedia「全文検索」

上記のページを見れば、全文検索の概要は把握することができます。ありがたい限りです。

FTS(全文検索）とは

「Full text search」の頭文字を取った語。
複数の文書にまたがって、文書に含まれる単語の検索を行う。
FTS（全文検索）はLIKEのようなパターンベースの検索とは異なり、単語ベースの検索を行う。

全文検索技術の分類

大きく「grep型」と「索引型」の２つの方法に分かれるようです。

grep型

複数のテキストファイルの内容を順次走査していくことで、検索対象となる文字列を探し出す方法。
この方法は事前にインデックスを作成しないため、検索対象が多くなるほど検索速度が低下する。

索引型

上記のgrep型に対して、こちらは予め検索対象にインデックスを作成しておくことで、検索速度の向上を図る。
AndroidでSQLiteによる全文検索を行う場合、こちらの方法を使用する。

索引文字列の抽出方法としては、「形態素解析」や「N-Gram」という方法がよく使われるようです。

N-Gram法とは

検索対象を単語単位ではなく文字単位で分解し、後続の N-1 文字を含めた状態で出現頻度を求める方法をN-Gram法という。
たとえば、Nの値が２の時、「私は太郎です。」という文字列は「私は」 「は太」 「太郎」 「郎で」 「です」 「す。」と分割されます。

形態素解析を実施するには、文脈や単語の解析をするための辞書が必要なため、お手軽に試すのは難しそうですが、N-Gram法であれば、一定の規則で文字列を分割するだけなのでお手軽に試せそうです。

ということで、今回はこのN-Gram法による文字列分割をKotlinで実装してみました。
以下がその実装です。

ソースコード

object FtsUtils {
    const val DEFAULT_SEPARATOR: String = " "
    const val DEFAULT_GRAM: Int = 2

    fun ngram(src: String, n: Int = DEFAULT_GRAM) : List<String> {
        return if (n <= src.length) {
            listOf(src.take(n)) + ngram(src.drop(1), n)
        } else {
            emptyList()
        }
    }

    fun toNgramText(src: String, n: Int = DEFAULT_GRAM, separatedBy: String = DEFAULT_SEPARATOR) : String =
        ngram(src, n).foldRight(initial = "", operation = {s, acc -> s + separatedBy + acc })
}

fun main() {
    println(FtsUtils.toNgramText("私は太郎です。"))
}

上記のコードを実行した結果は以下です。

実行結果

私は は太 太郎 郎で です す。 

ちゃんと動いていそうです。
また、時間のあるときにAndroidアプリでFTSを使った検索機能を実装してみようと思います。