Firestore(+Cloud Functions)で関連度つき全文検索をできるようにした話

# 記事概要を3行で
* Firestoreは便利だが全文検索機能はない
* でも外部サービスは使いたくない
* Firestore上に全文検索用のインデックス（転置インデックス）を構築して全文検索可能にした
* ついでに関連度（TF-IDF）で並べて表示できるようにした
* Cloud Functionsのコードと使い方はここ→https://github.com/tommyktech/Japanese-Fulltext-Search-in-Firestore


# Firestoreには全文検索機能が無い
[Firestoreの公式ドキュメント](https://firebase.google.com/docs/firestore/solutions/search)によると、Firestoreでは全文検索機能を提供しておらず、それをやりたいならサードパーティの検索サービスを使う必要があるようです。

> Cloud Firestore データの全文検索を有効にするには、専用のサードパーティの検索サービスを使用します。これらのサービスは、単純なデータベース クエリで実現できる機能をはるかに上回る、高度なインデックス作成と検索の機能を提供します。
続行する前に、調査して以下の検索プロバイダのいずれかを選択してください。

> * Elastic
> * Algolia
> * Typesense

> [全文検索 | Firebase](https://firebase.google.com/docs/firestore/solutions/search)

確かにElaticsearchは高機能でデータ分析までできる優れものですが、SaaSとして使おうとするとお値段が高めですし学習コストも高めです。AlgoliaやTypesenseはElasticsearchよりは高くありませんが、ちょっと全文検索したいだけなのにわざわざ導入するとなると二の足を踏んでしまいます。

そこで、外部サービスを使わずにFirestoreだけでお手軽に全文検索できるようにしてみたのが本プロジェクトです。

# 全文検索用インデックスのデータ構造
Firestoreに保存するデータは2種類あり、それぞれを別のコレクションに保存します。
一つは**テキストをそのまま保存するコレクション**、もう一つはテキストを分かち書きしてできる**単語を保存するコレクション**です。

### テキストコレクション
テキストを保存するコレクションのドキュメント構造は以下のようになっています：

```
(doc_id) : {
　　"text": "テキスト本文",
　　"hash": "eaa4612cbfd24abac6555aada0de9712"
}
```

`(doc_id)`の部分はFirestoreに保存するときのドキュメントIDで、実際にはランダムな文字列（例: `hOk2`）が設定されます。
`hash`フィールドはテキストを完全一致で探すための補助的なもので、テキスト本文をMD5でハッシュ化したものです。Firestoreは検索テキストが長すぎるとエラーになってしまうようなので、そういったテキストの完全一致検索に対応するために設置しました。

### 単語コレクション
単語を保存するコレクションのドキュメント構造は以下のようになっています：

```
(term_id) : {
  　"term": "転職",
　　"doc_ids": {
　　　　#　(doc_id): (TF値),
　　　　"hOk2": 0.12,
　　　　"Iog8": 0.01,
　　　　"OGaA": 0.29
　　},
  　"num_docs": 3
}
```

`(term_id)`の部分は単語を保存するときのドキュメントIDで、単語そのものが入ります（なので、上記の例では本来`(term_id)`の部分は `転職` となります）。
`term`フィールドも単語そのものが入ります。冗長な構造のように見えますがこれは将来的な拡張を見越してのものなので、今は無視してください。
`doc_ids`フィールドは`転職`という単語が含まれるテキストデータのドキュメントIDとそのTF値がMap形式で格納されています。
この`(TF値)`とは[TF-IDF](https://ja.wikipedia.org/wiki/Tf-idf)のTF(Term Frequency)のことで、上記の例だとdoc_id:`hOk2`のTF値`0.12`はそのテキスト中における

```
"転職"の出現数 / テキストの単語数
```
の計算結果となっています。

`num_docs`フィールドはこの単語が含まれるテキストデータの数であり、これは`doc_ids`フィールドのデータ数と一致します。
この値はTD-IDFのDF(Document Frequency)の値に相当するもので、本来は以下のように「全テキストデータ中でこの単語が出現する割合」のことを意味します。

```
"転職"が出現したテキストの数 / テキストデータの総数
```

しかし、関連度順に並び替えるためだけであれば`テキストデータの総数`は不要なため、今回はそこを省略[^1]して`"転職"が出現したテキストの数`だけを格納してあります。

上記のような構造にすることで、**TF-IDFの計算が単語のドキュメント内にあるデータだけで完結し、検索ワード1つにつき1回のアクセスだけで関連度計算に必要なデータがすべて揃う**ようになっています。


# 検索ロジック
検索処理は以下のような段階を踏みます: 

1. 単語コレクションから検索ワードに合致する単語ドキュメントを取得
1. そのデータから関連度（TF-IDF）を計算し、その値の降順にテキストのドキュメントIDを並び替える
1. 関連度の高い順にテキストコレクションからテキストデータを取得する

### 1. 単語コレクションから検索ワードに合致する単語ドキュメントを取得
これは単純に単語をドキュメントIDとして単語コレクションからドキュメントを取得するだけです。


### 2. そのデータから関連度（TF-IDF）を計算し、その値の降順にテキストのドキュメントIDを並び替える
TF-IDFの計算に必要なデータはすべて単語コレクションのドキュメント中に存在するため、そこから算出しソートすることで関連度順に並び替えることができます。

検索ワードが複数ある場合はその分だけ単語コレクションからドキュメントを取得し、それぞれにTF-IDFを計算して足し合わせてから並び替えます。

### 3. 関連度の高い順にテキストコレクションからテキストデータを取得する
関連度の高いものから順に、テキストコレクションからドキュメントを取得します。
当然、検索結果の件数を指定することも可能です。


# 制約と課題
このデータ構造の制約としては以下があります：

* Firestoreのドキュメントサイズ上限が1MB。つまり登録できるテキスト長とテキスト量に上限がある
* テキストデータの登録頻度が高すぎるとエラーになる（Firestoreの制限による）

テキスト長の問題以外は単語のドキュメントを分散構造にすることで対応できるはずなので、近々実装しようと思います。


# 作った感想
Firestoreを本格的に使うのはこれが初めてなので、実は気づいていないだけでもっと便利な機能があったりしそうですが、私なりに色々データ構造を考えた結果、たぶんこれが一番速くて安くて簡単だと思います（フラグ）。

また、私自身Elasticsearchのヘビーユーザーなのですが、今回（簡単ではあるものの一応）検索エンジンを作る立場になったことでより一層ElasticsearchとLuceneの偉大さを感じることができました。（fuzzy queryとかどうやって実装するんですかね？）

好きなことを気の赴くままに実装できるので、たまには無職[^2]もいいですね。

最後にもう一度Githubのリポジトリを掲載しておきます。よかったら☆ください。
https://github.com/tommyktech/Japanese-Fulltext-Search-in-Firestore

[^1]: 実は対数を取るのも省略してしまっています。
[^2]: 現在求職中。検索とか機械学習とか、ビッグデータ系の仕事ができる会社があれば[Twitter](https://twitter.com/ponko2ml)等で教えて下さい。