十六进制值的Mysql汉明距离

Question

我在mysql中存储了一些哈希值，我想通过汉明距离的比较来提取它们。

所存储的哈希值如下：

qw 1 ffe71b001820a1fd 
qw 2 ffffb81c1c3838a0 
qw 3 fff8381c1c3e3828 
qw 4 fffa181c3c2e3920 
qw 5 fffa981c1c3e2820 
qw 6 ff5f1c38387c1c04 
qw 7 fff1e0c1c38387ef 
qw 8 fffa181c1c3e3820 
qw 9 fffa381c1c3e3828

我通常这样获取：

SELECT product_id, HAMMING_DISTANCE(phash, 'phashfromuserinput') ;

但在MySQL中，汉明距离是按位运算符，如果字符串仅为数字，则可以执行该操作：

SELECT pagedata,BIT_COUNT(pagecontent^'$encrypted')searchengine WHERE pagecontent > 2 ; ")

它只适用于整数（数字），但我的要求是能够处理数字和字母，例如：

74898fababfbef46 and 95efabfeba752545

从我所了解的，首先我需要将字段转换为 binary，然后使用 CAST 或 CONVERT 来使用 bitcount。

SELECT BIT_COUNT( CONV( hash, 2, 10 ) ^ 
0b0000000101100111111100011110000011100000111100011011111110011011 )

或者

SELECT BIT_COUNT(CAST(hash AS BINARY)) FROM data;

这样将数据转换为二进制并使用位计数是可行的。现在问题是，mysql中存储的varbinary字符/哈希已经是字母数字混合的，如果我将字段转换为varbinary并使用位计数，那么它将无法工作，因为存储的哈希不是二进制字符串。

我该怎么办？

我正在参考PHP汉明距离匹配的示例：

function HammingDistance($bin1, $bin2) {
    $a1 = str_split($bin1);
    $a2 = str_split($bin2);
    $dh = 0;
    for ($i = 0; $i < count($a1); $i++) 
        if($a1[$i] != $a2[$i]) $dh++;
    return $dh;
}

echo HammingDistance('10101010','01010101'); //returns 8

但我不明白如何和mysql匹配并获取，因为我无法在mysql中实现它。

- 125fura

---

汉明距离适用于二进制值。前九个值似乎是16个十六进制数字，易于解释为64位二进制值。我们知道如何处理它。然后你说“仅适用于整数”...这有点正确，因为我们可以将64位二进制值表示为BIGINT。然后你说你的要求是“和字母”[sic]，并且你展示了包含'v'和'g'的值，而这些不是有效的十六进制数字。在这个问题能够被回答之前，你需要解释一下二进制值“95gfgdgd75425456”代表什么。 - spencer7593

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - 125fura

我理解了问题。我不明白的是字符串**74898acvdf566556和95gfgdgd7542545应该代表什么二进制值。（这些是十六个字符，大多数字符都是有效的十六进制数字，但是字符v和g不是有效的十六进制数字。）至于你的“主要疑问是它是否适用于字母数字”... 不，它不适用。海明距离适用于**二进制值。将十六进制字符串表示转换为二进制很容易... - spencer7593

好的，实际上74898acvdf566556和95gfgdgd7542545是打错了，它们应该是74898fababfbef46和95efabfeba752545，也就是十六进制。 - 125fura

是的，在比较两个值之前，请将它们都转换为64位二进制。在MySQL中，这意味着转换的目标数据类型是BIGINT UNSIGNED。您可以使用CAST或CONVERT函数，并指定UNSIGNED作为目标数据类型。您用于执行该转换的MySQL表达式取决于您要从中进行转换的数据类型/表示形式。请参见Rick James的答案，以了解将包含16个十六进制数字的文字字符串或varchar列转换的示例。 - spencer7593

Answer 1

以最后两个数字为例：

SELECT BIT_COUNT( CAST(CONV('fffa181c1c3e3820', 16, 10) AS UNSIGNED) ^
                  CAST(CONV('fffa381c1c3e3828', 16, 10) AS UNSIGNED) ) ;
--> 2

• 散列值是十六进制的。
• 转换后需要以BIGINT UNSIGNED结束。

（如果您使用MD5（128位）或SHA1（160位）哈希，则需要通过SUBSTR()将它们拆分，对每个对进行XOR，BIT_COUNT，然后将结果相加。）

编辑以使用列名：

SELECT BIT_COUNT( CAST(CONV( a.pagecontent , 16, 10) AS UNSIGNED) ^
                  CAST(CONV( b.pagecontent , 16, 10) AS UNSIGNED) ) ;

- Rick James

---

@spencer7593，数据以varchar（16）和qw的形式存储，4个是名称和编号，但不是必需的。 - 125fura

@RickJames 数据表如下：CREATE TABLE searchengine ( id INT NOT NULL AUTO_INCREMENT , pageurl BLOB NOT NULL , pagecontent varchar(16) NOT NULL , PRIMARY KEY (id) ) ENGINE = MYISAM - 125fura

那应该澄清之前的问题。这并不改变我的建议解决方案。还有什么问题？ - Rick James

这个答案展示了你将使用的MySQL表达式，以计算从十六进制字符串表示转换而来的64位二进制值的汉明差异。我认为这回答了所提出的问题，即如何在MySQL表达式中计算汉明距离。 - spencer7593

对于使用超过64位的任何人，请注意。这不起作用，至少不是“原样”。您需要将十六进制数分成16位组，每个组进行BIT_COUNT，然后将位数相加。 - Rick James