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

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



我可以直观地看到，如果 d 远离我正在搜索的单词，并且我可以容忍 n 错误，那么我至少需要与我所在单词的 d-n 距离才能“逆转”差异。同样，我最多可以拥有 d+n，因为在“逆转”差异之后，我可以引入更多差异。

我很困惑如何使用三角不等式来得到这个。如果我们让 d(test, query) = d 和 d(query, found)

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

我们怎样才能找到

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

最佳答案

使用@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|

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

关于string - 从三角不等式了解 BK 树 : How do we derive the (d-n, d+n) 范围？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34842803/