SQLのバイナリ文字列のハミング距離

Question

DBには、SHA256ハッシュをバイナリ（32）列に保存するテーブルがあります。列のエントリのハミング距離を供給された価値に計算する方法を探しています。つまり、次のようなものです。

SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(hash, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10

（あなたが疑問に思っている場合、文字列AとBのハミング距離は次のように定義されています BIT_COUNT(A^B), 、ここで、 ^はbitwise xor演算子であり、bit_countはバイナリ文字列の1の数を返します）。

今、私は ^演算子とbit_count関数の両方が整数でのみ機能することを知っているので、おそらくそれを行う唯一の方法は、サブストリングのバイナリ文字列を分割し、各バイナリサブストリングを整数にキャストし、計算することだと思います。距離をハミングすると、それらを追加します。これに関する問題は、それがひどく複雑で、効率的ではなく、間違いなくエレガントではないことです。したがって、私の質問は次のとおりです。もっと良い方法を提案できますか？ （私は共有ホスティングを使用しているため、DBサーバーやロードライブラリを変更できないことに注意してください）

編集（1）：明らかにテーブル全体をPHPでロードし、計算を行うことが可能ですが、このテーブルはおそらく非常に大きくなるので、むしろそれを避けたいと思います。

編集（2）：DBサーバーはmysql 5.1です

編集（3）：以下の私の回答には、上記で説明したコードが含まれています。

編集（4）：バイナリ（32）の代わりにハッシュを保存するために4つのBIGINTSを使用すると、大規模な速度の改善が得られることがわかりました（100倍以上）。以下の私の答えへのコメントを参照してください。

Answer 1

データを保存するように見えます BINARY 列は、パフォーマンスが低下するようになったアプローチです。まともなパフォーマンスを得るための唯一の高速な方法は、 BINARY 複数の列 BIGINT それぞれが元のデータの8バイトのサブストリングを含む列。

私の場合（32バイト）、これは4を使用することを意味します BIGINT 列とこの関数の使用：

CREATE FUNCTION HAMMINGDISTANCE(
  A0 BIGINT, A1 BIGINT, A2 BIGINT, A3 BIGINT, 
  B0 BIGINT, B1 BIGINT, B2 BIGINT, B3 BIGINT
)
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(A0 ^ B0) +
  BIT_COUNT(A1 ^ B1) +
  BIT_COUNT(A2 ^ B2) +
  BIT_COUNT(A3 ^ B3);

私のテストでは、このアプローチを使用すると、 BINARY アプローチ。

---

FWIW、これは問題を説明しながら示唆していたコードです。同じことを達成するためのより良い方法は歓迎されます（私は特にバイナリ>ヘックス>小数の変換が好きではありません）：

CREATE FUNCTION HAMMINGDISTANCE(A BINARY(32), B BINARY(32))
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 1,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 1,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 9,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 9,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 17, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 17, 8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 25, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 25, 8)), 16, 10)
  );

Answer 2

興味深い質問、私はこれを行う方法を見つけました binary(3) それはaのためにも機能するかもしれません binary(32):

drop table if exists BinaryTest;
create table  BinaryTest (hash binary(3));
insert BinaryTest values (0xAAAAAA);

set @supplied = cast(0x888888 as binary);

select  length(replace(concat(
            bin(ascii(substr(hash,1,1)) ^ ascii(substr(@supplied,1,1))),
            bin(ascii(substr(hash,2,1)) ^ ascii(substr(@supplied,2,1))),
            bin(ascii(substr(hash,3,1)) ^ ascii(substr(@supplied,3,1)))
        ),'0',''))
from    BinaryTest;

replace すべてのゼロを削除し、残りの長さはゼロの数です。 （バイナリへの変換はリーディングゼロを省略しているため、ゼロをカウントすることは機能しません。）

これはプリントです 6, 、の数と一致します

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010