相关疑难解决方法(0)

问题:

给定一个大的(~1亿)无符号32位整数列表,无符号32位整数输入值和最大汉明距离,返回在输入值的指定汉明距离内的所有列表成员.

保持列表的实际数据结构是开放的,性能要求决定了内存中的解决方案,构建数据结构的成本是次要的,查询数据结构的低成本是至关重要的.

例:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

到目前为止我的想法:

对于汉明距离为0的退化情况,只需使用排序列表并对特定输入值进行二分搜索.

如果汉明距离只有1,我可以翻转原始输入中的每一位并重复上述32次.

如何有效地(不扫描整个列表)发现汉明距离> 1的列表成员.

我的数据库中有一个表,我将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上运行,所以我想说可能唯一的方法就是分解子字符串中的二进制字符串,将每个二进制子字符串转换为整数,计算汉明距离子串,然后添加它们.这个问题是它听起来非常复杂,效率不高,绝对不优雅.因此,我的问题是:你能提出更好的建议吗？(请注意我在共享主机上,因此我无法修改数据库服务器或加载库)

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

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

编辑(3):我的答案包含我刚才描述的代码.

编辑(4):我刚刚发现使用4个BIGINT来存储哈希而不是BINARY(32)会产生大量的速度提升(速度提高100倍以上).请参阅下面的评论.

有一个包含N个固定长度字符串的数据库.有一个相同长度的查询字符串.问题是从数据库中获取具有最小汉明距离的第k个字符串到q.

N很小(约400),弦长,长度固定.数据库不会更改,因此我们可以预先计算索引.查询变化很大,缓存和/或预计算不是一种选择.每秒有很多.我们总是需要k结果,即使k-1结果匹配0(在汉明距离上排序并取第一个k,因此局部敏感散列和类似方法不会这样做).kd-tree和类似的空间分区可能比线性搜索表现更差(字符串可能很长).BK树目前是最好的选择,但它仍然比它需要的慢和复杂.

感觉就像有一个算法,它将构建一个索引,它将在很少的步骤中丢弃大多数条目,留下k <= t << N个条目来计算实际的汉明距离.

人们建议基于Levenstein距离的模糊字符串匹配 - 谢谢,但问题要简单得多.基于广义距离度量的方法(如BK树)是好的,但也许有利用上述事实(小DB /长固定大小的字符串,简单的汉明距离)

链接,关键字,论文,想法？=)

我们正在将 MySQL 5.7 数据库迁移到 PostgreSQL 9.6。

一个真正的问题是bit_countPostgreSQL缺乏功能。此功能在即将发布的版本 10 中也不可用。

当前 MySQL 代码片段（简化）：

-- mysql specific, tested with 5.7.19
select code,phash,bit_count(phash ^ -9187530158960050433) as hd 
from documents 
where phash is not null and bit_count(phash ^ -9187530158960050433) < 7
order by hd;

我们尝试了一个简单的解决方案（将 BIGINT 转换为字符串并计算“1”），但与 MySQL 相比，它的表现非常糟糕。

Java使用了 Hacker's Delight 的一个技巧，但 AFAIK 这在 PostgreSQL 中是不可能的，因为该>>>运算符（也）不可用。

问题：是否有与 MySQL 性能相当的解决方案/解决方法？

更新 1

我能找到的最佳解决方案是基于这个 SO 答案：

首先创建bit_count函数：

CREATE OR REPLACE FUNCTION bit_count(value …