Fuzzy Containsについて

小ネタです。

かつてあいまい検索といえば、レーベンシュタイン距離などで語句同士の類似度合いを数値化して、域値で絞ったり類似度順に並べるのが普通だったように思います。

ja.wikipedia.org

ですが、数年くらい前からか、もっと簡単なあいまい検索をよく見かけるようになりました。 AtomやVS Code、GitHubのファイル検索なんかで使われているあれです。

なんて名前なのかな？と思っていたのですが、Fuzzy Containsとか呼ばれているようです。

とても単純なロジックなのでサクッと書けます。 JavaScriptだと以下のような感じ。

function fuzzyContains(query, target) {
  if (query.length > target.length) return false;
  for (let i = 0, j = 0, l = query.length; i < l; i++, j++) {
    j = target.indexOf(query[i], j);
    if (j === -1) return false;
  }
  return true;
}

結果は文字が順番通りに含まれているか否かという二値だけですが、場面によってはこれが類似度を使うよりも直感的で使いやすいように感じます。 気に入ったのでいろいろなところで使っていきたいと思います。