元ネタはずいぶんと昔の記事なのだけど。
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン...
http://d.hatena.ne.jp/naoya/20090329/1238307757
思い付きはまったく関係ない所から。
mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。
— Vim芸人 (@mattn_jp) February 25, 2017
これを週末にやってました。naoya さんの記事にも書かれている通り、Levenshtein Distance の実装はとてつもなく簡単。
GitHub - mattn/go-lsd
https://github.com/mattn/go-lsd
ついでにこれを使った grep コマンド作ったら面白いんじゃないかと思って O(N^2) になる事覚悟の上で実装してみた。
実装にあたってまず Unicode のクラスを識別する物を作った。
GitHub - mattn/go-unicodeclass
Unicode class package
https://github.com/mattn/go-unicodeclass
これは与えらえた rune が Unicode のどの部類に属するかを返すためのライブラリ。Vim のコードを一部参考にしました。もともとは bufio/scanner で与える区切り文字(デフォルトは改行)を Unicode のクラス区切りに出来ないかと思って実装しました。こんな風に使えます。
scan := bufio.NewScanner(strings.NewReader("本日は晴天なり"))
scan.Split(unicodeclass.SplitClass)
var got []string
for scan.Scan() {
got = append(got, scan.Text())
}
// "本日", "は", "晴天", "なり"
まぁ結果的に言えば後で追加した unicodeclass.Split で十分事足りましたが。で、出来上がったのが lsdgrep。
GitHub - mattn/lsdgrep
lsdgrep Fuzzy Grep using Levenshtein String Distance
https://github.com/mattn/lsdgrep
これを使えば例えば
俺の名前は伊藤直哉だ
もしかしたら俺は伊藤直かもしれない
ちょっと待ってくれ佐藤直哉をお忘れではないか
こんばんわ佐藤B作です
こんなテキストに対して lsdgrep -d 3 伊藤直哉 を実行すると以下の様に「伊藤直哉」に近い単語がマッチする。しかも色付き！(ポイント高い)
距離が3なのでマッチする単語も荒い。距離を1にするとそこそこ近い物がマッチする。
いつもの事ながら研究材料なので実用的なものを作るつもりは無い。
