2017/02/27

Recent entries from same category

  1. Visual Studio Code で ssh 先のファイルを編集する方法
  2. 虫が入り込むその瞬間
  3. ダウンロードの進捗プログレスバー実装は可能か
  4. sudo コマンド書いた。
  5. Re: Goでコマンドライン引数と環境変数の両方からflagを設定したい

元ネタはずいぶんと昔の記事なのだけど。

編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン...

http://d.hatena.ne.jp/naoya/20090329/1238307757

思い付きはまったく関係ない所から。

これを週末にやってました。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 伊藤直哉 を実行すると以下の様に「伊藤直哉」に近い単語がマッチする。しかも色付き!(ポイント高い)

lsdgrep

距離が3なのでマッチする単語も荒い。距離を1にするとそこそこ近い物がマッチする。

lsdgrep

いつもの事ながら研究材料なので実用的なものを作るつもりは無い。


blog comments powered by Disqus