👨‍🌾

Go の文字列距離実装シリーズ

2022/12/25に公開

はじめに

検索システムを作る時に、ちょっとした揺らぎがあってもマッチさせたい要件があります。例えば「こんにちわ」と入力されても「こんにちは」を候補として出したい場合もあります。

そんなケースでは文字列距離アルゴリズムを使います。実用されている身近な例としては、git コマンドで checkout をタイプするつもりで chekcout とタイプした時に出るアレです。

$ git chekcout
git: 'chekcout' is not a git command. See 'git --help'.

The most similar command is
        checkout

あれもこれからご紹介するレーベンシュタイン距離を使って実装されています。

https://github.com/git/git/blob/7c2ef319c52c4997256f5807564523dfd4acdfc7/help.c#L656-L657

文字列距離いろいろ

単純に文字列距離アルゴリズムといっても沢山あります。

ハミング距離

長さが同じ文字列の異なる部分をカウントする事で文字列の距離を表すアルゴリズムです。

https://ja.wikipedia.org/wiki/ハミング距離

以下、Go の実装。

https://github.com/mattn/go-hsd

レーベンシュタイン距離

2つの文字列を比較する際に、どの様な編集を行えば対象の文字列になるのかを計算し、その編集量で文字列の距離を表すアルゴリズムです。

https://ja.wikipedia.org/wiki/レーベンシュタイン距離

以下、Go の実装。

https://github.com/mattn/go-lsd

ジャロ・ウィンクラー距離

文字列の一部の類似度を文字列距離として表すアルゴリズムです。文字数が異なる場合でも高い類似度となるため人間の判断に近い文字列距離が出せると言われています。

https://ja.wikipedia.org/wiki/ジャロ・ウィンクラー距離

以下、Go の実装。

https://github.com/mattn/go-jsd

ダメラウ・レーベンシュタイン距離

基本はレーベンシュタイン距離ですが、転置を許容する事でレーベンシュタイン距離よりも厳密さのないあいまいな文字列でも近い距離が表せるアルゴリズムです。

https://ja.wikipedia.org/wiki/ダメラウ・レーベンシュタイン距離

以下、Go の実装。

https://github.com/mattn/go-dlsd

応用例

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