「MiniSearch を読んでみる①」の続きです。
① では何を読んだか？
SearchableMap という、radix木 を使った Map の実装を見てみました。
使い方は、
// 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 より少し便利になったものになっています。
実装の詳細は、
にあります。
この記事では、SearchableMap を使った MiniSearch の実装を見てみましょう。
MiniSearch の実装
MiniSearch の使い方は、公式 によると
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 の実装は、
にあります。
コメントも含めると 1500行近くのコードのなっていますが、やっていることは SearchableMap を使った文書のインデックス・検索 と その結果を使った検索結果の結合など や スコアリング(BM25, 文字数も考慮した TFIDF)をしています。
SearchableMap の型
まずは、typescript で書いているんで、SearchableMap の型設定を少しみてみましょう。
SearchableMap が出てくるのは、MiniSearch の初期化をしている部分 の _index の部分ですが、protected _index: SearchableMap<FieldTermData> のようになっています。SearchableMap.ts を見ると <T> は
T The type of the values stored in the map.
のようになっていますね。
つまり SearchableMap の FieldTermData は、SearchableMap の value になっています。set などを見ても、
set (key: string, value: T): SearchableMap<T>
のようになっていますね。
では、SearchableMap<FieldTermData> の FieldTermData は、
type DocumentTermFreqs = Map<number, number>
type FieldTermData = Map<number, DocumentTermFreqs>
のように、Map を Map で包んだ形になっていますね。
コメントに、number の正体が書いていないので、ここで、_index に情報を追加している部分を見てみましょう。
それが、addTerm になります。
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 の初期化
初期化処理は、ここ で行っています。
options に色々な設定が入るようですね。そして、最後に this.addFields(this._options.fields) でフィールドを追加しています。this.addField の中身も簡単で、this._fieldIds[fields[i]] = i で for文を回しているだけですね（結果、this._fieldIds の連想配列に フィールドIDがキーでバリューが i が追加される ）。
options でよく使われる オプションは、extractField / tokenize / processTerm (参考コメント) になっていて、defaultOptions (ここ) に使われる extractField / tokenize / processTerm が載っています。
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 の実装自体は、ここ にあって、for文で this.add を回しているだけに見えますね。
では、this.add を見てみましょう（ここ）。
何やら長そうに見えますが、下の方にある addTerm を主に行っている関数だと思えば大丈夫です。
その前にやっているのは、
１：ID があるかの確認
２：constructor で設定された field が設定されているか
３：fields に対応する value を tokenize する
４：tokenize した token を for文で回し、addTerm する
addTerm では、再掲になりますが、
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の関数）
２：上の query の各単語で、_index (SearchableMap) の get します
３：get した要素の 各ドキュメント の 単語の出現回数・単語が出現したドキュメントの数・ドキュメントの総数・フィールドの数などのパラメーターを BM25 という TFIDF の改良版の文書の順位付けのアルゴリズムに適用し、結果を出します（結果には、Boost する 文書・フィールドのパラメーターも掛け合わせます）。初期値になるので、< 文書と対応するBM25値 > の Map の結果を保存します。コードでは、termResults という関数が該当します。
４：fuzzySearch や prefixSearch をすることを１で決めてた場合は、それぞれ _index.fuzzyGet と _index.atPrefix して、結果を取得した後、３と同じように BM25 の結果を出します。文書が既に存在する場合は、BM25の値を足し合わせます。
５：結果を、AND / OR / ANDNOT で抽出し、その結果を返しています。コードでは、combinators 及び ここら辺 ) になります。
もっと簡単に言えば、クエリを空白で分けて、それぞれで get (指定した場合は、fuzzy, prefix)で検索して、その結果（文書の出現回数など）から BM25 という文書の類似度を測る指標を算出し、それを結果に表示しています。
AutoSuggest という関数もありますが、やっていることは 今回説明した search を呼び出して sort しているだけですね。
ここまでで、MiniSearch の説明はおしまいです。
最初に思ったほどは難しくはなかったです。
今回出てきた BM25 は TFIDF を少し知っていれば理解できなくはないものかもしれません。あまり触れなかったので、興味があったら調べてみるといいかもしれませんね。