Tim*_*ler 5 algorithm set hamming-distance
我想做一件相对简单的事情：
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 这样的多位错误代码可以快速解码，但它们的空间效率远非如此。另一方面，对于d = 4，扩展汉明 (SECDED) 码是最佳紧凑的。我见过基于 BCH 的方法来制作 DECTED 代码，但我不知道它们是否是最佳的。为了探索最佳编码，N位与一些任意 d 并生成电路来对它们进行编码和解码，选择最紧凑的。我还希望找到一些我们可以利用的更长代码的模式。
如果这 (a) 还没有完成，(b) 可行，并且 (c) 有人想合着一篇论文，请告诉我。:)
我认为这个问题可以通过将每个数字从S拆分为子字符串来解决，这样查询结果必须至少有 1 个分区，其与查询的相应分区的汉明距离不超过 1。
\n该算法在文章中进行了描述：Alex X. Liu, Ke Shen, Eric Torng。大规模汉明距离查询处理，2011。作者将该算法称为HEngine。我尝试解释一些直觉。
\n让N - 数字的位数（它的维数）
\nk - 查询汉明距离
\nr-cut(\xce\xb1) - 将数字\xce\xb1分割为r子串{\xce\xb11, \xce\xb12, ..., \xce\xb1r}的函数，其中第一个r \xe2\x88\ x92 (m mod r)子串的长度为\xe2\x8c\x8am/r\xe2\x8c\x8b，最后m mod r子串的长度为\xe2\x8c\x88m/r\xe2\x8c\x89
\n该算法基于以下定理：
\n对于任意两个二进制字符串\xce\xb2和\xce\xb3使得HD(\xce\xb2, \xce\xb3) \xe2\x89\xa4 k，考虑r-cut(\xce\xb2)和r-cut (\xce\xb3)其中r \xe2\x89\xa5 \xe2\x8c\x8ak/2\xe2\x8c\x8b + 1。必须是HD(\xce\xb2i, \xce\xb3i) \xe2\x89\xa4 1对于至少q = r \xe2\x88\x92 \xe2\x8c\x8ak/2\xe2\x8c\ x8b i的不同值。
\n例如，我们有长度为N = 8位的二进制字符串。我们想找到k = 2的子串。
\n\xce\xb1 = 10001110\n\xce\xb2 = 10100110\nHD(\xce\xb1, \xce\xb2) = 2\n然后r = \xe2\x8c\x8a2/2\xe2\x8c\x8b + 1 = 2的最小值。在这种情况下，r-cut(\xce\xb1,\xce\xb2)生成 2 个长度为 4 位的子串：
\n \xce\xb11 = 1000 \xce\xb12 = 1110\n \xce\xb21 = 1010 \xce\xb22 = 0110\nHD(\xce\xb11, \xce\xb21) = 1, HD(\xce\xb12, \xce\xb22) = 1\nq = 2 - \xe2\x8c\x8a2/2\xe2\x8c\x8b = 1。
\n作者还介绍了下一个定理：
\n考虑任何字符串\xce\xb2 \xe2\x88\x88 T使得HD(\xce\xb1, \xce\xb2) \xe2\x89\xa4 k。给定任何r \xe2\x89\xa5 \xe2\x8c\x8ak/2\xe2\x8c\x8b + 1，则至少有一个签名\xce\xb2 -signature 与其兼容签名\xce\xb1 -signature 匹配。
\n该算法的基本思想是对S进行预处理，以便于找到S中满足签名匹配属性的所有字符串\xce\xb2 ，然后验证这些字符串中的哪些实际上在\xce\xb1的汉明距离k内。
\n我想你应该使用 HEngine 算法将S集准备到子表，并以相同的方式将Q拆分为分区。然后按对应分区进行搜索，并考虑到与对应分区的汉明距离不大于1。
\n我建议您在文章中查看更多详细信息。
\n| 归档时间： |
|
| 查看次数： |
928 次 |
| 最近记录： |