此处定义的二进制字符串是固定大小的位“数组”。我称它们为字符串，因为它们没有顺序(将它们排序/索引为数字没有意义)，每一位都独立于其他位。每个这样的字符串都是 N 位长，N 以百为单位。
我需要存储这些字符串，并使用汉明距离作为距离度量，为最近的邻居提供一个新的二进制字符串查询。
有专门的数据结构(度量树)用于基于度量的搜索(VP 树、覆盖树、M 树)，但我需要使用常规数据库(在我的例子中是 MongoDB)。
是否有一些索引函数可应用于二进制字符串，以帮助数据库在执行一对一汉明距离匹配之前仅访问记录的子集？ 或者，如何在标准数据库上实现这种基于汉明的搜索？
最佳答案
汉明距离是一个度量，因此它满足三角不等式。对于数据库中的每个位串，您可以将它的汉明距离存储到某个预定义的常量位串。然后就可以利用三角不等式过滤掉数据库中的位串。
让我们说
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，使得下限高于最低上限。
对于选择哪个 C 的最佳方式，我不是 100% 确定。我想您会希望它是一个靠近您的位串度量空间“中心”的位串。
关于database - 在数据库中存储和索引二进制字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6597713/