PythonのLevenshtein距離は編集距離として1だけ与えます

Question

私は2つのリスト（1つはエラーと他の正しいデータで）を読むためのPythonプログラムを持っています。エラーのあるリストのすべての要素を、正しいリストのすべての要素と比較する必要があります。比較した後、私は比較された各ペア間のすべての編集距離を取得します。今私は与えられたエラーデータのための最小の編集距離を見つけることができ、私の正しいデータを取得します。

私は編集距離を計算するのにlevenshtein距離を使用しようとしていますが、すべての編集距離が1であるとしてもそれは間違っています。

これは、レーベンシュタイン距離を計算するコードが正しくないことを意味します。私はこれを解決するために苦労しています。助けて！

マイコード

import csv 

def lev(a, b): 
    if not a: return len(b) 
    if not b: return len(a) 
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1) 

if __name__ == "__main__": 

    with open("all_correct_promo.csv","rb") as file1: 
     reader1 = csv.reader(file1) 
     correctPromoList = list(reader1) 
     #print correctPromoList 

    with open("all_extracted_promo.csv","rb") as file2: 
     reader2 = csv.reader(file2) 
     extractedPromoList = list(reader2) 
     #print extractedPromoList 

    incorrectPromo = [] 
    count = 0 
    for extracted in extractedPromoList: 
     if(extracted not in correctPromoList): 
      incorrectPromo.append(extracted) 
     else: 
      count = count + 1 
    #print incorrectPromo 

    for promos in incorrectPromo: 
     for correctPromo in correctPromoList: 
      distance = lev(promos,correctPromo) 
      print promos, correctPromo , distance 

Answer 1

実装が正しいです。私はあなたのコメントに気づいたように、あなたの問題

def lev(a, b): 
    if not a: return len(b) 
    if not b: return len(a) 
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1) 


print lev('abcde','bc') # prints 3, which is correct 
print lev('abc','bc') # prints 1, which is correct 

あなたがメソッドを呼び出したときに、おそらくです：私はこれをテストした

a = ['NSP-212690'] 
b = ['FE SV X'] 

print lev(a,b) # prints 1 which is incorrect because you are comparing arrays, not strings 
print lev(a[0],b[0]) # prints 10, which is correct 

だから、何を行うことができますことは次のとおりです。前

"lev（a、b）"を呼び出し、各配列の最初の要素を抽出する

def lev(a, b): 
    if not a: return len(b) 
    if not b: return len(a) 
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1) 

a = ['NSP-212690'] 
b = ['FE SV X'] 
a = a[0] # this is the key part 
b = b[0] # and this 
print lev(a,b) # prints 10, which is correct 

とにかく、

def lev(seq1, seq2): 
    oneago = None 
    thisrow = range(1, len(seq2) + 1) + [0] 
    for x in xrange(len(seq1)): 
     twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1] 
     for y in xrange(len(seq2)): 
      delcost = oneago[y] + 1 
      addcost = thisrow[y - 1] + 1 
      subcost = oneago[y - 1] + (seq1[x] != seq2[y]) 
      thisrow[y] = min(delcost, addcost, subcost) 
    return thisrow[len(seq2) - 1] 

または多分このわずかに変更されたバージョン：パフォーマンスは

私が代わりにこの実装をお勧めします（wikipedia-levenshteinソース）：veeeery悪いので、筆記体の実装は、

def lev(seq1, seq2): 
    if not a: return len(b) 
    if not b: return len(a) 
    oneago = None 
    thisrow = range(1, len(seq2) + 1) + [0] 
    for x in xrange(len(seq1)): 
     twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1] 
     for y in xrange(len(seq2)): 
      delcost = oneago[y] + 1 
      addcost = thisrow[y - 1] + 1 
      subcost = oneago[y - 1] + (seq1[x] != seq2[y]) 
      thisrow[y] = min(delcost, addcost, subcost) 
    return thisrow[len(seq2) - 1] 

Answer 2

Pythonパッケージがありますlevenshtein distanceを実装するもの：python-levenshtein

インストールするには

pip install python-levenshtein 

がそれを使用するには：

>>> import Levenshtein 
>>> string1 = 'dsfjksdjs' 
>>> string2 = 'dsfiksjsd' 
>>> print Levenshtein.distance(string1, string2) 
3