Go の文字列距離実装シリーズ
はじめに
検索システムを作る時に、ちょっとした揺らぎがあってもマッチさせたい要件があります。例えば「こんにちわ」と入力されても「こんにちは」を候補として出したい場合もあります。
そんなケースでは文字列距離アルゴリズムを使います。実用されている身近な例としては、git コマンドで checkout をタイプするつもりで chekcout とタイプした時に出るアレです。
$ git chekcout
git: 'chekcout' is not a git command. See 'git --help'.
The most similar command is
checkout
あれもこれからご紹介するレーベンシュタイン距離を使って実装されています。
文字列距離いろいろ
単純に文字列距離アルゴリズムといっても沢山あります。
ハミング距離
長さが同じ文字列の異なる部分をカウントする事で文字列の距離を表すアルゴリズムです。
以下、Go の実装。
レーベンシュタイン距離
2つの文字列を比較する際に、どの様な編集を行えば対象の文字列になるのかを計算し、その編集量で文字列の距離を表すアルゴリズムです。
以下、Go の実装。
ジャロ・ウィンクラー距離
文字列の一部の類似度を文字列距離として表すアルゴリズムです。文字数が異なる場合でも高い類似度となるため人間の判断に近い文字列距離が出せると言われています。
以下、Go の実装。
ダメラウ・レーベンシュタイン距離
基本はレーベンシュタイン距離ですが、転置を許容する事でレーベンシュタイン距離よりも厳密さのないあいまいな文字列でも近い距離が表せるアルゴリズムです。
以下、Go の実装。
応用例
go-sqlite3 ではユーザ関数を追加する事ができます。上記のレーベンシュタイン距離の実装 go-lsd を使って SQL から呼び出せる関数を作ります。
package main
import (
"database/sql"
"fmt"
"log"
"os"
"github.com/mattn/go-lsd"
"github.com/mattn/go-sqlite3"
)
func main() {
sql.Register("sqlite3_custom", &sqlite3.SQLiteDriver{
ConnectHook: func(conn *sqlite3.SQLiteConn) error {
if err := conn.RegisterFunc("levenshtein", lsd.StringDistance, true); err != nil {
return err
}
return nil
},
})
db, err := sql.Open("sqlite3_custom", "./catalog.sqlite")
if err != nil {
log.Fatal(err)
}
defer db.Close()
rows, err := db.Query(`
SELECT name, price FROM catalog WHERE levenshtein(name, ?) < 3
`, os.Args[1])
if err != nil {
log.Fatal(err)
}
defer rows.Close()
for rows.Next() {
var name string
var price int
err = rows.Scan(&name, &price)
if err != nil {
log.Fatal(err)
}
fmt.Println(name, price)
}
}
go-sqlite3 の RegisterFunc は便利に出来ているので、変にラッパー関数を作ることなく SQL 側に関数をエクスポートできます。では実際試してみましょう。DDL は以下の通り。
create table catalog(name text not null primary key, price integer not null);
insert into catalog(name, price) values('みかん', 180);
insert into catalog(name, price) values('バナナ', 200);
insert into catalog(name, price) values('リンゴ', 150);
コマンドライン引数で名称を少し惜しい感じに渡してみます。
$ ./main みかん
みかん 180
$ ./main おかん
みかん 180
$ ./main バカナ
バナナ 200
上手く動きました。
まとめ
文字列距離アルゴリズムを数個ご紹介するついでに、僕が実装した物を宣伝しました。また go-sqlite3 から扱う方法をご紹介しました。ぜひ遊んでみて下さい。
Discussion