3

2つの弦の間の距離を教えてくれるプログラムがありますが、これは問題なく機能しています。

例えば

word 1 = hello
word 2 = hi

あるものから別のものに移動するのに5のコストがかかります（iのeへの置換は2であり、3つの挿入があります）。

基本的に、挿入コスト1、削除コスト1、置換は2です。コストを削減するために、文字列内で単語をシャッフルすることもできます。

アラインメントを表示できるように、どの操作がどの時点で発生しているかを覚えておく方法が必要です。

例えば

wax
S M S(substitute move substitute, cost of 4)
and

アイデアやヒントはありますか？

import sys
from sys import stdout


def  minEditDist(target, source):

    # Length of the target strings set to variables
    n = len(target)
    m = len(source)

    distance = [[0 for i in range(m+1)] for j in range(n+1)]

    for i in range(1,n+1):
        distance[i][0] = distance[i-1][0] + insertCost(target[i-1])

    for j in range(1,m+1):
        distance[0][j] = distance[0][j-1] + deleteCost(source[j-1])


    for i in range(1,n+1):
        for j in range(1,m+1):
           distance[i][j] = min(distance[i-1][j]+1,
                                distance[i][j-1]+1,
                                distance[i-1][j-1]+subCost(source[j-1],target[i-1]))

    # Return the minimum distance using all the table cells
    return distance[i][j]

def subCost(x,y):
    if x == y:
        return 0
    else:
        return 2

def insertCost(x):
    return 1

def deleteCost(x):
    return 1

# User inputs the strings for comparison
# Commented out here because cloud9 won't take input like this
# word1 = raw_input("Enter A Word: ")
# word2 = raw_input("Enter The Second Word: ")
word1 = "wax"
word2 = "and"
word1x = word1
word2x = word2
# Reassign variables to words with stripped right side whitespace
word1x = word1x.strip()
word2x = word2x.strip()

if(len(word1) > len(word2)):
    range_num = len(word1)
else:
    range_num = len(word2)

# Display the minimum distance between the two specified strings
print "The minimum edit distance between S1 and S2 is: ", minEditDist(word1x,word2x), "!"
print (word1x)
print (word2x)
4

2 に答える 2

1

あなたはこのようなものから始めることができます。

「S」の適切なデータを追加しました。

path = []

def  minEditDist(target, source):

    # Length of the target strings set to variables
    n = len(target)
    m = len(source)

    distance = [[0 for i in range(m+1)] for j in range(n+1)]

    for i in range(1,n+1):
        distance[i][0] = distance[i-1][0] + insertCost(target[i-1])

    for j in range(1,m+1):
        distance[0][j] = distance[0][j-1] + deleteCost(source[j-1])


    for i in range(1,n+1):
        for j in range(1,m+1):
           sc = subCost(source[j-1],target[i-1])
           distance[i][j] = min(distance[i-1][j]+1,
                                distance[i][j-1]+1,
                                distance[i-1][j-1]+sc)
           if distance[i-1][j]+1 > distance[i-1][j-1]+sc and distance[i][j-1]+1 > distance[i-1][j-1]+sc:
               path.append("S");

    print path

    # Return the minimum distance using all the table cells
    return distance[i][j]

def subCost(x,y):
    if x == y:
        return 0
    else:
        return 2

def insertCost(x):
    path.append("I")
    return 1

def deleteCost(x):
    path.append("D")
    return 1
于 2013-01-09T08:58:12.200 に答える
1

レーベンシュタイン距離を計算しています(または、操作のコストが異なるため、加重レーベンシュタインI距離を計算しています: / D=> 1, M=>2)。

操作の順序を取得する一般的な方法は、ある種のバックトレースを行うことです。

次の方法を検討してくださいbacktrace*:

...
# Return the minimum distance using all the table cells
def backtrace(i, j):
    if i>0 and j>0 and distance[i-1][j-1] + 2 == distance[i][j]:
        return backtrace(i-1, j-1) + "S"
    if i>0 and j>0 and distance[i-1][j-1] == distance[i][j]:
        return backtrace(i-1, j-1) + "M"
    if i>0 and distance[i-1][j] + 1 == distance[i][j]:
        return backtrace(i-1, j) + "D"
    if j>0 and distance[i][j-1] + 1 == distance[i][j]:
        return backtrace(i, j-1) + "I"
    return ""

return distance[i][j], backtrace(i, j)

distanceメソッドにネストされたメソッドとして追加したので、距離行列をパラメーターとして渡す必要はありません。

スクリプトが出力するようになりました

S1 と S2 の間の最小編集距離は (4, 'SMS') です。

また、Python でレーベンシュタイン距離を使用する場合は、Google コードに pylevenshteinという名前の高速な実装があることに注意してください。

* おそらく 100% 正確ではありません :-)

于 2013-01-09T09:54:22.243 に答える