Help us understand the problem. What is going on with this article?

編集距離 (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

mercari
フリマアプリ「メルカリ」を、グローバルで開発しています。
https://tech.mercari.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away