string - 从三角不等式理解 BK 树 : How do we derive the (d-n, d+n) 范围？

Question

阅读 this post about BK Trees ，我发现以下代码片段有点令人困惑:

"Assume for a moment we have two parameters, query, the string we are using in our search, and n the maximum distance a string can be from query and still be returned. Say we take an arbitary string, test and compare it to query. Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test."

我可以直观地看到，如果某些东西与我正在搜索的词相差 d 并且我可以容忍 n 错误，那么我至少需要d-n 与我要“反转”差异的单词的距离。同样，我最多可以有 d+n，因为在“反转”差异之后，我可以再引入 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|

由于非负度量的属性而使用绝对值。