Расстояние Levenshtein в python, дающее только 1 как расстояние редактирования

Question

У меня есть программа python для чтения двух списков (одна с ошибками и другая с правильными данными). Каждый элемент в моем списке с ошибкой должен сравниваться с каждым элементом в моем правильном списке. После сравнения я получаю все расстояние редактирования между каждой сравниваемой парой. теперь я могу найти наименьшее расстояние редактирования для данных ошибок и получить мои правильные данные.

Я пытаюсь использовать расстояние levenshtein для вычисления расстояния редактирования, но его возвращающее все расстояние редактирования равно 1, даже если это неверно.

Это значит, что код для расчета levenshtein distance неправильный. Я изо всех сил пытаюсь найти решение для этого. ПОМОГИТЕ!

Мой код

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 

Итак, что вы можете сделать, это:

Перед тем, звоните в «лева (а, б)», извлечь первый элемент каждого массива

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 

Во всяком случае, я бы не рекомендовал вам, что ре скоропись реализация, потому что производительность veeeery бедная

Я бы рекомендовал эту реализацию вместо (источник: wikipedia-levenshtein)

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] 

или, возможно, это слегка измененная версия:

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 доступный, который реализует расстояние левенштейна: python-levenshtein

Для его установки:

pip install python-levenshtein 

Чтобы использовать его:

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