在数据库中存储和索引二进制字符串

Question

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

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

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

Answer 1

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

因此，

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 的最佳方式。我认为您希望它是一个接近位串度量空间“中心”的位串。

Answer 2

您可以使用类似于 levenshtein 自动机 的方法，应用到位串：

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

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