編集距離については、ちょっと古いですが伊藤直也さんの記事が参考になります。
簡単にいうと、２つの文字列の近さを数値として表す方法です。
参考: 編集距離 (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, "ほげほげ") みたいに
文字の近い順に出してくれるので便利です。
ただし、インデックスは効かないので、全レコード捜査になってレコード数が多いとかなり重いクエリになります。