测试一组最小汉明距离的算法？
Algorithm to test minimum hamming distance against a set?
我有一件比较简单的事情想做：
- 给定查询编号
Q、查询距离d和一组编号S，确定S是否包含任意 个汉明距离小于或等于 d. 的数字
最简单的解决方案是只创建 S 一个列表并迭代它，计算距离。如果计算出的距离小于或等于 d，则退出 return TRUE.
但考虑到我只想检查是否存在，比线性时间解决方案更快的方法应该是可能的。
我试过的一件事是M-tree。参考关于 Whosebug 的其他一些问题、维基百科文章 (https://en.wikipedia.org/wiki/M-tree) 和两个预先存在的实现，我昨天花了几个小时实现了一个自定义解决方案。关于这个问题的好处之一是，通过两个数字的异或（使用 SSE 指令）计算 popcount 实际上比存储允许避免计算度量的数字更便宜，因此解决方案的几个方面可以简化和优化速度。
结果非常令人失望。事实证明，与最小汉明距离相比，我正在处理的公制半径很小。例如，在 12 位数字的 space 中，最大汉明距离为 12。如果我要寻找的最小值是 4，则不会为良好的非重叠分区留下太多机会。事实上，我就是这样尝试的，通过蛮力创建一组最小汉明距离为 4 的 12 位数字，然后（通过蛮力）找到最佳二叉树分区，以便搜索算法可以访问最少数量的节点。如果我想统计查询d内集合元素的个数，我无法将节点访问次数减少到总数的30%左右以下，发现首先它访问了大约 4%。这意味着我或多或少做了一个线性时间的解决方案，其中精心设计的树搜索算法的开销与不必检查尽可能多的集合成员所节省的开销大致相同。
但是我想做的很有限。我什至不想计算查询距离为 <= d 的集合成员的数量，更不用说枚举它们了。我只想检查是否存在。这让我想到布隆过滤器和哈希之类的东西。
我也考虑过尝试构建一个图结构，其中集合成员通过带权重的边连接。使用汉明距离尊重三角不等式这一事实，在我看来必须有某种方法来搜索此图，以便边遍历导致与查询的距离可能更小的方向，但我什至不知道从哪里开始这里。
有没有人对这里的解决方案有任何其他建议，可以轻松击败简单迭代数组的性能？
编辑和动机：
最终这来自一个编码理论问题。对于给定的偶数 d 和字长 N，我可以将多少个最小汉明距离 d 的代码放入一个 N 位数中？这允许创建一个代码，可以检测 d/2 位的错误，纠正最多 d/2-1 位的错误。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊的最小汉明距离的长码，并且它们需要很长时间才能解码。还有像 OLSC 这样的多位错误代码可以快速解码，但它们远非 space 高效。另一方面，对于 d = 4，扩展汉明 (SECDED) 代码最紧凑。我见过基于 BCH 的方法来制作 DECTED 代码，但我不知道它们是否是最佳的。为了探索最佳编码，我想做的是用一些任意的 d 生成 N 位的替代代码集，并生成电路来编码和解码它们，选择最紧凑的。我也希望找到一些可以用于更长代码的模式。
如果这 (a) 尚未完成，(b) 可行，并且 (c) 有人想合着一篇论文，请告诉我。 :)
我认为可以通过将每个数字从 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。对于至少 q = r − ⌊k/2⌋ 不同的值，必须是 HD(βi, γi) ≤ 1的 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，可以得出至少一个签名 β-signature 与其兼容的签名 α-签名.
算法的基本思想是对S进行预处理，方便查找S[=]中的所有字符串β 80=]满足签名匹配属性，然后验证这些字符串中哪些实际上在α的汉明距离k内。
我想你应该用HEngine算法将S的集合准备成子表，然后用同样的方法将Q拆分成分区。考虑到对应分区的汉明距离不大于1，再按对应分区进行搜索
我建议您在文章中查看更多详细信息。
我有一件比较简单的事情想做：
- 给定查询编号
Q、查询距离d和一组编号S，确定S是否包含任意 个汉明距离小于或等于d. 的数字
最简单的解决方案是只创建 S 一个列表并迭代它，计算距离。如果计算出的距离小于或等于 d，则退出 return TRUE.
但考虑到我只想检查是否存在，比线性时间解决方案更快的方法应该是可能的。
我试过的一件事是M-tree。参考关于 Whosebug 的其他一些问题、维基百科文章 (https://en.wikipedia.org/wiki/M-tree) 和两个预先存在的实现，我昨天花了几个小时实现了一个自定义解决方案。关于这个问题的好处之一是，通过两个数字的异或（使用 SSE 指令）计算 popcount 实际上比存储允许避免计算度量的数字更便宜，因此解决方案的几个方面可以简化和优化速度。
结果非常令人失望。事实证明，与最小汉明距离相比，我正在处理的公制半径很小。例如，在 12 位数字的 space 中，最大汉明距离为 12。如果我要寻找的最小值是 4，则不会为良好的非重叠分区留下太多机会。事实上，我就是这样尝试的，通过蛮力创建一组最小汉明距离为 4 的 12 位数字，然后（通过蛮力）找到最佳二叉树分区，以便搜索算法可以访问最少数量的节点。如果我想统计查询d内集合元素的个数，我无法将节点访问次数减少到总数的30%左右以下，发现首先它访问了大约 4%。这意味着我或多或少做了一个线性时间的解决方案，其中精心设计的树搜索算法的开销与不必检查尽可能多的集合成员所节省的开销大致相同。
但是我想做的很有限。我什至不想计算查询距离为 <= d 的集合成员的数量，更不用说枚举它们了。我只想检查是否存在。这让我想到布隆过滤器和哈希之类的东西。
我也考虑过尝试构建一个图结构，其中集合成员通过带权重的边连接。使用汉明距离尊重三角不等式这一事实，在我看来必须有某种方法来搜索此图，以便边遍历导致与查询的距离可能更小的方向，但我什至不知道从哪里开始这里。
有没有人对这里的解决方案有任何其他建议，可以轻松击败简单迭代数组的性能？
编辑和动机：
最终这来自一个编码理论问题。对于给定的偶数 d 和字长 N，我可以将多少个最小汉明距离 d 的代码放入一个 N 位数中？这允许创建一个代码，可以检测 d/2 位的错误，纠正最多 d/2-1 位的错误。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊的最小汉明距离的长码，并且它们需要很长时间才能解码。还有像 OLSC 这样的多位错误代码可以快速解码，但它们远非 space 高效。另一方面，对于 d = 4，扩展汉明 (SECDED) 代码最紧凑。我见过基于 BCH 的方法来制作 DECTED 代码，但我不知道它们是否是最佳的。为了探索最佳编码，我想做的是用一些任意的 d 生成 N 位的替代代码集，并生成电路来编码和解码它们，选择最紧凑的。我也希望找到一些可以用于更长代码的模式。
如果这 (a) 尚未完成，(b) 可行，并且 (c) 有人想合着一篇论文，请告诉我。 :)
我认为可以通过将每个数字从 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。对于至少 q = r − ⌊k/2⌋ 不同的值，必须是 HD(βi, γi) ≤ 1的 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，可以得出至少一个签名 β-signature 与其兼容的签名 α-签名.
算法的基本思想是对S进行预处理，方便查找S[=]中的所有字符串β 80=]满足签名匹配属性，然后验证这些字符串中哪些实际上在α的汉明距离k内。
我想你应该用HEngine算法将S的集合准备成子表，然后用同样的方法将Q拆分成分区。考虑到对应分区的汉明距离不大于1，再按对应分区进行搜索
我建议您在文章中查看更多详细信息。