我一直在尝试修改Levenshtein距离函数,使其能够找到两条线或一组x-y坐标之间的距离(换句话说,这些线的相似度或差异性,而不是它们的几何距离)。但我遇到了一些问题。我知道如何使用上面的值获取删除成本,以及使用左侧的值获取添加成本,但在替换过程中,我尝试使用欧几里得距离,但它对我没有起作用。
如果您能指出我做错了什么,那就太棒了。
以下是javascript中相关的代码:
如果您能指出我做错了什么,那就太棒了。
以下是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