JavaScriptで実装する文字列のあいまい検索（ファジー検索）アルゴリズム

本記事では、検索文字列を受け取り、対象の文字列に対して緩やかな（あいまいな）一致判定を行うJavaScriptのString関数を実装する方法を解説します。

実装の要件

この関数は次の基準を満たす必要があります。

• 検索クエリの各文字を先頭から順にループ処理する
• それぞれの文字が、対象の文字列内で同じ順序で出現するかどうかを確認する

すべての文字が順序どおりに見つかれば true を返し、途中で見つからない文字があれば false を返します。

動作例

('a haystack with a needle').fuzzySearch('hay sucks'); // false
('a haystack with a needle').fuzzySearch('sack hand'); // true

1つ目の例では「hay sucks」の一部の文字が順序どおりに存在しないため false となり、2つ目の例では「sack hand」の各文字がすべて順序どおりに見つかるため true となります。

コード例

const fuzzySearch = function (query) {
   const str = this.toLowerCase();
   let i = 0, n = -1, l;
   query = query.toLowerCase();
   for (; l = query[i++] ;){
      if (!~(n = str.indexOf(l, n + 1))){
         return false;
      };
   };
   return true;
};
String.prototype.fuzzySearch = fuzzySearch;
console.log(('a haystack with a needle').fuzzySearch('hay sucks'));
console.log(('a haystack with a needle').fuzzySearch('sack hand'));

コードの解説

このアルゴリズムのポイントは以下のとおりです。

• 大文字・小文字の統一：this.toLowerCase() と query.toLowerCase() により、両方の文字列を小文字に変換してから比較します。これにより、大文字・小文字の違いを無視した柔軟な検索が可能になります。
• indexOfによる順序チェック：str.indexOf(l, n + 1) は、前回見つかった位置 n の次の位置から文字 l を検索します。検索開始位置を前に戻さないことで、各文字が元のクエリと同じ順序で出現することが保証されます。
• ビット演算子 ~ の活用：indexOf は文字が見つからなかった場合に -1 を返します。-1 のビット反転（~-1）は 0（falsy値）になるため、!~(...) は「見つからなかった場合」に true となります。これを利用して、一致しない文字が出た時点で即座に false を返し、無駄な処理を省いています。

出力

上記のコードを実行すると、コンソールには次の出力が表示されます。

false
true