小编m20*_*16b的帖子

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

• 给定一个查询号码Q，查询距离d，以及一组数字S，确定是否不S包含任何与汉明距离数小于或等于d。

最简单的解决方案是制作S一个列表并对其进行迭代，计算距离。如果计算出的距离小于或等于 d，则退出 return TRUE。

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

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

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

但是我想做的很有限。我什至不想用 query distance 计算 set 成员的数量<= d，更不用说枚举它们了。我只是想检查是否存在。这让我想到了布隆过滤器和哈希之类的东西。

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

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

编辑和动机：

最终这来自一个编码理论问题。对于给定的偶数d和字长N，我可以将多少个具有最小汉明距离 d 的代码放入一个 N 位数字中？这允许创建可以检测d/2位错误的代码，纠正多达d/2-1位的错误。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊最小汉明距离的长码，它们需要很长时间才能解码。还有像 OLSC …

我有一个矩阵B，我想获得一个C维度(L+k)*m为的矩阵L*n。L和k是输入值。B0 , B1 , ... , Bk大小m为n.

例如 ：

如果我有一个矩阵B = [1 1 ; 1 1 ; 1 1]与B0 = [1 1]，B1 = [1 1]和B2 = [1 1]，并且每个B0 , B1 , B2维度1由2与k = 2和L = 4。

然后C得到的矩阵由C = [1 1 0 …

我有H带有1/2速率和扩展因子的802.16e 标准的奇偶校验表96：

Hb = 
-1 94 73 -1 -1 -1 -1 -1 55 83 -1 -1 7 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 27 -1 -1 -1 22 79 9 -1 -1 -1 12 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 24 22 81 -1 33 -1 -1 -1 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 …