MiniSearch を読んでみる ②

「[MiniSearch を読んでみる①](https://qiita.com/YmBIgo/items/e6a68852237ad56d7a25)」の続きです。

## ① では何を読んだか？
SearchableMap という、[radix木](https://qiita.com/YmBIgo/items/e6a68852237ad56d7a25#radix木) を使った Map の実装を見てみました。
使い方は、

```typescript:index.ts
// SearchableMap.ts を同じディレクトリに置く
import SearchableMap from './SearchableMap'

let _index = new SearchableMap()
// set & get
_index.set("Book", "本")
_index.get("Book")
// fetch
_index.fetch("Book", () => "書籍") // -> "本"
_index.fetch("Article", () => "記事") // -> "記事"
// fussyGet
_index.fuzzyGet("Boo", 2) // -> {"Book" => ["本", 1]}
_index.fuzzyGet("B", 1) // -> {}

```

という 普通のMap より少し便利になったものになっています。
実装の詳細は、

https://qiita.com/YmBIgo/items/e6a68852237ad56d7a25

にあります。


この記事では、SearchableMap を使った MiniSearch の実装を見てみましょう。

## MiniSearch の実装

MiniSearch の使い方は、[公式](https://github.com/lucaong/minisearch) によると

```javascript:index.js
import MiniSearch from 'minisearch'

// A collection of documents for our examples
const documents = [
  {
    id: 1,
    title: 'Moby Dick',
    text: 'Call me Ishmael. Some years ago...',
    category: 'fiction'
  },
  {
    id: 2,
    title: 'Zen and the Art of Motorcycle Maintenance',
    text: 'I can see by my watch...',
    category: 'fiction'
  },
  {
    id: 3,
    title: 'Neuromancer',
    text: 'The sky above the port was...',
    category: 'fiction'
  },
  {
    id: 4,
    title: 'Zen and the Art of Archery',
    text: 'At first sight it must seem...',
    category: 'non-fiction'
  },
  // ...and more
]

let miniSearch = new MiniSearch({
  fields: ['title', 'text'], // fields to index for full-text search
  storeFields: ['title', 'category'] // fields to return with search results
})

// Index all documents
miniSearch.addAll(documents)

// Search with default options
let results = miniSearch.search('zen art motorcycle')
// => [
//   { id: 2, title: 'Zen and the Art of Motorcycle Maintenance', category: 'fiction', score: 2.77258, match: { ... } },
//   { id: 4, title: 'Zen and the Art of Archery', category: 'non-fiction', score: 1.38629, match: { ... } }
// ]
```

のように、MiniSearch の初期化(`new MiniSearch`)・ドキュメントの追加(`miniSearch.addAll`、ここでインデックスを作っている)・検索(`miniSearch.search`) のように行っている。

その MiniSearch の実装は、

https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts

にあります。
コメントも含めると 1500行近くのコードのなっていますが、やっていることは SearchableMap を使った文書のインデックス・検索 と その結果を使った検索結果の結合など や スコアリング(BM25, 文字数も考慮した TFIDF)をしています。

##### SearchableMap の型

まずは、typescript で書いているんで、SearchableMap の型設定を少しみてみましょう。
SearchableMap が出てくるのは、[MiniSearch の初期化をしている部分](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L380) の _index の部分ですが、`protected _index: SearchableMap<FieldTermData>` のようになっています。SearchableMap.ts を見ると \<T\> は

```
T  The type of the values stored in the map.
```

のようになっていますね。
つまり SearchableMap<FieldTermData> の FieldTermData は、SearchableMap の value になっています。set などを見ても、

```typescript:SearchableMap.ts
set (key: string, value: T): SearchableMap<T>
```

のようになっていますね。
では、`SearchableMap<FieldTermData>` の FieldTermData は、

```typescript:MiniSearch.ts
type DocumentTermFreqs = Map<number, number>
type FieldTermData = Map<number, DocumentTermFreqs>
```

のように、Map を Map で包んだ形になっていますね。
コメントに、number の正体が書いていないので、ここで、_index に情報を追加している部分を見てみましょう。
それが、addTerm になります。

```typescript:MiniSearch.ts
  private addTerm (fieldId: number, documentId: number, term: string): void {
    const indexData = this._index.fetch(term, createMap)

    let fieldIndex = indexData.get(fieldId)
    if (fieldIndex == null) {
      fieldIndex = new Map()
      fieldIndex.set(documentId, 1)
      indexData.set(fieldId, fieldIndex)
    } else {
      const docs = fieldIndex.get(documentId)
      fieldIndex.set(documentId, (docs || 0) + 1)
    }
  }
```

`fieldIndex == null` の場合を見れば分かりますが、`Map{fieldId: Map{documentId, count}}` になっています。
これで、_index に入る SearchableMap の value が `Map{fieldId: Map{documentId, count}}` であることが分かりましたね。

SearchableMap の型も簡単に分かったところで、MiniSearch の初期化から読んでみましょう。

##### MiniSearch の初期化

初期化処理は、[ここ](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L452) で行っています。
options に色々な設定が入るようですね。そして、最後に `this.addFields(this._options.fields)` でフィールドを追加しています。`this.addField` の中身も簡単で、`this._fieldIds[fields[i]] = i` で for文を回しているだけですね（結果、this._fieldIds の連想配列に フィールドIDがキーでバリューが i が追加される ）。
options でよく使われる オプションは、extractField / tokenize / processTerm ([参考コメント](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L413)) になっていて、defaultOptions ([ここ](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L1411])) に使われる extractField / tokenize / processTerm が載っています。

```typescript:MiniSearch.ts
const defaultOptions = {
  idField: 'id',
  extractField: (document: { [key: string]: any }, fieldName: string) => document[fieldName],
  tokenize: (text: string, fieldName?: string) => text.split(SPACE_OR_PUNCTUATION),
  processTerm: (term: string, fieldName?: string) => term.toLowerCase(),
  fields: undefined,
  searchOptions: undefined,
  storeFields: []
}
```


次に、`miniSearch.addAll` を見てみましょう。

##### addAll

addAll の実装自体は、[ここ](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L530) にあって、for文で this.add を回しているだけに見えますね。
では、this.add を見てみましょう（[ここ](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L492)）。
何やら長そうに見えますが、下の方にある addTerm を主に行っている関数だと思えば大丈夫です。
その前にやっているのは、
　１：ID があるかの確認
　２：constructor で設定された field が設定されているか
　３：fields に対応する value を tokenize する
　４：tokenize した token を for文で回し、addTerm する
addTerm では、再掲になりますが、

```typescript:MiniSearch.ts
  private addTerm (fieldId: number, documentId: number, term: string): void {
    const indexData = this._index.fetch(term, createMap)

    let fieldIndex = indexData.get(fieldId)
    if (fieldIndex == null) {
      fieldIndex = new Map()
      fieldIndex.set(documentId, 1)
      indexData.set(fieldId, fieldIndex)
    } else {
      const docs = fieldIndex.get(documentId)
      fieldIndex.set(documentId, (docs || 0) + 1)
    }
  }
```

`Map{fieldId: Map{documentId, count}}` のデータ構造になっていルので、_index の SearchableMap で単語を調べれば documentId 一覧が出てくることになります。
SearchableMap のデータ構造が分かれば、分かりやすいですね。

次に、search を見てみましょう。

##### search

この search が少し難しくて、簡単に言うと search は次のステップで動いています。

　１：query (searchの第一引数) を tokenize, processTerm して、各クエリ・fuzzySearchの有無・prefixSearchの有無を決定します（[executeQuery](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L1015)の関数）
　２：上の query の各単語で、_index (SearchableMap) の get します
　３：get した要素の 各ドキュメント の 単語の出現回数・単語が出現したドキュメントの数・ドキュメントの総数・フィールドの数などのパラメーターを BM25 という TFIDF の改良版の文書の順位付けのアルゴリズムに適用し、結果を出します（結果には、Boost する 文書・フィールドのパラメーターも掛け合わせます）。初期値になるので、< 文書と対応するBM25値 > の Map の結果を保存します。コードでは、[termResults](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L1163) という関数が該当します。
　４：fuzzySearch や prefixSearch をすることを１で決めてた場合は、それぞれ _index.fuzzyGet と _index.atPrefix して、結果を取得した後、３と同じように BM25 の結果を出します。文書が既に存在する場合は、BM25の値を足し合わせます。
　５：結果を、AND / OR / ANDNOT で抽出し、その結果を返しています。コードでは、[combinators](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L1345) 及び [ここら辺](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L1031) ) になります。


もっと簡単に言えば、クエリを空白で分けて、それぞれで get (指定した場合は、fuzzy, prefix)で検索して、その結果（文書の出現回数など）から BM25 という文書の類似度を測る指標を算出し、それを結果に表示しています。

[AutoSuggest](https://github.com/lucaong/minisearch/blob/2e2b3b791858abf665c842800069728c8e3666c1/src/MiniSearch.ts#L873) という関数もありますが、やっていることは 今回説明した search を呼び出して sort しているだけですね。 

ここまでで、MiniSearch の説明はおしまいです。
最初に思ったほどは難しくはなかったです。
今回出てきた BM25 は TFIDF を少し知っていれば理解できなくはないものかもしれません。あまり触れなかったので、興味があったら調べてみるといいかもしれませんね。