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

小编典典

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

mysql

我在数据库中有一个表，其中将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上使用，所以我想说，唯一的方法是将子字符串中的二进制字符串分解，将每个二进制子字符串转换为整数，然后计算将汉明距离按字符串细分，然后将其添加。问题在于，这听起来非常复杂，效率不高，而且绝对不优雅。因此，我的问题是：您能提出更好的建议吗？（请注意，我正在共享主机上，因此无法修改数据库服务器或加载库）

edit（1）：显然可以在PHP中加载整个表并进行计算，但是我宁愿避免使用它，因为此表可能会变得很大。

edit（2）：数据库服务器是MySQL 5.1

edit（3）：下面的答案包含了我上面刚刚描述的代码。

edit（4）：我刚刚发现使用4个BIGINTs而不是BINARY（32）存储哈希可以显着提高速度（快100倍以上）。请参阅下面对我的答案的评论。

阅读 759

2020-05-17

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

2020-05-17