修改Levenshtein距离函数以计算两组x-y坐标之间的距离？

Question

我一直在尝试修改Levenshtein距离函数，使其能够找到两条线或一组x-y坐标之间的距离（换句话说，这些线的相似度或差异性，而不是它们的几何距离）。但我遇到了一些问题。我知道如何使用上面的值获取删除成本，以及使用左侧的值获取添加成本，但在替换过程中，我尝试使用欧几里得距离，但它对我没有起作用。

如果您能指出我做错了什么，那就太棒了。

以下是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

- HFLW

---

我希望你知道，有更简单的方法来“找到两条线或一组x-y坐标之间的距离”。 - spender

当我说“距离”时，我指的是两条线路之间的相似或不同程度。 - HFLW

我认为这是一个统计学问题，而不是几何学问题。 - ironfroggy

顺便提一下，你可以使用勾股定理来计算两点之间的距离。 - Anderson Green

Answer 1

如果我理解你的问题正确，那么你应该完全删除计算两点之间欧几里得距离的代码！

首先，让我重述一下你的问题：

你有两组点，例如：

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

你试图计算这两个集合之间的Levenshtein距离。你用“点”代替“字母”。

到目前为止，这是有意义的。只需将Levenshtein算法中的“字母”替换为“点”，就完成了！

但你犯了一个错误：原始的Levenshtein算法不会计算两个字母之间的距离，例如distance(a,b)=1或distance(a,d)=3。

你试图使用euclideanDistance()函数扩展算法以实现此功能。但Levenshtein算法并不适用于这种情况。如果你仔细看一下，你会发现它行不通（矩阵中的值具有含义，并且每个循环迭代使用在先前迭代中计算的矩阵中的值）。

Levenshtein距离是编辑距离，而不是几何距离。你试图改变它，使它计算编辑和几何距离的混合。这种混合没有意义，是无用和错误的，我认为。

结论

要计算两组x-y坐标的莱文斯坦距离，您应该将euclidianDistance()替换为简单的相等比较(a[0]==b[0] && a[1]==b[1])。

然后莱文斯坦算法将给出一个“编辑距离”。

- Frunsi

Answer 2

使用几何学计算两条线之间的距离不是更聪明吗？或者有特定的原因不想使用它。

由于两条直线总是有一个交点，除非它们是平行的（编辑，谢谢），所以很容易计算最小距离：那就是0或插入一些可以在谷歌上找到的数学公式！

- Pindatjuh

---

你的意思是除非它们是并行的。 - Anurag

当我说“距离”时，我的意思更多地是指这两行有多相似或不同。 - HFLW

请注意，提问者谈论的是两组“x-y坐标”，而不仅仅是两个x-y坐标。你无法以任何精确的方式在两组点之间画出一条直线。 - ironfroggy

问题确实提到了“两条直线之间的距离，或者一组x-y坐标”，但这些陈述在一起没有意义。 - Anurag

Answer 3

我不明白为什么你要用Levenshtein算法，似乎通过简单的计算可以得到更好的结果。

• 要找到线条之间的角度差异，你可以简单地找到每条线的角度（arctan((x_1-x_2)/(y_1-y_2)))并相减。
• 要找到线条的平均距离，你可以使用距离公式，以每条线的第一个点和第二个点为基础，并将这些距离平均在一起。

除此之外（除非你的线条是在三维空间中），没有其他东西可以真正“比较”它们。

也许我误解了。你是想比较线条的字符串值吗？

- mattbasta