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

Question

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

27

我在数据库中有一个表，其中我在BINARY(32)列中存储SHA256哈希值。我正在寻找一种方法来计算该列条目与提供的值之间的汉明距离，即类似于：

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函数只适用于整数，所以我认为可能唯一的方法是将二进制字符串分成子字符串，将每个二进制子字符串转换为整数，逐个子字符串计算汉明距离，然后相加。问题在于这听起来非常复杂，不高效，绝对不优雅。因此，我的问题是：你能否提出更好的方法？（请注意，我使用的是共享托管，因此无法修改DB服务器或加载库）

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

编辑(2)：DB服务器是MySQL 5.1

编辑(3)：我的下面的答案包含了我刚才描述的代码。

编辑(4)：我刚刚发现，使用4个BIGINT来存储哈希而不是BINARY(32)可以极大地提高速度（超过100倍）。请参见下面对我的答案的评论。

- CAFxX

如有必要，可以随意建议不同的哈希存储方式以寻找更好的解决方案。 - CAFxX

如果您将哈希存储在8个整数中（可能除了二进制存储之外），计算就会变得更容易。 - Andomar

我正在尝试使用phasher在mysql上进行海明距离计算。我刚刚尝试了这个查询，但似乎没有返回最接近的具有相似签名的记录。你能解释一下吗？ - TomSawyer

@TomSawyer 我不是通灵的，所以没有看到你的代码就无法知道问题出在哪里。在我的情况下，它运行得相当好（请参见我下面的答案）。 - CAFxX

请参阅相关答案：您可以扩展它，将所有计算作为函数在数据库中进行。https://dev59.com/KmHVa4cB1Zd3GeqPlUcT#47487949 - Philippe Ombredanne

显示剩余4条评论

2个回答

1

有趣的问题，我已经找到了一种方法可以用于 binary(3)，可能也适用于 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 函数会移除所有的零，剩下的长度就是二进制中 1 的个数。（转换为二进制时省略前导零，因此计算零的数量不起作用。）

这将打印出 6，与二进制中 1 的数量相匹配。

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010

- Andomar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CAFxX · Accepted Answer

看起来把数据存储在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倍以上。

顺便说一下，这是我在解释问题时暗示的代码。欢迎更好的方法来完成同样的事情（我特别不喜欢二进制>十六进制>十进制转换）：

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