4

私は、レーベンシュタイン距離関数を変更して、2つの線の間の距離、または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
4

3 に答える 3

1

私があなたの質問を正しく理解したなら、2点間のユークリッド距離を計算するためのコードを完全に削除する必要があります！

まず、あなたの質問を言い換えさせてください。

2セットのポイントがあります。

A = [ [1,1], [0,9], [3,3], [4,4] ]
B = [ [1,1], [2,2], [3,3], [4,4] ]

これらの2つのセット間のレーベンシュタイン距離を計算しようとします。「文字」を「ポイント」に置き換えます。

この時点まで、それは理にかなっています。レーベンシュタインアルゴリズムの「文字」をポイントに置き換えるだけで完了です。

しかし、あなたは間違いを犯しました。元のレーベンシュタインアルゴリズムは、たとえばdistance（a、b）= 1やdistance（a、d）= 3のように、2文字間の距離を計算しません。

あなたはそのようなことでアルゴリズムを拡張しようとしました（euclideanDistance（）関数を使用して）。しかし、レーベンシュタインアルゴリズムはそのようなことを意図したものではありません。そして、よく見ると、機能しないことがわかります（マトリックスの値には意味があり、各ループの反復では、前の反復で計算されたマトリックスの値が使用されます）。

レーベンシュタイン距離は編集距離であり、幾何学的距離ではありません。編集と幾何学的距離の組み合わせを計算するように変更しようとしました。このミックスは意味がありません、それは役に立たず、間違っています、私見。

結論

2セットのxy座標のレーベンシュタイン距離を計算するには、euclidianDistance（）を単純な等式比較（a[0]==b[0] && a[1]==b[1]）に置き換える必要があります。

次に、レーベンシュタインアルゴリズムは「編集距離」を提供します。

于 2010-01-18T15:07:57.400 に答える
0

なぜこれにレーベンシュタインを使用するのかわかりません。単純な計算ではるかに良い結果が得られるようです。

  • 線の角度の違いを見つけるには、各線の角度（arctan（（x_1-x_2）/（y_1-y_2）））を見つけてそれらを引くだけです。
  • 線の平均距離を見つけるには、各線の最初の点と各線の2番目の点で距離の式を使用し、それらの距離を平均するだけです。

それ以外に（ラインが3Dでない限り）、それらを実際に「比較」するものは他にありません。

おそらく私は誤解しました。行の文字列値を比較しようとしていますか？

于 2010-01-18T14:39:16.513 に答える
0

2 本の線の間の距離を計算するために幾何学を使用する方が賢明ではないでしょうか? または、それを使用したくない特定の理由があります。

2 本の線には常に交点があるため、それらが平行でない限り(編集、感謝)、最小距離を計算するのは簡単です。

于 2010-01-17T22:48:16.033 に答える