エディタ補完ddc-fuzzyと曖昧一致 (Fuzzy matching)
エディタ補完に求めること
エディタ補完は、使用者が単語を入力しているときに、その入力を補助することが目的となります。補助するには二つの側面があります。
- 少ないタイプ数で単語を入力する (
getEでgetElementByIdを入力したい) - メソッドを覚えていなくても、推薦される(
[].で[].concatが使えることを教えて欲しい)
エディタ補完はとても便利です。しかし、便利さ故に沢山の候補を提示してくることがあります。この大量の候補から効率良く、相応しい候補を選ぶことができれば嬉しいです。私はこの二つを効率良く実現するのが曖昧検索だと主張します。
エディタの多くは、その補完候補を前方検索で探索します。つまり、getEはgetElementById、getElementsByTagnameに一致するため、これらの語を補完候補にしますが、getFileExtensionは候補になりません。このとき、getElementByIdを選択するためにはgetEでは複数の候補があるのでgetElementBまで入力しないと一意に定まった候補が表われません。また、getとExtensionという単語を知っていて,その間に含まれる単語を覚えていない場合、getを入力語にその候補からgetFileExtensionを人力で探す必要があります。
では曖昧一致の場合はどうでしょうか？getElementsByIdを入力したい場合はなんとgetEIと入力することで、(getE)lementBy(I)dと一意に候補を絞ることが可能になります。また、getとExtensionという単語を知っていて,その間に含まれる単語を覚えていない場合でも、getExで、その単語(get)File(Ex)tensionを絞り込むことが可能です。
では、このような検索は、どのように実装するのが良いのでしょうか？文字列を検索するための手法には、単純一致の他に、曖昧一致、ワイルドカードを用いたもの、正規表現を用いるものなどが存在し、それぞれの特性を知り、検索対象に応じて使い分ける必要があります。本稿では曖昧一致の基本とその改良案を理論と実装の両面で示します。さらに、このアルゴリズムをVimの補完候補の絞り込みへ応用したddc-fuzzyを紹介します。
曖昧一致とは
私達が文字列を検索するときその検索文字列を完璧に把握していることは珍しいです。例えばGoogle検索にて「たまねぎを使ったレシピ」という検索語を調べることを考えてみます。このとき私達は「たまねぎを使うレシピ」という文字列も併せてしらべて欲しいと思うでしょう。最近の検索エンジンは賢いので、そういった些細な違いも含めて検索結果に出してくれます。また、一昔の検索エンジンに慣れ親しんだ人なら、上記の検索語を用いずに「たまねぎ レシピ」と間に挟まった変化しやすい箇所を含まない形で入力するでしょう。ちななみにこの検索語は「たまねぎ<なんらかなの文字列>レシピ」を意図しており、「たまねぎ レシピ」という単語をそのまま調べたい訳ではないですね。
曖昧一致とは、このような一致といいつつも完璧に一致した文字列ではなく、検索語に似ている単語を検索する技術になります。
文字列が似ているということ
では,文字列が似ているというのは、どういうことなのでしょうか。類似度を測る基準には3つの基準があります。
- 挿入: 同じ文字列に1文字挿入された文字列は似ている文字列と言えます。たとえば、abcとaxbcは似ている文字列と言えますね。
- 削除: 同じ文字列から1文字取り除かれた文字列も似ていると言えます。たとえば、abcとabは似ている文字列と言えますね。
- 置換: 同じ文字列から1文字を別の文字に置き換えた文字列も似ていると言えます。たとえば、abcとabdは似ている文字列と言えますね。
ほかにも、文字列中の2文字を入れ替えたものも似ていると言うこともあります。3つの基準から類似度を計算した値を編集距離と呼びます。この値が小さいほど似ている文字列と呼びます。
単純な曖昧一致
ところで、挿入、削除、置換の3つを考慮した似ている文字列を全部調べるとなると大変です。
冒頭の例で言えば「たまねぎを使ったレシピ」という単語で「たまねぎを使うレシピ」を見つけることになります。この場合、検索語の長さ
詳しい人向けの説明をします。挿入のみを考慮した文字列の一致は正規表現として、
さらに詳しい人向けの余談です。情報科学の教科書だと有限状態オートマトンと正規言語と正規表現は対応すると書かれることが多いですが、ソフトウェアとして広く普及している正規表現ライブラリ
語の類似度による並べ替えとその改良
曖昧一致によって、検索候補から一致した文章を集めてきたとき、それを雑多に並べるだけでは実用的ではありません。それらを類似度に沿って並べる必要があります。この並べ替えの素朴なアイディアには編集距離を用いる方法が考えられます。一致した文章と検索語の間の編集距離が近ければ、その文章を前方に置くというアイディアです。
ところでこの手法では以下の場合に順序に基づいて比較することが出来ません。
「たまねぎを使うレシピ」と「たまごとねぎレシピ!」
この二つは、「たまねぎレシピ」との間の編集距離3の文字列です。通常の編集距離では文字同士の結合度が考慮されていないことが原因です。
また、多くの場合余計な文字列が末尾や先頭についていても問題ありません。
「たまねぎを使ったレシピ」と「こどもが喜ぶたまねぎレシピ10選」の二つの場合、
「たまねぎ レシピ」との編集距離は前者の前者の方が近いですが後者の方が好ましいことが多いです。
さらに、場合によっては検索語が早く表れたほうが好ましいかもしれません。
「こどもが喜ぶたまねぎレシピ10選」と「たまねぎレシピでこともが喜ぶ!」の二つの場合、
後者の方が好ましいことがあります。
これらの重み付けに基いた類似度は以下の手順で計算されます。
// sourceは検索語，matchは曖昧一致した文字の添え字の配列
export function scoreMatch(source: string, match: number[]): number {
// 一致した文字列の範囲
const length = (match.at(-1) ?? 0) - match[0];
// 隣接している一致した文字のグループの数
let ngroup = 1;
for (let i = 0; i < match.length; i++) {
if ((match.at(i - 1) ?? -1) + 1 !== match[i]) {
ngroup += 1;
}
}
// 類似度
let score = 0;
score += 1 / ngroup; // グループの数
score += 1 / (match[0] + 1) / 10; // 一致文字列の出現位置
score += 1 / length / 100; // 一致文字列の大きさ
score += 1 / source.length / 1000;// 文章全体の大きさ
return score;
}
DDC Fuzzy
DDC.vimはneocompleteやdeopeleteに続く系譜にあるVimの補完フレームワークです。私はこのDDC.vimの拡張機能として曖昧一致を実装しました。この拡張機能は冒頭に述べた効率良い変換候補を絞り込むだけでなく、上記の基準を用いた、並べ替えによる推薦、一致箇所の可視化を提供しています。これらの付加機能によりユーザーには、並べ替えや一致箇所のプレビューを通して効率の良い入力を促します.
詳しくはREADMEをご覧ください.
Discussion