Почему минимальная оценка Левенштейна для этих двух строк?

Question

Я использую алгоритм расстояния Левенштейна, чтобы найти похожие строки, и в настоящее время у меня есть оценка для принятия как 12 (потому что некоторые из моих строк имеют до 5 слов). Но я был удивлен, чтобы увидеть ниже двух строк получить балл 11, они кажутся очень разными для меня ..

def string1 = "Facial Fuel" 
def string2 = "Calendula Toner" 

println("Result is ${distance(string1,string2)}"); 

def distance(String str1, String str2) { 
    def dist = new int[str1.size() + 1][str2.size() + 1] 
    (0..str1.size()).each { dist[it][0] = it } 
    (0..str2.size()).each { dist[0][it] = it } 

    (1..str1.size()).each { i -> 
    (1..str2.size()).each { j -> 
     dist[i][j] = [dist[i - 1][j] + 1, dist[i][j - 1] + 1, dist[i - 1][j - 1] + ((str1[i - 1] == str2[j - 1]) ? 0 : 1)].min() 
     } 
    } 
    return dist[str1.size()][str2.size()] 
} 

Что-то не так с алгоритмом здесь или что правый счет?

Answer 1

Ваш результат правильный.

string1: F a c i a  l . F u e l 
    operation: S C S S S I I C I C S S I C S 
    string2: C a l e n d u l a . T o n e r 

('.' означает ' ')

Операции

C : Copy 
    S : Substitue 
    I : Insert 
    D : Delete 

Левенштейн расстояние

S * 7 + I * 4 = 11