3

阅读这篇关于 BK Trees 的帖子，我发现以下代码段有点令人困惑：

“假设我们有两个参数，查询，我们在搜索中使用的字符串，以及字符串可以与查询的最大距离并且仍然返回。假设我们采用任意字符串，测试并将其与查询进行比较. 称结果距离为 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
4

3 回答 3

3

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

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

于 2016-01-22T19:22:40.493 回答
1

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

假设任意 3 个字符串a，我们有b，但在这种情况下，我们可以通过步骤找到，因此我们有矛盾。这就是为什么服从三角不等式和。cd(a,c)>d(a,b)+d(b,c)d(a,c)d(a,b)+d(b,c)dd(a,c)<=d(a,b)+d(b,c)

现在让我们想象一下如何通过那棵树进行搜索。我们有一个搜索功能，它以查询和最大距离f作为输入。QN

问题：为什么该函数需要查看段中的边[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)as a、d(t,x)asb和d(Q,x)as表示为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。

于 2018-09-17T18:45:14.773 回答
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 次编辑中将测试转换为结果词。这就是上限的来源——它不是三角不等式的结果，而是距离度量的定义方式的结果。

于 2016-01-17T21:26:43.517 回答