Установить стоимость для расстояния Левенштейна?

Question

У меня есть код python, который успешно выполняется для вычисления расстояния Левенштейна, но теперь я хочу вычислить затраты на вставку, замену и удаление.

Мой фрагмент кода

def levenshtein_distance(first, second): 

    matrix = np.zeros((len(first)+1,len(second)+1), dtype=np.int)
    for i in range(len(first)+1): 
        for j in range(len(second)+1): 
            if i == 0:  
                matrix[i][j] = j  

            elif j == 0: 
                matrix[i][j] = i
            else: 
                matrix[i][j] = min(matrix[i][j-1] + 2,  
                                   matrix[i-1][j] + 1,        
                                   matrix[i-1][j-1] + 3)     
    return matrix[len(first)][len(second)]

Мои затраты

Вставка: 2 Удалить: 1 Заменить: 3

При указании этих затрат внутри функции min () он каким-то образом просчитывает стоимость замещения. Как рассчитать стоимость?

Answer 1

Нигде в вашем коде вы не сравниваете содержимое first или second. Посмотрите на эту реализацию псевдокода: https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_full_matrix