Sublime Text は、私のお気に入りのプログラミング用テキストエディタです。

Sublime Textで気に入っている特徴の1つは、あいまい検索アルゴリズムです。ファイルや関数の検索が超高速なのです。これまで多くの人が、インターネット上で、この仕組みについて質問していましたが、満足の行く回答はありませんでした。そこで、私が自らこれを解明することにしました。

全部読むのが面倒な方へ

本文を読まずに最終結果だけ知りたいですか？　了解！　私は、あなたを責めたりしませんよ。

インタラクティブなデモ： こちらをクリック
ソースコード： C++ 、 JavaScript

Sublime Textの仕組み

Sublime Textのあいまい一致とは何でしょうか。そして、なぜそれはそんなに賢いのでしょうか。聞いてくれてうれしいです。

Sublime Textには、2つの非常に便利なナビゲーション関数があります。1つはファイル検索用で、もう1つが関数、クラス名などのシンボル検索用です。どちらも同じような仕組みで動きます。ファイル名を 一字一句正確に 入力する必要はなく、ほんの数文字タイプすれば良いのです。入力した文字が巧妙に一致して、順位付けされた結果リストを作成してくれます。例を見てみましょう。

これは、ファイル検索です。検索パターンとして”clu”と入力すると、最上位の結果は、” cl ient_ u nit.cpp”です。結果ごとに一致した文字が、太字で表示されます。

次の例を見てみましょう。

“agn”と入力すると、多くのAnimGraphNode型が見つかりました。ほとんどのアイテムは、いくつかキーを打つだけで、一意的に特定されます。

インスピレーション

Sublime Textのあいまい一致は、素晴らしいです。本当にすごいです。私はこれに心底惚れ込んでいます。残念ながら、他にこの仕組みを使っているものはありません。他のテキストエディタも、IDEも、検索フィールドのあるWebサイトも、どれもこれを使っていません。至るところで使われていてもいいのに、どこにも使われていないのです。

私は、この状況を変えたいと考えています。まずは、あいまい一致の謎を解明したいと思います。次に、既存のプロジェクトの検索を改善するのに使えるソースコードを提供したいと思っています。

具体的なユースケースのアイデアがいくつかあります。ファイル名やクラス、関数などのプログラミングをサポートしたいと思っています。しかし、それで全てではありません。

私は、熱心な ハースストーン のプレーヤです。ハースストーンのプレーヤがカードを探すことはよくあり、ゲーム中にデッキを構築する際にも検索をするでしょう。多くのプレーヤはオンラインでもカードを探しますが、ドラフトには、 HearthArena のようなサイトが役立ちます。私は、 Hearth.cards のようなカードデータベースサイトも大好きです。

多くのハースストーン関連サイトでは、基本的な部分一致のみが行われています。”Ragnaros the Firelord”というカード名に、部分列”rag”は含まれていますか？　はい、含まれています。しかし、”Inner Rage”、”Faerie Dragon”、”Magma Rager”、それにもっと多くの名前にも”rag”は含まれています。”rtf”あるいは”ragrs”と入力できれば、 ずっと 速くて便利です。

実際のところ、速い必要があります。何万という入力に対してテストしているのであれば、インタラクティブに実行が行われるべきです。

機能性

Sublime Textを試してみると、2つのことがすぐに明らかになります。

1. あいまい一致は、順序通りに各文字を一致しようとする。
2. いくつかの一致した文字には、他の文字よりも高いポイントが得られる秘密のスコアがある。

1番目については簡単に実装することができるので、早速やってみましょう！

出来上がり！　私はC++とJavaScriptの両方に対応できる、このシンプルなバージョンをライブラリに入れました。それには具体的な理由があります。分かりきっていることですが、シンプルな部分文字列の一致を置き換えることができるからです（えへん。 Slack の絵文字検索のように。えへん）。

スコアリング

面白いのは、秘密のスコアがあることです。どの要素がチェックされ、そしてそれが、何ポイント得ることができるのか？　以下は私がここでチェックする要素です。

• 一致した文字
• 一致しなかった文字
• 連続して一致した文字
• スタートからの近さ
• セパレータ（スペースやアンダーバー）の後ろに続く文字
• 小文字の後ろに続く大文字（別名、キャメルケース）

この部分は簡単です。一致した文字はプラスですが、一致しなかった文字はマイナスです。スタートに近い一致、フレーズの中間にある最初の文字に一致、またキャメルケース入力の大文字に一致もプラスです。

問題は、これらの要素が何ポイントを得ることができるのか、という点です。これに対する唯一の正解はないと思っています。重み付けは期待するデータセットに依存しますし、ファイルパスはファイル名によっても異なります。また、ファイル拡張子は無視できるでしょうし、個々の単語は連続した一致と関連しますが、セパレータやキャメルケースは関連しません。

そうは言っても、妥当なバランスを見つけられたと思っています。いくつもの異なるデータセットに対して見事に機能します。是非、こちらの ソースコード を確認してみてください。

• スコアの初期値は0
• 一致した文字： +0ポイント
• 一致しなかった文字： -0ポイント
• 連続した一致のボーナス： +5ポイント
• セパレータのボーナス： +10ポイント
• キャメルケースのボーナス： +10ポイント
• 一致しなかった頭文字： -3ポイント（最大-9ポイント）

これにはある特別な意味合いがあります。スコアには本質的な意味はありません。スコアの範囲は0から100までではなく、およそ[-50から50]です。長い単語の場合、一致しなかった文字のペナルティがあるので、最低スコアが下がります。また、長い検索パターンの場合は、一致したボーナスがあるので、最高スコアが上がります。

セパレータやキャメルケースのボーナスは、かなりのポイントが得られますし、連続した一致も、それなりのポイントが得られます。

最初の3文字が一致”しない”場合のペナルティもあります。つまり、スタートの近くで一致するポイントが得られることになります。ただし、中間で一致しようが最後で一致しようが、その差はありません。

完全一致に対する明確なボーナスはありません。一致しなかった文字はペナルティを得ますから、短い文字列や一致に近い文字は、それよりも高いポイントが得られます。

以上です。1つの検索パターンにおける結果は、スコアによってソートされるでしょう。こちらもうまく機能します。まだこちらの デモ をご覧になっていない方は、是非チェックしてみてください。

秘伝のソース

さらにここには、大きな違いを生む、ちょっとした複雑性が1つあります。検索パターン”tk”と文字列”The Black Knight”を思い浮かべてください。これらは、2つの異なる形で一致する可能性があります。

1. T he Blac k Knight
2. T he Black K night

Kという文字が、’black’の最後と’knight’の最初の2回現れています。最初のkに一致すると仮定すると、+0ポイントですが、2つ目のKに一致すると仮定すると、+10ポイントとなります。

このアルゴリズムを書くという私の最初の試みは、「パターン内で全ての文字が見つかった時点でループ状態となる」という結果になってしまいました。残念ながら、それより後の文字も一致し、ポイントも高くなるはずなのにです。ですから、検索文字列全体を走査しなくてはなりません。ループは”ベスト”スコアを追跡し、次のパターンの文字が一致した時にだけ適用されます。

パフォーマンス

Grepは非常に高速です 。とても速いです。高度な最適化がされており、各文字をテストする必要がありません。先に飛ばしていくことができます。

あいまい一致は、Grepほど高速ではありません。検索文字列内の全ての文字をテストする必要があります。私がクリーンコードだと思ってコードを書いていた間、決して最適化されることはありませんでした。それは、教育的目的のために明らかに可読性を重視しているからだと言えます。

私のホームCPUは、Intel i5-4670 Haswell @ 3.4Ghzです。Unreal Engine 4で13,164のファイル名に対してパターンの一致を見つける速さは、シングルスレッドで最大5ミリ秒、355,000ワード数の英語のワードリストに対するテストでは、最大50ミリ秒です（秘伝のソースを加える前は30ミリ秒でした）。

JavaScriptはC++ほど高速ではありません。実際、25倍ほど遅いようです。私は、webdevについて全く知識のないビデオゲームプログラマです。恐らく、どこかに改善の余地があるのではないかと思っていますが、Async helperが提供されているので、検索が遅いことによってスクリプトがブロックされることはありません。

最後に

私はSublime Text、そしてそのあいまい一致アルゴリズムが大好きです。私の1つ目の目標は、あいまい一致同様の効果的な何かを作り上げることでしたが、その目標は達成できたと思っています。

2つ目の目標は、GitHubにそのソリューションのパッケージを載せ、他の人にも役立ててもらいたいということでした。その目標が達成できたかは分かりませんが、そう願いたいです。もし、この記事が皆さんの役に立った、または有益であったと感じたようであれば、是非教えてください。皆さんがこのコードをどんな形であれ、使っていただけるのであれば、詳細を聞いてみたいです。特定のユースケースのために、このコードをカスタマイズしていただいても結構です。

インタラクティブなデモ： こちらをクリック
ソースコード： C++ 、 JavaScript
GitHub： lib_fts

お読みいただき、ありがとうございました。