我一直在尝试修改 Levenshtein Distance 函数,以便它可以找到两条线之间的距离,或 xy 坐标集(换句话说,线的相似或不同,而不是它们的几何距离)。我遇到了一些问题。我知道您如何使用上面的值来获得删除成本,而左边的值是为了获得加法,但是在替换过程中我试图使用欧几里得距离,它对我不起作用。
如果你能指出我做错了什么,那就太棒了。
这是javascript中的相关代码:
padlock.dtw = {
_deletionCost: 1,
_insertionCost: 1,
levenshtein: function(a,b){
var l1 = a.length, l2 = b.length;
if (Math.min(l1, l2) === 0) {
return Math.max(l1, l2);
}
var i = 0, j = 0, d = [];
for (i = 0 ; i <= l1 ; i++) {
d[i] = [];
d[i][0] = i;
}
for (j = 0 ; j <= l2 ; j++) {
d[0][j] = j;
}
for (i = 1 ; i <= l1 ; i++) {
for (j = 1 ; j <= l2 ; j++) {
d[i][j] = Math.min(
d[i - 1][j] + this._deletionCost, /* deletion */
d[i][j - 1] + this._insertionCost, /* addition */
d[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? 0 : this.euclideanDistance(a[i-1], b[j-1])) /* substitution, use euchlidean distance as cost */
);
}
}
this._debugPrintMatrix(d);
return d[l1][l2];
},
euclideanDistance: function(a, b){
var xd = a[0]-b[0];
var yd = a[1]-b[1];
return Math.abs(Math.sqrt(Math.pow(xd, 2) + Math.pow(yd, 2)));
},
_debugPrintMatrix: function(m){
for(var i=0;i<m.length;i++){
console.log.apply(this, m[i]);
}
}
}
样本输出:
>>> padlock.dtw.levenshtein( [ [1,1], [0,9], [3,3], [4,4] ], [ [1,1], [2,2], [3,3], [4,4] ] )
Distance Matrix:
0 1 2 3 4
1 0 1 2 3
2 1 2 3 4
3 2 2.414213562373095 2 3
4 3 3.414213562373095 3 2
Final Distance: 2