为什么这两个字符串的 Levenshtein 距离得分这么低?
Why is the Levenshtein distance score so low for these two strings?
我正在使用 Levenshtein 距离算法来查找相似的字符串,目前我的接受分数为 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()]
}
这里的算法有问题还是正确的分数?
你的结果是正确的。
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
我正在使用 Levenshtein 距离算法来查找相似的字符串,目前我的接受分数为 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()]
}
这里的算法有问题还是正确的分数?
你的结果是正确的。
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