汉明距离的MySQL

Question

的MySQL架构和查询在这里

http://sqlfiddle.com/#!9/444873/1

查询似乎工作并返回我只行 有汉明距离小于7位。

看来，下面的属性适用于：

bit_count(a^b) >= abs(bit_count(a) - bit_count(b)) 

一些例子

   bit_count 
a  1111  4 
b  0000  0 
a^b 1111  4 

a  1010  2 
b  0110  2 
a^b 1100  2 

a  1001  2  
b  1001  2 
a^b 0000  0 

是上述不等式真的吗？

如果有人可以提供证据吗？

我问的是，因为，如果上述不等式为真，那么 我使用的索引有意义的减少查询时间

Answer 1

这里有一个证明，大概可以做到简单，但它不是太糟糕了。

随着比特串的长度感应，基本情况是空串，对此，不等式显然成立。

的感应步骤前面加上（或附加，不作任何差异）中的比特，以A和B

• 既，如果我们在前面加上0至两个，所述popcnts不改变，因此不平等依然成立。
• 如果我们预先给他们中的一个赋值0，而将1赋值给另一个，那么他们的XOR将会有一个比特集，所以LHS会上升1.在RHS中，其中一个弹出窗口会增加（无所谓，绝对差值是可交换的），因此RHS将或者通过1（与LHS相同，没有问题）或者下降 1（尽管如此，RHS允许小于LHS的上升 ，但这就是为什么它不是平等）
• 如果我们在两者之前加上1，它们的XOR不会改变，所以LHS保持不变。在RHS中，两支球员都增加了1个，他们相互抵消，所以RHS也保持不变。

因此，这种不等式适用于任何长度的位串。