編集距離 (Levenshtein Distance)をpython で求める

More than 3 years have passed since last update.

編集距離については、ちょっと古いですが伊藤直也さんの記事が参考になります。

簡単にいうと、2つの文字列の近さを数値として表す方法です。

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


準備

python-Levenshtein というパッケージがあったのでそれを入れてみます。

$ sudo pip install python-Levenshtein


やってみる

こんな感じのコードを書いてみます。

#!/usr/bin/env python

# coding: utf8

import Levenshtein

string1 = "井上泰治"
string2 = "井上泰次"

string1 = string1.decode('utf-8')
string2 = string2.decode('utf-8')

print Levenshtein.distance(string1, string2)

$ python levenshtein.py

1

日本語でもOKですね。

1文字取り替えれば正解の文字になるので、編集距離は1になります。

僕はpython という文字を入力するのが苦手で気づくとpyhtonとかになってしまっているのですが、

pyhton と python の編集距離は 2になります。(2つの文字を入れ替えると同じになるので)


おまけ

ドキュメント を見ると、他にも、 Jaro-Winkler 距離 の計算とかいろいろできるようですね。


おまけ2

下記のような感じでMySQLのストアドとして登録しておくと、ORDER BY LEVENSHTEIN(title, "ほげほげ") みたいに

文字の近い順に出してくれるので便利です。

ただし、インデックスは効かないので、全レコード捜査になってレコード数が多いとかなり重いクエリになります。

https://github.com/fza/mysql-doctrine-levenshtein-function


関連

PHP - [マルチバイト対応] レーベンシュタイン距離を求める - Qiita