Minimum Edit Distance

今回は文字間の距離を計算するMinimum Edit Distanceについて説明したいと思います。普通に暮らしていたらMinimum Edit Distanceは使わないでしょうね笑それでも説明します。

まずは具体的な例としてintentionとexecutionという文字間の距離を測りたいとします。

intentionという文字列を文字一つ一つ順に見ていき文字の削除、挿入、転換を繰り返してexecutionに変換すると下図のようになるとおもいます。

f:id:tsurutan:20160518224058p:plain

dはdeletesはsubstitution,iはinsertionの略です。 delete, insertionを使ったとき文字間は1離れ、substitutionを使った場合文字間は2離れているとします。（ただし,substitutionで転換する文字が同じ場合は0）

f:id:tsurutan:20160518223443p:plain

この場合dssisとなっているので距離は8となります。

このような流れをひとつひとつ考えていくととても大変ですのでこれをアルゴリズム化してコンピューター上で計算できるようにしましょう。

アルゴリズム化するため下記のように定義します。ただしsourceは縦軸、targetは横軸,#は空文字としています。またtarget i-1, source i -1などのように1引かれているのは先頭に#がついているため、その長さ分調整するために1引かれています。

f:id:tsurutan:20160518230404p:plain

文字	意味
distance	距離の配列
ins-cost	挿入時の距離
sub-cost	転換時の距離
del-cost	削除時の距離
source	変換される文字配列
target	変換後の文字配列

この式を適用し先ほどのintentionとexecutionをテーブルを使い計算すると下記のようになります。

f:id:tsurutan:20160518230745p:plain

さて後はこのアルゴリズムをコードに直すだけです。コードのフローは下記のようになります。

f:id:tsurutan:20160518230440p:plain

こちらをPythonで書いてみると

# coding: UTF-8

INS_COST = 1
DEL_COST = 1
target = raw_input("input target ")
source = raw_input("input source ")

# increase length for '#'
target_len = len(target) + 1
source_len = len(source) + 1
distance = [[0 for i in range(target_len)] for j in range(source_len)]
distance[0][0] = 0


def calc():
    for i in range(1, source_len):
        distance[i][0] = distance[i - 1][0] + INS_COST

    for i in range(1, target_len):
        distance[0][i] = distance[0][i - 1] + INS_COST

    for i in range(1, source_len):
        for j in range(1, target_len):
            distance[i][j] = min(distance[i - 1][j] + INS_COST,
                                 distance[i - 1][j - 1] + sub_cost(target[j - 1], source[i - 1]),
                                 distance[i][j - 1] + DEL_COST)
    print_table()


def sub_cost(target_char, source_char):
    if target_char == source_char:
        return 0
    else:
        return 2

def print_table():
    for i in range(source_len, 0, -1):
        print distance[i - 1]