単語間の削除の距離

Question

2つの単語を同じにするために削除する必要のある文字の数を調べようとしています。たとえば、 "at"、 "cat"は1になります。なぜなら私はc、 "boat"、 "got"を削除することができるから3、b、a、gを削除することができるからです。私はその単語の数を値として辞書に入れます。次に、辞書を繰り返して、そのキーが他の辞書に存在するかどうかを確認します。それ以外の場合は、その差に1を加えます。これは非常に非効率的なアルゴリズムですか？

しかし、私が必要とする削除の数を過大評価しています。

def deletiondistance(firstword, secondword): 
dfw = {} 
dsw = {} 
diff = 0 
for i in range(len(firstword)): 
    print firstword[i] 
    if firstword[i] in dfw: 
     dfw[firstword[i]]+=1 
    else: 
     dfw[firstword[i]]=1 
for j in range(len(secondword)): 
    if secondword[j] in dsw: 
     dsw[secondword[j]] +=1 
    else: 
     dsw[secondword[j]]=1 

for key, value in dfw.iteritems(): 

    if key in dsw: 
     #print "key exists" 
     pass 

    else: 
     diff +=1 

print "diff",diff 

Answer 1

@Hulkこれはレーベンシュタイン距離と類似して述べたように。唯一の違いは置換は許されないが、置換コストは2であり、これは両方の文字列から文字を削除するのと同じである。例：

def dist(s1, s2): 
    cur = list(range(len(s2) + 1)) 
    prev = [0] * (len(s2) + 1) 
    for i in range(len(s1)): 
     cur, prev = prev, cur 
     cur[0] = i + 1 
     for j in range(len(s2)): 
      # Substitution is same as two deletions 
      sub = 0 if s1[i] == s2[j] else 2 
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1) 

    return cur[-1] 

cases=[('cat','bat'), 
     ('bat','cat'), 
     ('broom', 'ballroom'), 
     ('boat','got'), 
     ('foo', 'bar'), 
     ('foobar', '')] 

for s1, s2 in cases: 
    print('{} & {} = {}'.format(s1, s2, dist(s1, s2))) 

出力：

cat & bat = 2 
bat & cat = 2 
broom & ballroom = 3 
boat & got = 3 
foo & bar = 6 
foobar & = 6 

Answer 2

あなたの目標はlevenshtein distanceと似ていると思います。

レーベンシュタイン距離は、2つのストリング間の距離を測定するための基準です。

ここにwiki-linkがあります。 https://en.wikipedia.org/wiki/Levenshtein_distance

ここでは、レビンステン距離のピピパッケージです。 https://pypi.python.org/pypi/python-Levenshtein

Answer 3

これにはdifflibを使用できます。

例：

import difflib 

cases=[('cat','bat'), 
     ('bat','cat'), 
     ('broom', 'ballroom'), 
     ('boat','got')] 

for a,b in cases:  
    print('{} => {}'.format(a,b)) 
    cnt=0 
    for i,s in enumerate(difflib.ndiff(a, b)): 
     if s[0]==' ': continue 
     elif s[0]=='-': 
      print(u'Delete "{}" from position {}'.format(s[-1],i)) 
     elif s[0]=='+': 
      print(u'Add "{}" to position {}'.format(s[-1],i))  
     cnt+=1 
    print("total=",cnt,"\n") 

プリント：

cat => bat 
Delete "c" from position 0 
Add "b" to position 1 
total= 2 

bat => cat 
Delete "b" from position 0 
Add "c" to position 1 
total= 2 

broom => ballroom 
Add "a" to position 1 
Add "l" to position 2 
Add "l" to position 3 
total= 3 

boat => got 
Delete "b" from position 0 
Add "g" to position 1 
Delete "a" from position 3 
total= 3