重み付きレーベンシュタイン距離（編集距離）のライブラリを書きました。文字ごとに追加・削除・置換のコストが指定できます。文字列の長さによる正規化や複数の文字列から近いものを選ぶ関数も含まれてます。
エラーメッセージをラフに分類したいという動機から作り始めました。類型的で機械学習が必須なわけでない分類タスクにお役立てください。
詳しい使い方はGitHubのREADMEを見てください。
go get -u github.com/deltam/go-lsd-parametrizedカスタマイズ
重みの調整でだいたいの用途は足りるかなーと思います。編集方法ごとに重みを付ける場合はlsdp.Weights構造体、さらに文字ごとに重みを付けたい場合はlsdp.ByRune()を使います。
// weighted
wd := lsdp.Weights{Insert: 0.1, Delete: 1, Replace: 0.01}
fmt.Println(wd.Distance(a, b))
// Output:
// 0.22
// weighted by rune
wr := lsdp.ByRune(&lsdp.Weights{1, 1, 1}).
Insert("g", 0.1).
Insert("h", 0.01).
Replace("k", "s", 0.001).
Replace("e", "i", 0.0001)
fmt.Println(wr.Distance(a, b))
// Output:
// 0.1111
調整するときに分類精度を評価するのが面倒なのでtools.Evaluate()というのも作りました。tools.EvaluateCSV()ならCSVでテストデータを用意できるので便利。
もっと細かく調整したい場合はlsdp.DistanceMeasurer インターフェイスを実装する必要があります。
ただロジック的な変更のみでパラメータが無い場合はいちいち構造体を定義するのも面倒なので、こちらの記事を参考に直接関数で指定できるようにしてみました。
Goのメソッドは構造体以外にでも定義できるしそれが便利なこともよくある - Qiita
// 長さの差を距離とする
func lenDiff(a, b string) float64 {
d := utf8.RuneCountInString(a) - utf8.RuneCountInString(b)
return math.Abs(float64(d))
}
func main() {
var d lsdp.DistanceFunc = lenDiff
fmt.Println(d.Distance("kitten", "shitting"))
// Output:
// 2
group := []string{"", "a", "ab", "abc"}
s, dist := lsdp.Nearest(d, "xx", group)
fmt.Println(s, dist)
// Output:
// ab 0
}
Goで書いた感想
Goでライブラリを書く経験はそれほどなかったのでいろいろ勉強になりました。
interfaceの使い方
Effective Goでこんな一節があったのでNormalized()の実装で実践してみました。
Generality
If a type exists only to implement an interface and will never have exported methods beyond that interface, there is no need to export the type itself.
Effective Go - The Go Programming Language
構造体を作ってInterfaceとして返すようにしておけば実装の詳細を隠せるのであとで変更しやすいです。Go moduleだと後方互換性が大事なのでこうしておくとのちのち楽です。
ベンチマークテストたのしい
Goの標準ライブラリのコミットログを見てるとベンチマークテストの結果が貼り付けられたものがあります（例：string）。効果が分かりやすいし、なんかかっこいいので真似することにしました。
Big Sky :: golang でパフォーマンスチューニングする際に気を付けるべきこと
単純な比較ならbenchcmpというのもあります。入力をランダム生成して複数回試行するようなベンチマークならbenchstatのほうが良さそう。
アルゴリズム的なやつ
コスト計算を工夫してメモリ削減
レーベンシュタイン距離のアルゴリズム（解説）では文字列１、２の先頭からの部分列に対して段階的にコストを計算する方法を使います。空行から文字列全体なので文字列１，２がそれぞれN文字、M文字ならば N+1行 M+1列の表を作ります。
詳しい説明は省きますが、現在の行を計算するのに必要なのは一つ前の行の値だけなので実際に必要な記憶領域は(N+1)*2だけです。レーベンシュタイン距離の実装を見てみるとN+1の配列２つを互い違いに使うことで表の代用をする方法が多いです。
ベンチマークテストを追加した影響でもっと効率化できないか考えるようになりメモリ削減のアイデアを思いつきました。表のあるコスト(i, j)の計算に必要なコストは左(i-1, j)、左上(i-1, j-1)、上(i, j-1)の３つだけです。コスト(i, j)の計算が終わったら次は(i+1, j)に移るので、実は左上(i-1, j-1)の値はもう参照しません。だったら左(i-1, j)の値で上書きしちゃえばいいのでは？というが思いついたアイデア。これによって記憶領域はN+2で済みます。
たぶん既出アイデアだと思うけどそこそこ高速化できたので気分がいい。
Performance improvement for accumulateCost() · deltam/go-lsd-parametrized@61be4fe
ベンチマークテスト万歳！
重み付き〜の定義
最初かんぜんに勘違いしてた、はずかしい…
アルゴリズム - 重み付きレーベンシュタイン距離の定義について - スタック・オーバーフロー
勘違いの副産物で削除・挿入・置換ごとの最短回数を集計する関数ができました（通常のレーベンシュタイン距離はコストは全部合計するため編集種別ごとの回数は分からない）。
lsdp.CountEdit()
なんかあったらissue、PullReq投げてくださいー。
おわり。
0 件のコメント:
コメントを投稿