Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
23
Help us understand the problem. What is going on with this article?
@tenten1010

編集距離についての説明及びPythonでの実装

More than 3 years have passed since last update.

アルゴリズムの説明

編集距離(レーベンシュタイン距離)はつまりある文字列をもう一つの文字列に変えるためかかるステップ数
そのステップは、
・一文字を削除する
・任意の一文字を挿入する
・文字一文字を他の文字と置き換える
のいずれかである

まずレーベンシュタイン距離のアルゴリズムを理解しよう

例えば文字列cafecoffeeの場合だと
cafe→caffe→coffe→coffee
こんな感じですね

最初はまず表を作りましょう

c o f f e e
c
a
f
e

初期値を入れましょう
対象文字列が空の時(対象文字列はこれからちょっとづつ増やす)、もちろんレーベンシュタイン距離は文字列の長さと等しい
なので

c o f f e e
0 1 2 3 4 5 6
c 1 *
a 2
f 3
e 4

(3,3)の「」から本番のアルゴリズム始まります
これから残ったセルは、すべてこの下の最小値になります
・もしこのセルにある列の一番上の文字と、このセルにある行の一番左の文字が同じであれば、このセルの値は左上のセルの値と等しい、そうじゃなければ左上のセルの値+1になる
・左のセルの値+1
・上のセルの値+1

ここでは、(3,3)の場合だと
・(3,3)にある列の一番上の文字"c"と行の一番左の文字"c"が同じなので0になる
・(2,3)になるため1になる
・(3,2)になるため1になる
この上の三つの値の最小値を取るため、(3,3)が0になる

c o f f e e
0 1 2 3 4 5 6
c 1 0
a 2
f 3
e 4

このように、すべてのセルを埋めよう

c o f f e e
0 1 2 3 4 5 6
c 1 0 1 2 3 4 5
a 2 1 1 2 3 4 5
f 3 2 2 1 2 3 4
e 4 3 3 2 2 2 3

この表を得る。この表の一番右下の値がレーベンシュタイン距離になる

Python 3.5.2による実装

このアルゴリズムをプログラムにまとめると

levenshtein.py
class Levenshtein:
#ここで配列を立ち上げて、初期値を入れる
    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance
#セルに値を入れる
    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

if __name__ == '__main__':
    str1 = 'coffee'
    str2 = 'cafe'
    leven = Levenshtein(str1,str2)
    print(leven.dist)
23
Help us understand the problem. What is going on with this article?
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
tenten1010
早稲田基幹理工学部表現工学科4年 大学から日本来ました留学生です 日本語はビミョいです😅

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
23
Help us understand the problem. What is going on with this article?