SQL中二进制字符串的汉明距离

Question

我的数据库中有一个表,我将SHA256哈希存储在BINARY(32)列中.我正在寻找一种方法来计算列中条目的汉明距离到提供的值,即:

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

(如果您想知道,字符串A和B的汉明距离定义为BIT_COUNT(A^B),其中^是按位XOR运算符,BIT_COUNT返回二进制字符串中的1的数量).

现在,我知道^运算符和BIT_COUNT函数都只能在INTEGER上运行,所以我想说可能唯一的方法就是分解子字符串中的二进制字符串,将每个二进制子字符串转换为整数,计算汉明距离子串,然后添加它们.这个问题是它听起来非常复杂,效率不高,绝对不优雅.因此,我的问题是:你能提出更好的建议吗？(请注意我在共享主机上,因此我无法修改数据库服务器或加载库)

编辑(1):显然在PHP中加载整个表并进行计算是可能的,但我宁愿避免它,因为这个表可能会变得非常大.

编辑(2):数据库服务器是MySQL 5.1

编辑(3):我的答案包含我刚才描述的代码.

编辑(4):我刚刚发现使用4个BIGINT来存储哈希而不是BINARY(32)会产生大量的速度提升(速度提高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方法快100多倍.

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)
  );