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

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

阅读论文的第 7 部分:

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

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

“Dictionary matching and indexing with errors and don't care”，它在时间 O(m+log(nm)^d+occ) 使用空间 O(n*log(nm)^d) 解决了 d-query 问题)， 在哪里occ为查询结果条数。

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

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