fuzzy-finder を構成するアルゴリズム
fzy や fzf といった fuzzy-finder を使うと、stdin などからリストを受け取り、ユーザの入力によってマッチする行を絞り込むことができます。このとき、入力文字列の各文字は隣接している必要がありません。例えば、以下の画像のように baz という入力が与えられた時、これにマッチする行が絞り込まれます。また、マッチした行のリストは、入力値に基づいてより最適な順番にソートされて表示されています。同じく以下の画像の例を見てみると、入力後では baz という行が foobarbaz よりもセレクタに近い位置に表示されていることが分かります。このように、入力値が曖昧でも目当ての文字列を即座に見つけることができるのが fuzzy-finder の便利なところです。
上記のような機能は、approximate string matching と呼ばれ、主に以下の二つから構成されています。
- 入力文字列とマッチする行を絞り込む処理 (マッチング)
- ある行が入力文字列と比べてどのくらい類似しているかの評価処理 (スコアリング)
マッチングに関しては多少の差異はあるものの、単純な二重ループで各入力文字が出現するかどうかを調べれば良いだけなので、簡単に実装することができます。当然正規表現を使っても良いですが、ベンチマークを取ってみると圧倒的に素朴なループの方が早いので、どうしても必要なケースがない限り使うことはないかと思います。
スコアリングはユーザの体験に直結する部分で、fuzzy-finder の中でも重要かつ難しい部分です。ここでは、実装の一つとして fzy を見てみます。 fzy には ALGORITHM.md という、fzy で使われているアルゴリズムを解説しているマークダウンファイルがあります。
このファイルを見ると、fzy ではスコアリングを Levenshtein distance (Edit distance、編集距離) ベースの問題として扱い、Wagner-Fischer 法や Needleman-Wunsch (グローバルアラインメント) 法をベースとしたアルゴリズムを使用しているといった記述があります。
編集距離 (Levenshtein distance) と Wagner-Fischer 法
編集距離は以下のように定義されています。
二つの文字列間の編集距離は挿入、削除、置換によって片方の文字列をもう一方の文字列に変形するのにかかる最小の編集回数 *1
編集距離の基本的な考え方は 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー が非常に分かりやすいです。
編集距離を求めるために主に使われている手法が Wagner-Fischer 法で、動的計画法を用いたアルゴリズムです。Wikipedia に記載されている疑似コードを実装してみると以下のようなコードになります。見て分かる通り、Wagner-Fischer 法の時間計算量は O(mn) (m、n はそれぞれ二つの文字列の長さ) となります。
def wagner_fischer(s1, s2): m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)] for i in range(len(s1)+1): m[i][0] = i for j in range(len(s2)+1): m[0][j] = j for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): insert = m[i-1][j] + 1 delete = m[i][j-1] + 1 replace = m[i-1][j-1] + 1 if s1[i-1] != s2[j-1] else m[i-1][j-1] m[i][j] = min(insert, delete, replace) return m[len(s1)][len(s2)] print(wagner_fischer("kitten", "sitting")) # 3
Needleman-Wunsch 法 (グローバルアラインメント)
Needleman-Wunsch 法 は、バイオインフォマティクス分野で DNA などの配列から類似領域を特定するためのシーケンスアラインメントアルゴリズムです。*2
このアルゴリズムも動的計画法を用いており、実装は Wagner-Fischer 法と非常に似ています。シーケンスアラインメントアルゴリズムでは、二つの文字列の共通列が揃うようにギャップが挿入されます。ある地点 i、j におけるスコア m[i][j] は以下の 3 つが考えられます。
- スコア
m[i-1][j]にギャップが発生した - スコア
m[i][j-1]にギャップが発生した - スコア
m[i-1][j-1]に加えて最後に追加した文字がマッチ or ミスマッチしている場合
これらのうち、最もスコアが大きいものを実際のスコアとします。
def needleman_wunsch(s1, s2): GAP = 2 MATCH = 2 MISMATCH = 1 m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)] for i in range(len(s1)+1): m[i][0] = i * -GAP for j in range(len(s2)+1): m[0][j] = j * -GAP for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): s1gap = m[i-1][j] - GAP s2gap = m[i][j-1] - GAP match = m[i-1][j-1] + MATCH if s1[i-1] == s2[j-1] else m[i-1][j-1] - MISMATCH m[i][j] = max(s1gap, s2gap, match) return m[len(s1)][len(s2)]
needleman_wunsch("GCATGCU", "GATTACA") で関数を呼び出した後、m は以下のようになっています。
| G A T T A C A ------------------------------------ | 0 -2 -4 -6 -8 -10 -12 -14 G| -2 2 0 -2 -4 -6 -8 -10 C| -4 0 1 -1 -3 -5 -4 -6 A| -6 -2 2 0 -2 -1 -3 -2 T| -8 -4 0 4 2 0 -2 -4 G| -10 -6 -2 2 3 1 -1 -3 C| -12 -8 -4 0 1 2 3 1 U| -14 -10 -6 -2 -1 0 1 2
m を構築する際に m[0][0] から m[len(s1)][len(s2)] までで、それぞれ最も大きな値だったセルをパスとします。もし、最大値が複数ある場合は、パスが分岐します。m の構築後、記録したパスを m[0][0] へ向かってトレースバックしていくことでアラインメントを求めることができます。この時、ある時点での進路が左上であればマッチまたはミスマッチ、左であれば s1 へギャップの挿入、上であれば s2 へギャップの挿入を行います。例えば、上記の例では以下のようなアラインメントが一つの解として得られます。
GCATG-CU G-ATTACA
そして、m[len(s1)][len(s2)] がこのグローバルアラインメントにおけるスコアになっています。
Smith-Waterman 法 (ローカルアラインメント)
一方、fzf では Smith-Waterman 法 が使われています。*3 このアルゴリズムは Needleman-Wunsch 法とほとんど同じですが、各セルの最小値が 0 未満にならないように設定されています。
def smith_waterman(s1, s2): GAP = 2 MATCH = 2 MISMATCH = 1 m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)] max_score = 0 for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): s1gap = m[i-1][j] - GAP s2gap = m[i][j-1] - GAP match = m[i-1][j-1] + MATCH if s1[i-1] == s2[j-1] else m[i-1][j-1] - MISMATCH m[i][j] = max(s1gap, s2gap, match, 0) max_score = max(max_score, m[i][j]) return max_score
先程と同様の入力で実行すると m の状態は以下のようになります。
| G A T T A C A ------------------------------------ | 0 0 0 0 0 0 0 0 G| 0 2 0 0 0 0 0 0 C| 0 0 1 0 0 0 2 0 A| 0 0 2 0 0 2 0 4 T| 0 0 0 4 2 0 1 2 G| 0 2 0 2 3 1 0 0 C| 0 0 1 0 1 2 3 1 U| 0 0 0 0 0 0 1 2
Smith-Waterman 法では m[len(s1][len(s2)] ではなく、最大スコアを出したセルの位置を記録しておき、その地点からセル 0 になるまで左上へと遡っていきます。
上記の例では、m[4][3] の値 4 が最大スコアであるため、その位置から開始し、 m[0][0] まで遡ります。Needleman-Wunsch 法と同様にパスを求めると、以下のようになります。
GCAT G-AT
最大スコアがこのローカルアラインメントにおけるスコアになります。Smith-Waterman 法は、配列全体ではなく、局所的なアラインメントを求めるため、全体としてはあまり類似していない文字列間のスコアを求めるのに向いています。
ギャップペナルティ
通常、シーケンスアラインメントではギャップの挿入によるペナルティを課し、スコアを減点します。ペナルティ戦略にはいくつかの種類がありますが、ここではリニアギャップペナルティとアフィンギャップペナルティを紹介します。 ギャップペナルティに関しては Wikipedia のページ が良い感じに概要がまとまっていて感覚を掴むのに適しています。
リニアギャップペナルティは、ギャップの長さ (拡張) に比例してギャップペナルティが線形に増加します。増分は実装によります。
上記の Python のコードもリニアギャップペナルティを用いていて、増分は GAP = 2 です。
アフィンギャップペナルティは、リニアギャップペナルティに加えてギャップの開始にも一定のペナルティを課します。通常、ギャップの拡張に関するペナルティを大きくするとギャップの長さが長いほどスコアが低くなり、ギャップの開始に関するペナルティを大きくすると非連続なギャップの数だけスコアが低くなります。
マッチボーナス
fzy や fzf では、さらにギャップペナルティとは反対に、スコアを増加させることのできるマッチボーナスを導入しています。こちらも実装により様々ですが、以下のようなルールが採用されることが多いようです。
- 単語の先頭などの特殊な箇所にマッチしている
- マッチしている文字が隣接している
fzy や fzf などの fuzzy-finder はこのペナルティやボーナスのルールを調整することでより目的に合った候補を表示することができています。 ただし、闇雲にマッチボーナスを付与してしまうと適切ではない結果が生まれてしまう可能性があるため、ギャップペナルティとのバランスが重要です。fzf のコードコメントにはスコアリングルールが非常に詳細に記述されているので、それを読んでみると雰囲気をつかめるかと思います。
まとめ
fzy や fzf を元に、fuzzy-finder を構成しているアルゴリズムの概要を紹介しました。最近 Go ライブラリとしての fuzzy-finder をつくるためにこれらのアルゴリズムを学んでいて、だいたいの実装は終わったのですがやはりギャップペナルティとマッチボーナスをどう設定するかで悩んでいます。頑張って完成させるぞー。
*1:http://books.google.co.jp/books?id=Ofw5w1yuD8kC&pg=PA216&dq=%22%22
*2:バイオインフォマティクスは全くの無知なのでこれ以上のことはわかりません。
