25

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

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

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

编辑（3）：我下面的答案包含我刚才描述的代码。

编辑（4）：我刚刚发现使用 4 个 BIGINT 来存储哈希而不是 BINARY（32）会产生巨大的速度提升（快 100 倍以上）。请参阅下面对我的答案的评论。

4

2 回答 2

16

将数据存储在列中似乎BINARY是一种必然会表现不佳的方法。获得良好性能的唯一快速方法是将BINARY列的内容拆分为多BIGINT列，每列包含原始数据的 8 字节子字符串。

就我而言（32 字节），这意味着使用 4BIGINT列并使用此函数：

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)
  );
于 2011-01-24T14:55:46.727 回答
1

有趣的问题，我找到了一种方法来为 a 执行此操作，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
于 2011-01-23T23:49:41.453 回答