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

  • 18
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

編集距離については、ちょっと古いですが伊藤直也さんの記事が参考になります。
簡単にいうと、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