ハミング距離は、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

を減らすことは理にかなって ここに証拠だから、それはおそらく単純に行うことができますが、それはあまりにも悪くはないということ。求めています

ビットストリングの長さの誘導では、基本ケースは、明らかに不等式が成り立つ空のストリングです。

誘導ステップは、我々は両方に0を付加した場合にAとB

• の両方にビットを（任意の違いを確認しない、または追記）先頭に追加され、popcntsはそれほど変わりません不平等は依然として残る。
• もしそれらのうちの1つに0を付加して1を他方に加えるならば、それらのXORはもう1ビットが設定され、LHSが1だけ上がるようになります。RHSでは、popcntの1つが、絶対差は可換である）、その結果、RHSはになります。は1（LHSと同じ、問題ありません）またはの1つ下になります（まだうまくいけば、RHSはLHSより小さくすることができますしかし、これが平等ではない理由です）
• 両方に1を追加すると、そのXORは変化しないので、LHSは同じままです。 RHSでは、両方のpopcntが1つ上がると、互いに打ち消し合うので、RHSも同じままです。

このように、この不等式は任意の長さのビット列に適用されます。