変更Levenshtein距離関数の計算距離セットのx座標y座標?
-
21-09-2019 - |
質問
っていうのを変更すると、Levenshtein距離関数での距離と線セットのx座標y座標(つまり、どのように類似又は相異なり、ラインは、その幾何学的ます。私の走りくつかの問題点ものです。私だけの価値以上にコスト削除、左にまが置換んを利用することにしたのだろうeuchlidian距離れている方まで楽しめる、電話をかけてきました。
ばがどのようないくつかは間違っている。
こちらは当該コード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
解決
ばかなことが分かって良かったご質問を正しくあり、それが完全に除去し、コードの計算次元ユークリッド距離のポイント!
まず、枠ご質問:
いつのポイントなど
A = [ [1,1], [0,9], [3,3], [4,4] ]
B = [ [1,1], [2,2], [3,3], [4,4] ]
ごみについて計算するためlevenshtein距離の間に位置すること。きの代わりに"文字"と"点".
ここでは意味がある。で置き換えに"文字"にlevenshteinアルゴリズムのポイントだ。
だって間違い:元のLevenshteinアルゴリズム な計算間の距離の二つの文字, のように、例えば距離(a,b)=1または距離(a、d)=3となる。
また延長するアルゴリズムなどもふもふをご堪能ください(使用euclideanDistance()機能)。がlevenshteinアルゴリズムにすることではありません。している場合にはあままであるという動作しないの価値観のマトリクスを持つ意味を持つようになり、各ループの繰り返し使用価値のマトリクスした計算前の繰り返し処理).
Levenshtein距離は、編集距離の幾何学的距離をいう。また変更するには、その計算の編集および幾何学的距離をいう。この混んでいないことの意味で、無駄な、間違っているのは、まぁ.
結論
を計算するための levenshtein距離の二つのセットのx座標y座標, あきスペースにおeuclidianDistance()プ等との比較(a[0]==b[0] && a[1]==b[1]
).
そしてlevenshteinアルゴリズムでます---"の編集距離".
他のヒント
でしょうが、2本の線の間の距離を計算するための幾何学的形状を使用することがより賢いことではありませんか? それとも、それを使用したくない特定の理由がある。
彼らはの(編集、感謝)の平行でない限り、2行は常に、交差点のポイントを持っているので、は、それが最小の距離を計算するのは簡単です:それは0だかのいくつかの数学を挿入し、その缶Googleで見つけることがの!
かわからないのはなぜことはできませLevenshteinこれまり結果から算出します。
- の差の角度行きの角度をそれぞれの線(arctan((x_1-x_2)/(y_1-y_2)))減します。
- の平均距離のラインできるのは簡単での距離式の最初の行の各行の平均人の距離です。
その他(なおラインによる3D)、ほかには何もないのにどうしても"比較しています。
もっ誤解されてしまいます。おと比較する文字列の値です。