sql - 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)，其中 ^ 是按位异或运算符，BIT_COUNT 返回 1 的数量在二进制字符串中)。

现在，我知道 ^ 运算符和 BIT_COUNT 函数都只适用于整数，所以我想说可能唯一的方法是将二进制字符串分解为子字符串，将每个二进制子字符串转换为整数，计算汉明距 ionic 串，然后将它们相加。这样做的问题是它听起来非常复杂，效率不高，而且绝对不优雅。因此，我的问题是:您能提出更好的方法吗？ (请注意，我使用的是共享主机，因此无法修改数据库服务器或加载库)

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

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

edit(3):我下面的答案包含我刚才描述的代码。

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