Изменение функции расстояния Левенштейна для вычисления расстояния между двумя наборами координат x-y?

Question

Я пытался поработать над модификацией функции расстояния Левенштейна, чтобы она могла определять расстояние между двумя линиями или наборами координат 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

Answer 1

Если я правильно понял ваш вопрос, то вам следует полностью удалить код для вычисления евклидова расстояния между двумя точками!

Во-первых, позвольте мне переформулировать ваш вопрос:

У вас есть два набора точек, например

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

Вы пытаетесь вычислить расстояние Левенштейна между этими двумя наборами.Вы заменяете "буквы" на "точки".

До этого момента это имеет смысл.Просто замените "буквы" в алгоритме Левенштейна точками, и все готово!

Но ты совершил ошибку:Оригинальный алгоритм Левенштейна не вычисляет расстояния между двумя буквами, как , например ,расстояние (a, b)= 1 или расстояние (a, d)= 3.

Вы пытались расширить алгоритм с помощью такой вещи (используя функцию EuclideanDistance()).Но алгоритм Левенштейна не предназначен для таких вещей.И если вы внимательно посмотрите на это, вы увидите, что это не сработает (значения в матрице имеют значение, и каждая итерация цикла использует значения в матрице, которые были вычислены на предыдущей итерации).

Расстояние Левенштейна - это расстояние редактирования, а не геометрическое расстояние.Вы пытались изменить его, чтобы он вычислял сочетание редактирования и геометрического расстояния.Это сочетание не имеет никакого смысла, оно бесполезно и неправильно, ИМХО.

Заключение

Чтобы вычислить расстояние Левенштейна двух наборов координат x-y, вы должны заменить свой euclidianDistance() простым сравнением на равенство (a[0]==b[0] && a[1]==b[1]).

Затем алгоритм Левенштейна выдаст вам "расстояние редактирования".

Answer 2

Не было бы разумнее использовать геометрию для вычисления расстояния между двумя линиями?Или есть какая-то конкретная причина, по которой вы не хотели бы это использовать.

Поскольку две прямые всегда имеют точку пересечения, если только они не параллельны (отредактируйте, спасибо), легко вычислить наименьшее расстояние:это 0 или вставьте некоторые математические данные, которые можно найти в Google!

Answer 3

Я не понимаю, зачем вам использовать Левенштейна для этого, похоже, что вы получили бы гораздо лучшие результаты от простых вычислений.

• Чтобы найти разницу в углах линий, вы могли бы просто найти угол для каждой линии (arctan((x_1-x_2)/(y_1-y_2))) и вычесть их.
• Чтобы найти среднее расстояние между линиями, вы могли бы просто использовать формулу расстояния с первой точкой каждой линии и второй точкой каждой линии и усреднить эти расстояния вместе.

Кроме этого (если только ваши линии не выполнены в 3D), вам не с чем их действительно "сравнивать".

Возможно, я неправильно понял.Вы хотите сравнить строковые значения для строк?