了解 BK 树：我们如何从三角不等式中导出 (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 从我所在的单词到 "reverse" 的差异。同样，我最多可以有 d+n 因为在 "reversing" 个差异之后，我可以再引入 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

在下文中，d 是查询词到测试词（当前节点处的词）的距离，n 是您愿意搜索的最大距离。您有兴趣证明

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

您在涉及三角不等式的问题中使用的数学足以确定下界。我认为您遇到上限问题的原因是您实际上并不想在这里使用三角不等式。

您实际上不需要使用 - 事实上，可能不应该使用！ - 使用三角不等式得到上限。

请记住，d(x, y) 定义为 x 和 y 之间的 Levenshtein 距离，这是将 x 变为 y 所需的最少插入、删除或替换次数。我们希望在 n + d 处设置上限 d(test, anyResultingWord)。为此，请注意以下事项。从测试词开始，您可以将其转换为任何结果词，如下所示：

首先将其转换回查询词，这需要 d 次编辑。
将查询词转换为结果词，这需要 n 次编辑。

总的来说，这给出了将测试词转换为结果词所需的一系列 n + d 总编辑。这可能是最好的方法，但也可能不是。我们可以说的是 d(test, anyResultingWord) 必须最多为 n + d，因为我们知道我们可以在最多 n + d 次编辑中将测试转换为结果词。这就是上限的来源——它不是三角不等式的结果，而是距离度量定义方式的结果。

Answer 2

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

由于 non-negative 测量的属性使用了绝对值。

Answer 3

首先你要明白d服从三角不等式。让我们用反证法证明这一点：

Suppose for any 3 arbitrary strings a,b and c we have d(a,c)>d(a,b)+d(b,c), but in that case we can find d(a,c) with d(a,b)+d(b,c) steps, hence we have a contradiction. This is why d obeys the triangle inequality and d(a,c)<=d(a,b)+d(b,c).

现在让我们想象一下搜索那棵树的过程。我们有一个搜索函数 f，它将 Q——一个查询和 N——最大距离作为输入。

Question: Why does that function need to look at edges that are in the segment [d-n,d+n]?

现在让我们介绍几个其他字符串。令 x 为字符串，使得 d(Q,x)<=n 令 t 为我们正在检查的当前节点。显然，在上面的符号中 d 表示 d(Q,t).

因此，要重新表述上述问题，我们可以问：

Why 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-a
a+c>=b
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.

了解 BK 树：我们如何从三角不等式中导出 (d-n, d+n) 范围？

Understanding BK Trees: How do we derive the (d-n, d+n) range from the triangle inequality?

string

algorithm

tree

data-structures

bk-tree