测试针对集合的最小汉明距离的算法？

Question

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

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

最简单的解决方案是制作 S一个列表并对其进行迭代，计算距离。如果计算出的距离小于或等于 d，则退出返回 TRUE .
但是考虑到我想要做的就是检查是否存在，比线性时间解决方案更快的东西应该是可能的。
我试过的一件事是 M-tree .引用有关 stackoverflow 的其他一些问题、维基百科文章 ( https://en.wikipedia.org/wiki/M-tree ) 和两个预先存在的实现，我昨天花了几个小时来实现自定义解决方案。这个问题的一个好处是，通过两个数字的异或(使用 SSE 指令)计算 popcount 实际上比存储允许避免计算度量的数字更便宜，因此解决方案的几个方面可以简化和优化速度。
结果非常令人失望。事实证明，与最小汉明距离相比，我正在处理的公制半径很小。例如，在 12 位数字的空间中，最大汉明距离是 12。如果我要寻找的最小值是 4，那么就没有太多机会进行良好的非重叠分区。事实上，我只是尝试过，通过蛮力创建一组最小汉明距离为 4 的 12 位数字，然后(通过蛮力)找到最佳二叉树分区，以便搜索算法可以访问最少数量的节点。如果我想 计数 查询的 d 内的集合元素的数量，我不能将节点访问次数减少到总数的 30% 以下，并且当我发现第一个访问了大约 4% 时停止。这意味着我或多或少做了一个线性时间解决方案，其中精心设计的树搜索算法的开销与不必检查尽可能多的集合成员所节省的开销大致相同。
但是我想做的很有限。我什至不想计算查询距离 <= d 的集合成员的数量，更不用说列举它们了。我只是想检查是否存在。这让我想到了布隆过滤器和哈希之类的东西。
我还考虑过尝试构建一个图结构，其中集合成员通过带权重的边连接。使用汉明距离尊重三角不等式这一事实，在我看来，必须有某种方法来搜索此图，使得边遍历导致与查询的距离可能更小，但我什至不知道从哪里开始这里。
有没有人对这里的解决方案有任何其他建议，可以轻松击败简单迭代数组的性能？
编辑和动机:
最终这来自一个编码理论问题。对于给定的偶数 d和字号 N ，我可以将多少个具有最小汉明距离 d 的代码放入一个 N 位数字中？这允许创建可以检测 d/2 错误的代码。位纠正错误高达 d/2-1位。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊最小汉明距离的长码，它们需要很长时间才能解码。还有像 OLSC 这样的多位错误代码可以快速解码，但它们的空间效率远非如此。另一方面，对于 d = 4 , 扩展汉明 (SECDED) 码是最佳紧凑的。我见过基于 BCH 的方法来制作 DECTED 代码，但我不知道它们是否是最佳的。为了探索最佳编码，我想做的是生成 N 的替代代码集。位与一些任意 d 并生成电路来对它们进行编码和解码，选择最紧凑的。我还希望找到一些我们可以利用的更长代码的模式。
如果这 (a) 还没有完成，(b) 可行，并且 (c) 有人想合着一篇论文，请告诉我。 :)

Answer 1

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

这个算法在文章中有描述:Alex X. Liu, Ke Shen, Eric Torng. Large scale Hamming distance query processing, 2011 .作者将该算法称为 HEngine。我试图解释一些直觉。

让 N - 数字的位数(它的维数)

k - 查询汉明距离

r-cut(α) - 将数字 α 分成 r 个子串 {α1, α2, ..., αr} 的函数，其中前 r − (m mod r) 个子串的长度为 ⌊m/r⌋，最后一个 m mod r子串的长度为 ⌈m/r⌉

该算法基于以下定理:

对于任何两个二进制串 β 和 γ 使得 HD(β, γ) ≤ k，考虑 r-cut(β) 和 r-cut(γ)，其中 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 进行预处理，以便于找到 S 中满足签名匹配属性的所有字符串 β，然后验证这些字符串中哪些实际上在 α 的汉明距离 k 内。

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

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