ファジーにテキストをマッチングする処理について

はじめに

この記事は、Vim/Neovimのプラグイン開発で「テキスト候補をクエリで絞り込む」という処理を実装する際に、自分が考えたことや、こだわった点を紹介するものです。

特定のフレームワークや言語に依存する話ではないため、Vimに限らず「自分好みのファジーマッチングを実装してみたい」と考える方の、何かの参考になれば幸いです。
a

なぜ、独自のアルゴリズムを考えるのか

CLIにおけるfzfのようなツールや、エディタのファイル検索など、ファジーマッチングは非常に身近で強力な機能です。一方で、それぞれのファジーマッチングの挙動は千差万別であり、個人の好みによって相性も出てくると思います。

例えば、個人的に嫌いな挙動として、クエリの各文字が対象テキスト内に順序通りに存在すればマッチさせるというのがあります。

これはなるべく取りこぼさずにマッチさせるという意味では意味はあると思いますが、ファイルパスのような複数の単語を持つテキストに対して abc と入力した際に、path/to/[a]rchive/src/[b]utton/abc-[c]omponent.tsx とハイライトされるのは「期待挙動」ではないと自分は考えます。

もちろん、これはアルゴリズムの優劣ではなく、あくまで「相性」の問題です。
今回は、特にファイルパス検索のようなユースケースにおいて、この「細切れマッチ」を避けて連続的なマッチを優先する、自分にとって心地よいマッチャーを開発することにしました。

採用した戦略

1. 単語境界のマッチ: keyword-pattern というテキストに対し、kやpのような単語の先頭から始まるマッチを優先します。これは人間の直感に近く、また、探索開始点を限定できるため計算効率も向上します。

2. ロンゲストマッチ（最長一致）: fast-encryption-feature に対して fe と入力した場合、[f]ast-[e]ncryption-feature という細切れなマッチよりも、fast-encryption-[fe]ature という連続したマッチを優先します。

なんとなく「こういう感じにマッチさせるのがいいなあ」というのは普段から考えていたので、まずはシンプルな実装を書き始めました。

ステップ1： シンプルな貪欲法を実装する

最初に実装したのは、上記の方針に基づいたシンプルな貪欲法です。

アルゴリズムの概要

1. 対象テキストから、まず単語境界の位置をすべて列挙する。
2. クエリの未処理部分の先頭から、すべての単語境界を起点として 最も長く連続して一致する箇所を探す。
   • 例えば query: fe, text: fast-encryption-feature の場合、
   • [f]ast-encryption-feature (長さ1)
   • fast-encryption-[fe]ature (長さ2)
   • という可能性の中から、最も長い fast-encryption-[fe]ature を選択します。
3. 最も長くマッチしたものを「正解」として採用し、マッチした分のクエリとテキスト位置を進める。
4. クエリがなくなるまで、2〜3を繰り返す。

この素直な実装は、多くのケースでうまく機能しました。しかし、業務で利用する中で、特定のケースで「そもそもマッチしない」という問題があることがわかりました。

この手法の問題

ただし、シンプルな貪欲法ではシンプルなユースケースでも容易に問題が発生します。
例えば features/search というテキストに featuresearch というクエリを入力したことを考えます。

• この場合、最初の探索で、アルゴリズムは最も長く一致する [features]/search (長さ8) を「最良の選択」として採用します。
• しかし、残ったクエリは earch となってしまい、テキストの残りである /search とはマッチしません。結果、探索は失敗してしまいます。本当の正解は、敢えて短い feature（7文字）を採用することでした。

ステップ2： 限定的なバックトラッキングを導入する

この問題をある程度解決するため、限定的なバックトラッキングの仕組みを導入することを考えます。この手の処理で大事なことは計算量を爆発させずに現実的なメリットを享受することです。

アルゴリズムの改善

1. マッチが見つからなかった場合を「マッチしないクエリが余ってしまった」と捉える
2. 余ったクエリはどの単語境界でもマッチしないわけだが、「消費済みクエリを 1 文字ずつ足してリトライする」すれば救えるのではないか？と捉えてロジックを追加する

改善された動作例

1. 最初の試行
   • best_runは、まず [features]/search (長さ8) を採用する
   • 残りのクエリ earch の探索が失敗する
2. バックトラック
   • best_run は失敗を受け、earch に対して、消費済みクエリの末尾を足す
   • 結果としてクエリは search となる
   • 結果として[features]/[search] が最終的なマッチ範囲となる

2 の処理でバックトラックする範囲を「3 文字までとする」などの制限を設けることも可能です。
また、論理的な上限も存在するので、ミスマッチ時に常にすべてのクエリをやりなおすといったことは発生しません。

ステップ3： バックトラッキングによるスコアリングの問題

バックトラッキングを導入したことで、新たな問題が生まれました。
それはスコアが重複加算されてしまうという問題です。

問題点

• featuresearchの例では、マッチが [feature] と [search] という2つの範囲でマッチしましたが、s が 2 回カウントされてしまっています。
• これにより、普通に featuresearch が featuresearch にストレートにマッチしたケースよりもなぜかスコアが高く出てしまうという問題が発生します。

解決策: 減点法

1. まず、すべてのクエリが連続マッチしたケースを「理想スコア」として計算する
2. 実際のマッチ結果から「どれくらいの分割されたチャンクでマッチしたか」を計算する
3. 理想スコアから、断片の間に生まれた「ギャップ」の数（チャンク数 - 1）に応じてスコアを減算する

おわりに

こうして、シンプルな貪欲法を実装して、特定の問題にぶちあたってバックトラッキングを導入。スコアリング周りに工夫を加えてひとまず満足のいくマッチャーを実装することができました。

（ただ、実はこのマッチャーにもまだ苦手なクエリが存在します。例えば、単語境界の先頭 1 文字を複数マッチさせるようなクエリです。false negative が発生することがありますが、これに対応しようと思うと計算量がかなり増えるし、少なくとも自分はやらない操作なので妥協です。）

実装においては、コードを書く → 動作確認 → バグ発見 → LLM にバグ探しを依頼、というプロセスを繰り返していました。その際に色々と LLM に質問をしていたのですが、このようなアルゴリズムは一般的に「ヒューリスティック検索」と呼ばれるようです。数学的な厳密解（本当に正しい解）を求めるのではなく、経験に基づく工夫を積み重ねて実用的なものにするアプローチのようですね。

今回、ほとんどの実装アイデアは自分で出しましたが、スコアリングの調整については全面的に LLM の提案を採用しました。非常に便利な世界になってきていますね。