[Android] キーボードアプリの予測変換を高速にするために工夫したこと [Kotlin]

## はじめに

こんにちは！この記事では、私が開発している **Android アプリ** [スミレ 日本語キーボード](https://github.com/KazumaProject/JapaneseKeyboard) で、予測変換機能を高速化するために工夫したポイントを紹介します。

「スミレ」は、オフラインで動作するシンプルな日本語キーボードアプリです。予測変換のスピードや精度は、ユーザー体験に直結する重要な要素であり、特に辞書データを効率よく管理・検索する仕組みを整えることに力を入れています。

この記事では以下の4つのテーマで解説していきます。

1. Mozc 辞書データの活用と加工  
2. Dagger Hilt を使った効率的な辞書データの読み込み方法  
3. LOUDS を利用したトライ木構造の最適化  
4. rank/select 操作の高速化を実現する工夫  

アプリ開発者や辞書データの処理に興味のある方にとって、参考になる内容になれば幸いです！

## 辞書データの生成と Mozc の活用

まず、スミレで使用している辞書データについて解説します。

### Mozc 辞書データを活用

スミレでは、Google が提供する日本語入力システム「[Mozc](https://github.com/google/mozc)」の辞書データを活用しています。Mozc はオープンソースの日本語変換エンジンであり、大量の単語データを含む辞書が提供されています。

以下のファイルを辞書データとして利用しています。

- **`dictionary0.txt` などの辞書ファイル**: 単語や読み、品詞情報を含むテキスト形式のデータ  
- **`connection_single_column.txt`**: 単語間の接続情報を表すファイル  
- **`suffix.txt`**: 接尾辞データを格納するファイル  

これらのファイルは、スミレで利用できる形に加工されています。

### 辞書データの加工

辞書データを加工する際には、[kotlin-kana-kanji-converter](https://github.com/KazumaProject/kotlin-kana-kanji-converter) を利用しています。このプログラムで行っている主な処理は以下の通りです。

1. Mozc の辞書データを読み込む  
2. トライ木を構築し、LOUDS 形式に変換  
3. Android アプリで使用可能なバイナリ形式 (`.dat` ファイル) に出力  

この加工プロセスにより、辞書サイズを最適化しつつ、検索速度を大幅に向上させています。

生成された辞書データは、アプリの `assets` フォルダに配置しています。  
👉 [assets フォルダの辞書データ](https://github.com/KazumaProject/JapaneseKeyboard/tree/master/app/src/main/assets)

## Dagger Hilt を使った辞書データの読み込み

次に、Dagger Hilt を活用して辞書データを効率的に管理・利用する方法について説明します。

### Dagger Hilt とは？

Dagger Hilt は、依存性注入 (Dependency Injection) を簡単に実現するためのライブラリです。スミレでは、辞書データの管理や再利用性の向上のために Hilt を利用しています。

### Qualifiers を使った辞書の識別

辞書データには複数の種類があるため、それぞれを識別するために **Qualifier** を使用しています。

```kotlin
import javax.inject.Qualifier

@Retention(AnnotationRetention.RUNTIME)
@Qualifier
annotation class SystemYomiTrie

@Retention(AnnotationRetention.RUNTIME)
@Qualifier
annotation class SystemTangoTrie

@Retention(AnnotationRetention.RUNTIME)
@Qualifier
annotation class SystemTokenArray
```

### AppModule の実装

以下は、辞書データを Hilt で管理するための `AppModule.kt` の実装例です。

```kotlin
@Module
@InstallIn(SingletonComponent::class)
object AppModule {

    @SystemTangoTrie
    @Singleton
    @Provides
    fun provideTangoTrie(@ApplicationContext context: Context): LOUDS {
        val inputStream = context.assets.open("system/tango.dat")
        return LOUDS().apply { readExternalNotCompress(ObjectInputStream(BufferedInputStream(inputStream))) }
    }

    @SystemYomiTrie
    @Singleton
    @Provides
    fun provideYomiTrie(@ApplicationContext context: Context): LOUDSWithTermId {
        val inputStream = context.assets.open("system/yomi.dat")
        return LOUDSWithTermId().apply { readExternalNotCompress(ObjectInputStream(BufferedInputStream(inputStream))) }
    }

    @SystemTokenArray
    @Singleton
    @Provides
    fun provideTokenArray(@ApplicationContext context: Context): TokenArray {
        val tokenStream = context.assets.open("system/token.dat")
        val posTableStream = context.assets.open("pos_table.dat")
        return TokenArray().apply {
            readExternal(ObjectInputStream(BufferedInputStream(tokenStream)))
            readPOSTable(ObjectInputStream(BufferedInputStream(posTableStream)))
        }
    }
}
```

### Hilt を使った辞書データの利用例

以下は、KeyboardService で Hilt を利用して辞書データを注入する例です。

```kotlin
@AndroidEntryPoint
class KeyboardService : InputMethodService() {

    @Inject
    @SystemTangoTrie
    lateinit var tangoTrie: LOUDS

    @Inject
    @SystemYomiTrie
    lateinit var yomiTrie: LOUDSWithTermId

    @Inject
    @SystemTokenArray
    lateinit var tokenArray: TokenArray

    override fun onCreate() {
        super.onCreate()

        // 例: 入力「きょう」に対する候補を取得
        val suggestions = yomiTrie.search("きょう")
        Log.d("Suggestions", suggestions.toString())
    }
}
```

## rank/select の高速化

### 背景

LOUDS 形式では、ノードの探索に `rank` と `select` 操作が重要です。これらの操作はデフォルトでは線形時間 (O(n)) を要するため、スミレでは **事前計算した IntArray** を利用することで定数時間 (O(1)) に最適化しました。

### 高速化の実装例

以下は、rank/select 操作の高速化を実現する Kotlin コードの例です。

```kotlin
fun BitSet.rank1GetIntArray(): IntArray {
    val n = this.size()
    val rank = IntArray(n + 1)
    for (i in 1..n) {
        rank[i] = rank[i - 1] + if (this[i - 1]) 1 else 0
    }
    return rank
}

fun IntArray.rank1(index: Int): Int {
    return this[index]
}

fun IntArray.select1(value: Int): Int {
    for (i in indices) {
        if (this[i] == value) return i
    }
    return -1
}
```

この最適化により、大規模な辞書データを効率的に処理できるようになりました。

## 成果

- **予測変換の高速化**: 入力後の候補表示が大幅にスピードアップ。  
- **メモリ効率の向上**: LOUDS の採用でメモリ消費を削減。  
- **開発効率の向上**: Dagger Hilt による依存性管理で保守性を改善。

## 今後の展望

- **ユーザー辞書の追加**: カスタム単語を登録可能にする。  
- **さらなる最適化**: 辞書データの検索アルゴリズムを改良。  
- **多言語対応**: 日本語以外の辞書データの対応を検討。

## まとめ

この記事では、Google Mozc の辞書データを利用し、効率的に管理・加工する方法と、予測変換の高速化の工夫について解説しました。Dagger Hilt を活用した辞書管理や、rank/select の最適化によって、スムーズなユーザー体験を実現しています。

プロジェクトの詳細は以下のリポジトリで確認できます。

- [スミレ 日本語キーボード](https://github.com/KazumaProject/JapaneseKeyboard)  
- [辞書生成プログラム](https://github.com/KazumaProject/kotlin-kana-kanji-converter)  
- [Google Mozc](https://github.com/google/mozc)  

最後までお読みいただき、ありがとうございました！ 😊