【npmパッケージ】あいまい検索を簡単に実装できるFuse.jsの紹介とプチ性能評価

この記事について

あいまいなワードで住所をマッチングさせたいと思いました。既存実装ではいくつかパターンに沿ってマッチングさせていました。しかし、時間がかかりすぎる！！！！！解決したい！！！！
ということで今回は、あいまい検索ライブラリであるfuse.jsについて紹介します。

先に結論を３つ

• fuse.jsはあいまい検索ライブラリの中で最も多くダウンロードされているライブラリである
• 様々なoptionがあるので簡単に導入できる
• 部分一致に特化しているが、optionの設定次第では、完全一致の検索候補を抽出できると考えられる

詳細

導入

  // JavaScript
  >>> yarn add fuse.js 

  // TypeScript
  >>> yarn add @type/fuse

サンプルコード

import Fuse, { FuseResult } from 'fuse.js'

/**
 * @param targetList 検索対象のリスト
 * @param word 検索したいワード
 * @return 検索結果
 */
const fuseSearch = (targetList: string[], word: string) => {
  const options = {
    includeScore: true,
    isCaseSensitive: true,
    threshold: 0.4
  }

  const fuse = new Fuse(targetList, options);

  const resultList = fuse.search(word);

  return resultList;
}

• 検索結果例

// wordしたワード
"word": "丸の内1-1"

// resultListの中身

[
  {
    "item": "東京都千代田区丸の内1-1" // ヒットした値
    "refIndex": 1, // 比較に使用したアイテムのリスト内のインデックス
    "score": 0.15609486447437038  // ヒットしたスコア
  }
]

• optionを設定することであいまい検索の条件を編集することができる。使用頻度が高いと思われるoptionを以下に示します。
  • includeScore: 検索結果のオブジェクトにscoreの値を含めることができる。スコアが低いほどマッチ度が高い。
  • isCaseSensitive: 検索が大文字と小文字を区別するかどうかを制御できる。デフォルトはfalse。
  • threshold: スコアの閾値を設定することで、そのスコア未満の結果のみを抽出することができる
    この値を低く設定すれば、完全一致に近い検索候補をヒットさせることができる
  • includeMatches: 検索結果内でどの部分がマッチしたかを結果に含めることができる。
  • minMatchCharLength: ここで設定した文字数以下でマッチした結果を無視することができる
    • たとえば、結果内の単一文字の一致を無視したい場合は、これを２に設定する
    • minMatchCharLength: 3としておくと、2文字以下で一致した結果を無視することができる
  • shouldSort: 検索結果をスコア順にソートすることができる。デフォルトはtrue

最後に

• fuse.jsであいまい検索を実装しました。今回はシンプルなoptionのみで検索しました。他にもoptionがいくつかあり、組み合わせ次第では、複雑な条件での検索もできそうなので、今後も試していこうと思います。

Appendix

• 既存の実装とfuse.jsで出力結果がどのように変わったかをまとめる

前提

• 処理すべきデータ数：6,207,355通り
  • 検索対象のリストのデータ数：16,123個
  • 検索ワード数：385個

結果

閾値	既存	0.1	0.2	0.25	0.28	0.3
ヒットした数	149	121	121	124	154	235
時間(s)	41.554	5.239	7.744	9.505	10.319	10.294

データ数を変えてみる

前提

• 処理すべきデータ数：77,260,450通り
  • 検索対象のリストのデータ数：14,605個
  • 検索ワード数：5,290個

結果

閾値	既存	0.1
ヒットした数	149	121
時間(s)	530.052	86.03