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

Question

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

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 ()).Но алгоритм Левенштейна не предназначен для таких вещей.И если вы внимательно посмотрите на него, вы увидите, что он не будет работать (значения в матрице имеют значение, и каждая итерация цикла использует значения в матрице, которые были вычислены в предыдущей итерации).

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

Заключение

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

Тогда алгоритм Левенштейна даст вам «расстояние редактирования».

Answer 2

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

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

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

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

Answer 3

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

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