Понимание BK Trees: как мы получаем диапазон (dn, d+n) из неравенства треугольника?

Question

Читая этот пост о BK Trees, я нашел следующий фрагмент немного запутанным:

"Предположим на мгновение, что у нас есть два параметра: запрос, строка, которую мы используем в нашем поиске, и n максимальное расстояние, на которое строка может быть от запроса и все еще возвращаемая. Скажем, мы берем произвольную строку, тестируем и сравниваем ее с запросом Назовите полученное расстояние d. Поскольку мы знаем, что выполняется неравенство треугольника, все наши результаты должны иметь самое большее расстояние d+n и, по крайней мере, расстояние dn от теста."

Я могу интуитивно увидеть, что если что-то d от слова, которое я ищу, и у меня есть терпимость n ошибка, тогда мне понадобится хотя бы d-n Расстояние от слова, на котором я нахожусь, чтобы "обратить" различия. Точно так же я могу иметь максимум d+n потому что после "изменения" различий я могу ввести еще больше различий.

Я запутался, как неравенство треугольника использовалось, чтобы получить это. Если мы допустим d(test, query) = d и d(query, found) <= n, то по неравенству:

d(test, query) + d(test, nextWordToSearch) >= d(query, found)
d + d(test, nextWordToSearch) >= n

Как мы можем найти

d - n <= d(test, nextWordToSearch) <= d + n

Answer 1

Используя ответ @templatetypedef, я смог использовать неравенство треугольника для нахождения верхней и нижней границ.

d(query, desiredNode) = n
d(query, test) = d1

d(query, test) + d(test, desiredNode) >= d(query, desiredNode)
d1 + d(test, desiredNode) >= n
d(test, desiredNode) >= |n - d1|

d(test, query) + d(query, desiredNode) >= d(test, desiredNode)
|d1 + n| >= d(test, desiredNode)

Следовательно:

|d1 + n| >= d(test, desiredNode) >= |d1 - n|

Абсолютные значения используются из-за свойства неотрицательной меры.

Answer 2

Прежде всего, вы должны понимать, что d подчиняется неравенству треугольника. Давайте докажем это противоречием:

Предположим, для любых 3 произвольных строк a,b а также c у нас есть d(a,c)>d(a,b)+d(b,c), но в этом случае мы можем найти d(a,c) с d(a,b)+d(b,c) шаги, следовательно, у нас есть противоречие. Вот почему d подчиняется неравенству треугольника и d(a,c)<=d(a,b)+d(b,c),

Давайте теперь представим, как идет поиск по этому дереву. У нас есть функция поиска f который принимает в качестве входных данных Q - запрос и N - максимальное расстояние.

Вопрос: Почему эта функция должна смотреть на ребра, которые находятся в сегменте [d-n,d+n]?

Давайте теперь представим пару других строк. Позволять x быть строкой, такой, что d(Q,x)<=n, позволять t быть текущим узлом, который мы исследуем. Понятно, что в приведенных выше обозначениях d означало d(Q,t),

Итак, чтобы переформулировать вышеупомянутый вопрос, мы можем задать:

Зачем d(Q,t)-n<=d(t,x)<=d(Q,t)+n?

Для простоты обозначим d(Q,t) как a, d(t,x) как b, а также d(Q,x) как c,

Из неравенства треугольника ясно, что

1. a+b>=c => b>=c-a
2. a+c>=b
3. b+c>=a => b>=a-c

Из 1. и 3. видно, что b>=|a-c|, Итак, чтобы сложить все вместе, мы получаем |a-c|<=b<=a+c,

Теперь, это не конец доказательства, мы также имеем дело с 0<=c<=N,

Это можно легко сделать так:a-N<=a-c<=|a-c|<=b<=a+c<=a+N => a-N<=b<=a+N и с тех пор b>=0, у нас есть max(a-N,0)<=b<=a+N,

Answer 3

В дальнейшем пусть d будет расстоянием от слова запроса до тестового слова (слова в текущем узле), а n будет максимальным расстоянием, которое вы хотите найти. Вы заинтересованы в том, чтобы доказать это

n - d ≤ d(test, anyResultingWord) ≤ n + d.

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

Вы на самом деле не должны использовать - и на самом деле, вероятно, не должны! - использовать неравенство треугольника, чтобы получить верхнюю границу.

Помните, что d(x, y) определяется как расстояние Левенштейна между x и y, которое является минимальным количеством вставок, удалений или замен, необходимых для превращения x в y. Мы хотим, чтобы верхняя граница d (test, anyResultingWord) была равна n + d. Для этого обратите внимание на следующее. Начиная с тестового слова, вы можете преобразовать его в любое результирующее слово следующим образом:

• Начните с преобразования его обратно в слово запроса, которое требует редактирования.
• Преобразуйте слово запроса в результирующее слово, которое принимает n правок.

В целом, это дает серию всего n + d правок, необходимых для преобразования слова теста в слово результата. Это может быть лучший способ сделать это, но это не так. Что мы можем сказать, так это то, что d (test, anyResultingWord) должно быть не более n + d, поскольку мы знаем, что можем преобразовать тест в результирующее слово не более чем в n + d правках. Отсюда и верхняя граница - это не следствие неравенства треугольника, а следствие того, как определяется метрика расстояния.