阅读this post about BK Trees，我发现以下片段有点令人困惑：
“假设我们有两个参数，查询，我们在搜索中使用的字符串，以及字符串可以来自查询的最大距离，并且仍然可以返回。假设我们采用任意字符串，测试并将其与查询进行比较调用合成距离d。因为我们知道三角形不等式成立，所以我们所有的结果必须至多距离d + n且距离测试至少距离dn。
我可以直观地看到，如果某些东西是d远离我正在搜索的单词并且我有一个容忍n错误，那么我至少需要d-n距离我所用的单词“反转”差异。同样地，我最多可以拥有d+n，因为在“扭转”差异后，我可以引入更多的差异。
我很困惑如何使用三角不等式来得到它。如果我们让d（测试，查询）= d和d（查询，找到）<= n然后由不等式：
d(test, query) + d(test, nextWordToSearch) >= d(query, found)
d + d(test, nextWordToSearch) >= n
我们怎么能找到
d - n <= d(test, nextWordToSearch) <= d + n
使用@ templatetypedef的答案，我能够使用Triangle Inequality来查找上限和下限。
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|
由于非负测量的属性而使用的绝对值。
在下文中，设d是查询字到测试字（当前节点处的字）的距离，n是您愿意搜索的最大距离。你有兴趣证明这一点
n - d≤d（test，anyResultingWord）≤n+ d。
您在涉及三角不等式的问题中使用的数学足以建立下界。我认为你遇到上限问题的原因是你实际上并不想在这里使用三角不等式。
你实际上不需要使用 - 事实上，可能不应该使用！ - 使用三角不等式得到上界。
请记住，d（x，y）定义为x和y之间的Levenshtein距离，这是将x转换为y所需的最小插入，删除或替换次数。我们希望在n + d处上限d（test，anyResultingWord）。为此，请注意以下事项。从测试单词开始，您可以将其转换为任何结果单词，如下所示：
总的来说，这给出了将测试词转换为结果词所需的一系列n + d总编辑。这可能是最好的方法，但可能不是。我们可以说d（test，anyResultingWord）必须最多为n + d，因为我们知道我们可以将测试转换为最多n + d次编辑的结果字。这是上限来自的地方 - 它不是三角不等式的结果，而是距离度量如何定义的结果。
首先，你必须明白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。
从三角不等式中可以清楚地看出
a+b>=c => b>=c-aa+c>=bb+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。