搜索汉明距离小于阈值的字符串

Question

目前我正在使用大量散列值（字符串）的应用程序。
当给出查询散列值（字符串）时，搜索过程将遍历这些字符串并返回查询字符串与结果字符串之间的Hamming Distance小于给定阈值的字符串。

• 哈希值是而不是二进制字符串。例如“1000302014771944008”
• 所有哈希值（字符串）具有相同的固定长度。
• 阈值不小（通常为t>25）并且可能会有所不同。

我想用一种有效的算法来实现这个搜索过程，而不是使用暴力方法。
我已阅读一些研究论文（如this & this），但它们适用于二进制字符串或低阈值。我也试过Locality-sensitive hashing，但我发现的实现主要集中在二进制字符串上。

是否有任何算法或数据结构来解决这个问题？
任何建议也欢迎。先谢谢你。

。

其他信息

海明非二进制字符串

string 1: 0014479902266110001131133 
string 2: 0014409902226110001111133 
      ------------------------- 
       1  1  1 = 3 <-- hamming distance 

考虑蛮力方法之间的距离

1. 首先计算哈希字符串和之间的海明距离查询哈希字符串。
2. 如果汉明距离小于阈值，则将哈希串添加到结果列表中。
3. 对所有散列字符串重复步骤1和2。

Answer 1

像这样的东西可以为你工作。

http://blog.mafr.de/2011/01/06/near-duplicate-detection/

Answer 2

阅读该文章的第7部分：

“HmSearch：一种有效海明距离查询处理算法”。

国家的技术的结果为d查询问题，可以发现：

“字典匹配和索引错误和不关心”，它解决在时间为O d-查询问题（米+ log（nm）^ d + occ）使用空间O（n * log（nm）^ d），其中 occ是查询结果的数目。

如果阈值不是很小，那么在HmSearch上可以找到适用于二进制字符串的实际解决方案。

我认为可以将HmSearch上找到的相同实用解决方案应用于任意字符串，但我从未见过这些解决方案。