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

Вы пытаетесь вычислить расстояние levenshtein между этими двумя наборами. Вы заменяете «буквы» «точками».

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

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

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

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

Заключение

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

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

Answer 2

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

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

Answer 3

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

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

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

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