针对一组测试最小汉明距离的算法？

我想做一件相对简单的事情：

• 给定一个查询号码Q, 查询距离d，和一组数字S, 判断是否S包含any汉明距离小于或等于的数字d.

最简单的解决方案就是使S一个列表并迭代它，计算距离。如果计算出的距离小于或等于 d，则退出返回TRUE.

但考虑到我想做的只是检查是否存在，比线性时间解决方案更快的东西应该是可能的。

我尝试过的一件事是M-tree。参考 stackoverflow 上的一些其他问题，维基百科文章 (https://en.wikipedia.org/wiki/M-tree https://en.wikipedia.org/wiki/M-tree）和两个预先存在的实现，我昨天花了几个小时来实现一个自定义解决方案。这个问题的好处之一是，通过两个数字的 XOR（使用 SSE 指令）计算 popcount 实际上比存储可以避免计算指标的数字更便宜，因此该解决方案有几个方面：可以简化并优化速度。

结果非常令人失望。事实证明，与最小汉明距离相比，我正在处理的公制半径很小。例如，在 12 位数字的空间中，最大汉明距离是 12。如果我要寻找的最小值是 4，那么就没有太多机会进行良好的非重叠分区。事实上，我就是这样尝试的，通过暴力创建一组最小汉明距离为 4 的 12 位数字，然后（通过暴力）找到最佳二叉树分区，以便搜索算法可以访问最少数量的节点。如果我想count查询 d 内的集合元素数量，我无法将节点访问数量减少到总数的约 30% 以下，并且当我发现第一个节点访问数量约为 4% 时停止。这意味着我或多或少地提出了一个线性时间解决方案，其中复杂的树搜索算法的开销与不必检查尽可能多的集合成员所节省的开销大致相同。

但我想做的事情却很有限。我什至不想计算具有查询距离的集合成员的数量<= d，更不用说列举它们了。我只是想检查是否存在。这让我思考诸如布隆过滤器和哈希之类的事情。

我还考虑过尝试构建一个图形结构，其中集合成员通过带有权重的边连接。利用汉明距离尊重三角不等式这一事实，在我看来，必须有某种方法来搜索该图，以便边缘遍历导致到查询的距离可能更小的方向，但我什至不知道从哪里开始这里。

有没有人对这里的解决方案有任何其他建议，可以轻松击败简单迭代数组的性能？

编辑和动机：

归根结底，这来自于编码理论问题。对于给定的偶数d和字大小N，一个 N 位数字可以容纳多少个最小汉明距离 d 的代码？这允许创建可以检测错误的代码d/2位纠正错误高达d/2-1位。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊最小汉明距离的长码，并且它们需要很长时间才能解码。还有像 OLSC 这样的多位错误码，解码速度很快，但空间利用率很低。另一方面，对于d = 4，扩展汉明 (SECDED) 代码是最佳紧凑的。我见过基于 BCH 的方法来制作 DECTED 代码，但我不知道它们是否是最佳的。为了探索最佳编码，我想做的是生成替代的代码集N具有任意 d 的位并生成电路来编码和解码它们，选择最紧凑的。我还希望找到一些可以用于更长代码的模式。

如果 (a) 尚未完成，(b) 可行，以及 (c) 有人想共同撰写一篇论文，请告诉我。 :)

我认为这个问题可以通过将每个数字分开来解决S到子字符串，使得查询结果必须至少有 1 个分区与查询的相应分区的汉明距离不大于 1。

文章中描述了这个算法：Alex X. Liu，沉克，Eric Torng。大规模汉明距离查询处理，2011 https://ieeexplore.ieee.org/document/5767831。作者将该算法称为HEngine。我尝试解释一些直觉。

Lets N- 数字的位数（它的维数）

k- 查询汉明距离

r-cut(α)- 分号功能α into r子串{α1, α2, ..., αr}第一个在哪里r - (m 模 r)子串有长度⌊m/r⌋和最后一个m mod r子串有长度⌈m/r⌉

该算法基于以下定理：

对于任意两个二进制字符串β and γ这样HD(β,γ)≤k， 考虑r-cut(β) and r-cut(γ) where r ≥ ⌊k/2⌋ + 1。一定是这样的HD(βi,γi)≤1至少q = r − ⌊k/2⌋的不同值i.

例如，我们有长度的二进制字符串N = 8位。我们想找到子串k = 2.

α = 10001110
β = 10100110
HD(α, β) = 2

那么最小值r = ⌊2/2⌋ + 1 = 2。在这种情况下r-cut(α,β)产生 2 个长度为 4 位的子串：

    α1 = 1000    α2 = 1110
    β1 = 1010    β2 = 0110
HD(α1, β1) = 1,  HD(α2, β2) = 1

q = 2 - ⌊2/2⌋ = 1.

作者还介绍了下一个定理：

考虑任何字符串β ∈ T这样HD(α, β) ≤ k。给定任意r ≥ ⌊k/2⌋ + 1，由此可知至少有一个签​​名β-签名与其兼容的签名相匹配α-签名。

该算法的基本思想是预处理S方便查找所有字符串β in S满足签名匹配属性，然后验证这些字符串中的哪些实际上在汉明距离内k of α.

我想你应该准备一套S使用HEngine算法分表，并拆分Q以同样的方式进行分区。然后按对应分区进行搜索，并考虑到与对应分区的汉明距离不大于1。

我建议您在文章中查看更多详细信息。