3

此处定义的二进制字符串是固定大小的位“数组”。我称它们为字符串，因为它们没有顺序（将它们排序/索引为数字没有意义），每一位都独立于其他位。每个这样的字符串都有 N 位长，其中 N 为数百。

我需要存储这些字符串，并使用汉明距离作为距离度量，为最近的邻居提供一个新的二进制字符串查询。
基于度量的搜索（VP-trees、cover-trees、M-trees）有专门的数据结构（metric-trees），但我需要使用常规数据库（在我的例子中是 MongoDB）。

是否有一些索引功能可以应用于二进制字符串，可以帮助数据库在执行一对一的汉明距离匹配之前只访问记录的子集？或者，如何在标准数据库上实现这种基于汉明的搜索？

4

2 回答 2

4

汉明距离是一个度量，因此它满足三角不等式。对于数据库中的每个位串，您可以将其汉明距离存储到某个预定义的常量位串。然后可以使用三角不等式过滤掉数据库中的位串。

所以让我们说

C <- some constant bitstring
S <- bitstring you're trying to find the best match for
B <- a bitstring in the database
distS <- hamming_dist(S,C)
distB <- hamming_dist(B,C)

因此，对于每个B，您都将存储它对应的distB。

的下限hamming(B,S)为abs(distB-distS)。上限是distB+distS。

您可以丢弃所有B这样的下限高于最低上限。

我不能 100% 确定选择哪种C. 我认为您希望它是一个接近位串度量空间“中心”的位串。

于 2011-07-06T15:58:25.327 回答
2

您可以使用类似于levenshtein automata的方法，应用于位串：

  1. 计算满足您的汉明距离标准的第一个（字典上最小的）位串。
  2. 从数据库中获取大于或等于该值的第一个结果
  3. 如果该值匹配，则将其输出并获取下一个结果。否则，计算下一个大于匹配的值，然后转到 2。

这相当于对您的数据库和可能的匹配列表进行合并连接，而不必生成每个可能的匹配。它会减少搜索空间，但仍可能需要大量查询。

于 2011-07-07T00:55:34.753 回答