Firestoreだけで実用的な全文検索機能の実現を目指したい

## Firestoreで検索機能を作るのは難しい
FirebaseのFirestoreには全文検索機能がありません。[公式ドキュメント]("https://firebase.google.com/docs/firestore/solutions/search?hl=ja")をみてもサポートしていないことが明記されていますし、Algoliaなどの外部サービスの導入が推奨されています。

多くのアプリには検索機能が実装されていると思うので、開発者としては可能な限り低コスト・低労力で実現してしまいたいところ。しかしAlgoliaやElastic、Typesenseを調べてみると、いずれもそれなりに料金がかかりそうな感じです。

Firebaseの優れているところは、とにかく簡単にサクッとサービスを構築できるところなので、プロトタイプアプリを作ってある程度ユーザーが増えてから機能を拡充していきたいという開発者は多いと思います。

そんななかコアな機能の一つである全文機能にコストがかかるのはなんとしても避けたい。…ということで今回は「外部サービスを使わずにある程度実用的な全文検索機能を実装する」をやっていきたいと思います。

:::note warn
あくまで小規模サービスやプロトタイプの作成向けなので、将来的にはFirestore公式ドキュメントの記載に従う方がいいのでご注意ください。
:::



## 達成したいこと
今回は「コトバコ」というアプリをリリースするにあたって、全文検索機能を実装してみます。実際にストアにリリース済みですので、最終的にどんな感じになったのかを確認してみてください。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653721/e54793b8-db1d-15c4-9a9a-c4b9b73cb63f.png" width="50%">



【iOS】
https://apps.apple.com/jp/app/wordbox-your-word-collection/id6670331462

【Android】
https://play.google.com/store/apps/details?id=com.tamina.wordLog.word_log&pli=1


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653721/57afb3bb-ee1d-65d9-6f31-0f70a7fe9d59.jpeg" width="50%">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653721/822fdfdb-0de1-d5b0-3ada-c3d7b63f4647.jpeg" width="50%">


## Firestoreで全文検索を実現する方法
### N-gramとは
N-gramというアルゴリズムを使用します。N-gramは、テキストデータを小さな部分に分割する手法です。「N」は分割する文字数を表します。例えば：

Unigram (1-gram): 1文字ずつに分割
Bigram (2-gram): 2文字ずつに分割
Trigram (3-gram): 3文字ずつに分割

具体例を見てみましょう。"hello"という単語の場合：

Unigram: "h", "e", "l", "l", "o"
Bigram: "he", "el", "ll", "lo"
Trigram: "hel", "ell", "llo"

この方法によって、部分一致検索が容易になることです。例えば、"el"で検索すると、"hello"や"elephant"などの単語にマッチします。

### Firestoreのドキュメント設計
N-gramを使用した全文検索を実現するために、Firestoreのドキュメントを以下のように設計します。

unigramMap: 1文字ごとの出現を記録するマップ
bigramMap: 2文字の組み合わせの出現を記録するマップ

例えば、"Hello World"というテキストを含むドキュメントは以下のようになります。

:::note info
（以下、Flutterで説明します。）
:::



````markdown
{
  "text": "Hello World",
  "unigramMap": {
    "h": true,
    "e": true,
    "l": true,
    "o": true,
    "w": true,
    "r": true,
    "d": true
  },
  "bigramMap": {
    "he": true,
    "el": true,
    "ll": true,
    "lo": true,
    "wo": true,
    "or": true,
    "rl": true,
    "ld": true
  }
}
````

ドキュメントにこのようなunigramMap、bigramMapを保持することで、以下のようにしてフィルタリングの結果を取得できるようになります。
（なお検索の精度を高めるためにunigramとbigramを両方使用します。）

````
Future<List<ItemModel>> simpleSearchItems(String keyword) async {
  final resultList = <ItemModel>[];
  
  try {
    Query query = FirebaseFirestore.instance.collection('items');

    if (keyword.isNotEmpty) {
      if (keyword.length == 1) {
        // 1文字の場合はunigram検索
        query = query.where('unigramMap.$keyword', isEqualTo: true);
      } else {
        // 2文字以上の場合はbigram検索
        final firstBigram = keyword.substring(0, 2);
        query = query.where('bigramMap.$firstBigram', isEqualTo: true);
      }
    }

    final snapshot = await query.get();

    for (final doc in snapshot.docs) {
      final item = ItemModel.fromJson(doc.data() as Map<String, dynamic>);
      if (keyword.length > 2) {
        // 3文字以上の場合、クライアント側でさらにフィルタリング
        if (item.text.toLowerCase().contains(keyword.toLowerCase())) {
          resultList.add(item);
        }
      } else {
        resultList.add(item);
      }
    }
  } catch (e) {
    print('Error searching items: $e');
  }

  return resultList;
}
````
この実装により、効率的な全文検索が可能になります。

検索キーワードが1文字の検索はunigramMapを使用し、2文字以上の検索はbigramMapを使用して初期フィルタリングを行います。3文字以上の検索の場合は、さらにクライアント側で追加のフィルタリングを行うことで、より正確な結果を得ることができます。

このようにすることで、例えば「H」「He」「Hello」のように検索した時に、「Hello World」が検索ヒットするようになります。


## この手法の課題と問題点
冒頭でお伝えしたとおり、これはあくまでも簡易版であって、本格的なサービスで運用するには向いていない場合があります。いくつかの重要な課題と問題点を挙げてみたいと思います。

### スケーラビリティの制限

適切にlimitを設定してあげないと、大量のデータが取得しようとしてクエリが遅くなったりする可能性があります。多くのドキュメントを取得したい場合は、ページネーションを検討するなど適切な実装が必要です。

必要以上にFirestoreの読み取り操作を行うと、データ量が増えた場合にコストが急増する可能性もあります。

### 検索精度の問題

bigramのみを使用しているため、長い検索語句や複雑な検索条件に対して精度が低下する可能性もあります。完全一致や前方一致、AND検索やOR検索、フレーズ検索などの高度な検索オプションがサポートされていません。



### インデックスの肥大化

すべての文書に対してunigramMapとbigramMapを作成するため、インデックスのサイズが大きくなってしまいます。長文を管理する場合には注意が必要です。






## まとめ

これらの課題と問題点を考慮すると、この方法は小規模なアプリケーションやプロトタイプの作成には適していますが、大規模なプロダクションレベルのアプリケーションには適していない可能性があります。

ユーザー数や検索クエリの数が増加するにつれて、パフォーマンスやコストの問題が顕著になる可能性があるため、成長に応じて専門の検索エンジン（AlgoliaやElasticsearchなど）への移行を検討する必要があるでしょう。
（もっと安くなれー！というかFirestoreで完結させてくたら最高っー！）


## 参考サイト
[Firestore だけで Algolia を使わず全文検索]("https://qiita.com/oukayuka/items/d3cee72501a55e8be44a")


[[Flutter × Firebase]全文検索＋検索候補機能を実装してみた]("https://zenn.dev/yamamotosaishu/articles/6bf0c3b8c8c081")


## 執筆者の開発アプリ

https://lit.link/taminaryousuke

今回のアプリ
【iOS】
https://apps.apple.com/ja/app/wordbox-your-word-collection/id6670331462

【Android】
https://play.google.com/store/apps/details?id=com.tamina.wordLog.word_log&pli=1