blog.syfm

徒然なるままに考えていることなどを書いていくブログ

fzf ライクな fuzzy-finder を提供する Go ライブラリを書いた

f:id:ktr_0731:20190209113907p:plain

fuzzy-finder

fzffzyskim などの fuzzy-search (あいまい検索) を提供する CLI ツールの登場により、コマンドラインでの操作はますます表現豊かになっています。
例えば、カレントシェルのコマンドヒストリの一覧から fuzzy-finder を使って選択したり、ghq + fuzzy-finder + cd の組み合わせで選択したリポジトリのあるディレクトリへ移動したりといったケースが挙げられます。

また、fuzzy-finder それ自体をコア機能として組み込んだツールも増えています。例えば、cd コマンドの拡張である enhancd はパスの履歴を保持し、fuzzy-finder を使って移動したいディレクトリへすぐに移動することができます。また、拙作の itunes-cli は、iTunes で管理されている曲の一覧を入力にし、fuzzy-finder で選択・再生を行う機能を提供しています。

fuzzy-finder ツールの限界

しかし、fuzzy-finder は同名の要素を扱うことができない問題があります。
たとえば、先程紹介した itunes-cli を例として考えてみます。曲名はユニークではないので、当然衝突する可能性があります。そういった場合に fuzzy-finder で適切に選択するにはその他の情報も曲名と一緒に表示する必要がありますが、

  • 曲名は同じだが、アーティストが違う
  • 曲名もアーティストも同じだが、収録アルバムが違う
  • 曲名も収録アルバムも同じだが、アーティストが違う

ちょっと考えただけでこれだけのケースが挙げられます。そして、これらのケースをユニークに扱うためには、一行に曲名、アーティスト名、収録アルバム名を表示しなくてはならないため、ユーザの視点から見ると非常に冗長だと感じるでしょう。

インストールの複雑さ

インストールの複雑さに関する問題は、fuzzy-finder を組み込むツールをインストールする場合に発生します。そういったツールは内部でコマンド実行をすることで fuzzy-finder を起動しますが、そのためには fuzzy-finder が既にインストールされていなければいけません。もしその環境に fuzzy-finder がインストールされていないのであれば、ツールとは別に fuzzy-finder をインストールしなければいけません。また、ツールが検知するために環境変数などで fuzzy-finder のパスを指定しなければいけないかもしれません。

fuzzy-finder をライブラリとして提供する

github.com

上記二つのような問題を解決するために go-fuzzyfinder をつくりました。例えば以下のようなコードを書くだけで簡単に fuzzy-finder を起動できます。

type Track struct {
    Name      string
    AlbumName string
    Artist    string
}
var tracks = []Track{
    {"foo", "album1", "artist1"},
    {"bar", "album1", "artist1"},
    {"foo", "album2", "artist1"},
    {"baz", "album2", "artist2"},
    {"baz", "album3", "artist2"},
}

idx, err := fuzzyfinder.Find(tracks, func(i int) string {
    return tracks[i].Name
})

f:id:ktr_0731:20190208235230p:plain

この関数は戻り値として選択されたスライスのインデックスを返します。
しかし、上記の UI では先程挙げた、同名の行をうまく扱えない問題が発生しています。普通の fuzzy-finder の場合、この問題を解決するには一行あたりの情報量を増やすしかありません。 go-fuzzyfinder ではこの問題に対処するためにプレビューウインドウを提供しています。この機能は fzf を非常に参考にしています。 プレビューウインドウ付きで fuzzy-finder を起動するためには、以下のようにコードを変更します。

idx, _ := fuzzyfinder.Find(
    tracks,
    func(i int) string {
        return tracks[i].Name
    },
    fuzzyfinder.WithPreviewWindow(func(i, w, h int) string {
        return fmt.Sprintf("%s\n\nArtist: %s\nAlbum:  %s",
            tracks[i].Name,
            tracks[i].Artist,
            tracks[i].AlbumName)
    }))

f:id:ktr_0731:20190209000431p:plainf:id:ktr_0731:20190209000439p:plain
従来の方法とプレビューウインドウを使う方法

左の画像は従来の fuzzy-finder が取らなければならない方法で、右の画像がプレビューウインドウを使った方法です。付随する情報をプレビューウインドウへ分離したことでシンプルなインターフェースになっています。

この他にもいくつか機能がありますが、詳しくは GoDoc をご覧ください。

まとめ

fuzzy-finder をライブラリ化したことで、従来では難しかったことも実現できるようになりました。ぜひ使ってみてください!

fuzzy-finder で使われるスコアリングアルゴリズム

fuzzy-finder を構成するアルゴリズム

fzy や fzf といった fuzzy-finder を使うと、stdin などからリストを受け取り、ユーザの入力によってマッチする行を絞り込むことができます。このとき、入力文字列の各文字は隣接している必要がありません。例えば、以下の画像のように baz という入力が与えられた時、これにマッチする行が絞り込まれます。また、マッチした行のリストは、入力値に基づいてより最適な順番にソートされて表示されています。同じく以下の画像の例を見てみると、入力後では baz という行が foobarbaz よりもセレクタに近い位置に表示されていることが分かります。このように、入力値が曖昧でも目当ての文字列を即座に見つけることができるのが fuzzy-finder の便利なところです。

f:id:ktr_0731:20190130020555p:plainf:id:ktr_0731:20190130020634p:plain

上記のような機能は、approximate string matching と呼ばれ、主に以下の二つから構成されています。

  • 入力文字列とマッチする行を絞り込む処理 (マッチング)
  • ある行が入力文字列と比べてどのくらい類似しているかの評価処理 (スコアリング)

マッチングに関しては多少の差異はあるものの、単純な二重ループで各入力文字が出現するかどうかを調べれば良いだけなので、簡単に実装することができます。当然正規表現を使っても良いですが、ベンチマークを取ってみると圧倒的に素朴なループの方が早いので、どうしても必要なケースがない限り使うことはないかと思います。

スコアリングはユーザの体験に直結する部分で、fuzzy-finder の中でも重要かつ難しい部分です。ここでは、実装の一つとして fzy を見てみます。 fzy には ALGORITHM.md という、fzy で使われているアルゴリズムを解説しているマークダウンファイルがあります。

github.com

このファイルを見ると、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 法と非常に似ています。シーケンスアラインメントアルゴリズムでは、二つの文字列の共通列が揃うようにギャップが挿入されます。ある地点 ij におけるスコア 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 のコードコメントにはスコアリングルールが非常に詳細に記述されているので、それを読んでみると雰囲気をつかめるかと思います。

github.com

まとめ

fzy や fzf を元に、fuzzy-finder を構成しているアルゴリズムの概要を紹介しました。最近 Go ライブラリとしての fuzzy-finder をつくるためにこれらのアルゴリズムを学んでいて、だいたいの実装は終わったのですがやはりギャップペナルティとマッチボーナスをどう設定するかで悩んでいます。頑張って完成させるぞー。

*1:http://books.google.co.jp/books?id=Ofw5w1yuD8kC&pg=PA216&dq=%22%22

*2:バイオインフォマティクスは全くの無知なのでこれ以上のことはわかりません。

*3:入力文字列長が長すぎる場合は、時間計算量 O(n) で動作する別なアルゴリズムに切り替えています。

A Philosophy of Software Design を読んだ

A Philosophy of Software Design

A Philosophy of Software Design

170 ページくらいの洋書で、ソフトウェアの Complexity (複雑さ) について扱っている。洋書ではあるけど、難しい表現はあまりなく読みやすかった。

この本の冒頭で、Complexity を「ソフトウェアシステムを理解しづらくさせたり、変更させにくくする、システムの構造に関連するすべての要素」と定義し、それによって引き起こされる問題を述べている。
それ以降の章では、いかにして Complexity を減らすかというところにフォーカスし、モジュールの設計やレイヤーごとの抽象度、エラーの定義とハンドリング、コメントの種類と記述すべき場所など、さまざまな視点から見た手法や考え方が紹介されている。
どの章も興味深い内容だったけど、特に以下の章が良かった。

  • 第 4 章「Modules Should Be Deep」
  • 第 10 章「Define Errors Out Of Existence」
  • 第 13 章「Comments Should Describe Things that Aren't Obvious from the Code」

第 4 章「Modules Should Be Deep」には「deep module」という必要最小限の公開インターフェース (API) のみで多くの機能を提供できるようなモジュール設計の考え方が登場する。これを守ったモジュールは恐らく SOLID 原則を守ったモジュールと同様の特徴を持つと思うけど、モジュールの質を「deep」かどうかで測るという新しい視点は非常にわかりやすく、面白いと思った。

第 10 章の「Define Errors Out Of Existence」での、「モジュールの使用者が知らなくてはいけない例外やエラーは、そのインターフェースの仕様の一部 (= 仕様が増えるほど Complexity も増える)」という考え方が非常に良かった。さらに、この章では、その考え方に基づいて、エラーとしてモジュールの利用者へ投げないエラーを定義したり、いくつかのエラーを集約する手法が紹介されていた。

自分が普段よく使っている Go の標準ライブラリもこういった思想に基づいて作られているので、改めてよく設計されているなぁと感じた。

第 13 章の「Comments Should Describe Things that Aren't Obvious from the Code」は個人的に一番良かった章だった。 この章ではコメントの種類を以下の 4 つに分類し、適切な箇所に適切な種類のコメントをすべきだと主張していた。

  • インターフェースコメント: モジュールを利用するにあたって、そのインターフェースの振る舞い、引数や戻り値、副作用や返す可能性のあるエラーなどの記述
  • データ構造メンバコメント: クラスのフィールド変数や、静的変数に対するコメント
  • 実装コメント: メソッドや関数内に書くコメントで、それらのコードがどう動作するかの記述
  • クロスモジュールコメント: モジュールを跨ぐ依存に関する記述

モジュールの利用者に近い (より上位な) 種類のコメントでは、どういう振る舞いをするか (how) を記述する。その内部動作を抽象化したモジュールの仕様を記述し、実装をモジュール使用者から隠蔽する。 より実装に近い (下位な) 種類のコメントでは、なにをしているか・なぜそうしているか (what / why) を記述する。コメントの読み手がコードの挙動を理解できるように正確な記述を行う。

最近は、Go ソフトウェアを書くときにかなりの頻度で作成しているパッケージの GoDoc ドキュメントを見ることで、理解しやすい記述かを客観的に確かめたりしていた。そのため、この章で紹介されていたコメントの書き方は非常に参考になった。

この本の様な、即座に自身の開発スタイルやコードレビューに適用できる内容を扱っている本は今まであまりなかったため全体的に新鮮だった。もうちょっと戦術寄りな本だとリーダブルコードが近いと思った。
冒頭でも言ったとおり、そんなにボリュームが大きくなく読みやすい英文なので洋書を読んでみたいけどハードルが高い…と感じている人も是非。