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

Question

目前我在一个有大量哈希值（字符串）的应用程序上工作。
当给定查询哈希值（字符串）时，搜索过程会遍历这些字符串并返回查询字符串和结果字符串之间的汉明距离小于给定阈值的字符串。

• 哈希值不是二进制字符串。例如“ 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

阅读论文的第 7 部分：

“HmSearch：一种高效的汉明距离查询处理算法”。

d-query 问题的最新结果可以在以下位置找到：

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

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

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

Answer 2

像这样的东西可能对你有用。

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