SQL中二进制字符串的汉明距离
我在数据库中有一个表,其中将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):下面的答案包含了我上面刚刚描述的代码。
回答:
看来,将数据存储在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)
);
以上是 SQL中二进制字符串的汉明距离 的全部内容, 来源链接: utcz.com/qa/425561.html